讲师中心 微信公众号

工具推荐

视频效率加速
updream

一键生成高质量推广成片

立刻MV
立刻MV

低成本歌曲 MV、视频生成

Laper
Laper

剧本策划到成片协作

剧云
剧云

中文短剧剧本制作平台

怎样用Python实现Dijkstra算法求网络最短路径?

雨芳大大_6076

雨芳大大_6076

发布时间:2026-11-22 10:18:25

|

893人浏览过

|

来源于php中文网

原创

直接用heapq实现Dijkstra更可靠,因其是经过充分测试的最小堆,支持高效heappush/heappop维持堆顶为当前最小距离节点;避免用list.sort()或min()导致O(V²)退化;采用“重复入堆+visited跳过”策略处理距离更新。

怎样用python实现dijkstra算法求网络最短路径?

为什么直接用 heapq 实现 Dijkstra 更可靠?

手写优先队列容易出错,而 Python 标准库的 heapq 是经过充分测试的最小堆实现,支持 heappush 和 heappop,能稳定维持当前距离最小的节点在堆顶。Dijkstra 的核心是「每次取未访问中距离最小的节点」,这恰好对应堆顶操作。不推荐用 list.sort() 或 min() 扫描,时间复杂度会退化到 O(V²),尤其图稠密时明显变慢。

注意:heapq 不支持动态更新节点权重,所以采用「允许重复入堆」策略——当发现更短路径时,把新距离连同节点一起推入堆;后续 heappop 出来的若已被处理过(通过 visited 判断),就跳过。这是标准且高效的做法。

邻接表怎么建才适合 Dijkstra?

用字典套列表(或 defaultdict(list))最灵活:graph[u] = [(v, weight), ...]。每个键是起点,值是元组列表,每个元组含终点和边权。别用邻接矩阵——除非节点数极小(

常见错误:边权为负时调用 Dijkstra,结果不可靠。heapq 假设边权非负,一旦出现负权,已标记 visited 的节点可能不是全局最短,算法提前终止导致错误。负权图请改用 Bellman-Ford 或 SPFA。

立即学习“Python免费学习笔记(深入)”;

示例建图:

Define repeatable Python automation sessions in code with nox
Define repeatable Python automation sessions in code with nox

将测试、lint、构建和文档流程编码为命名的Python会话,以便人类和代理每次运行相同的workflow。

下载
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8)],
    'D': []
}

dist 初始化为什么不能全设为 float('inf')?

可以设,但要注意比较逻辑。Python 中 float('inf') + x 仍为 inf,不会报错,但若误写成 dist[v] = min(dist[v], dist[u] + w) 而没加 if not visited[v] 判断,可能触发冗余更新。更稳妥的是初始化为一个足够大的数(如 10**9),或保持 inf 但确保只对未访问节点松弛。

关键点:

  • dist[start] = 0 必须显式设置
  • 使用 visited 数组/集合记录已确定最短距的节点,避免重复处理
  • 松弛前检查 dist[u] + w ,且 <code>v 未被访问过

如何还原最短路径而不是只返回距离?

只需额外维护一个 prev 字典,记录每个节点的前驱节点。每次成功松弛 v 时,执行 prev[v] = u。路径还原时从终点倒推至起点,再反转列表即可。

容易忽略的细节:

  • 起点的 prev[start] 应设为 None,避免倒推时无限循环
  • 若终点不可达,prev.get(end) 会是 None,需提前判断
  • 还原路径时不要用递归,避免深度过大触发 RecursionError

示例还原逻辑:

path = []
curr = end
while curr is not None:
    path.append(curr)
    curr = prev.get(curr)
path = path[::-1]  # 反转得正向路径

实际跑通的关键不在“怎么写循环”,而在建图是否无负权、visited 更新时机是否严格、以及堆中重复节点是否被正确跳过——这三点错一个,结果就可能不对。

热门AI工具

更多
DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

Flowith
Flowith Hot

Flowith是一款基于画布和智能体工作流的 AI 协作工作空间。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

切问学术

切问学术是一款AI论文写作工具,复旦大学NLP团队推出的AI学术智能体。

UpDream
UpDream Hot

一款AI视频创作工具,主要用于哔哩哔哩推出的自研AI视频创作工具,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

花生AI
花生AI Hot

一款AI视频创作工具,主要用于B站推出的AI视频创作工具,适合需要提升相关任务效率的用户。

相关专题

更多
python打包成可执行文件
python打包成可执行文件

本专题为大家带来python打包成可执行文件相关的文章,大家可以免费的下载体验。

1971

2023.07.20

python能做什么
python能做什么

python能做的有:可用于开发基于控制台的应用程序、多媒体部分开发、用于开发基于Web的应用程序、使用python处理数据、系统编程等等。本专题为大家提供python相关的各种文章、以及下载和课程。

5664

2023.07.25

format在python中的用法
format在python中的用法

Python中的format是一种字符串格式化方法,用于将变量或值插入到字符串中的占位符位置。通过format方法,我们可以动态地构建字符串,使其包含不同值。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

1929

2023.07.31

python教程
python教程

Python已成为一门网红语言,即使是在非编程开发者当中,也掀起了一股学习的热潮。本专题为大家带来python教程的相关文章,大家可以免费体验学习。

34797

2023.08.03

python环境变量的配置
python环境变量的配置

Python是一种流行的编程语言,被广泛用于软件开发、数据分析和科学计算等领域。在安装Python之后,我们需要配置环境变量,以便在任何位置都能够访问Python的可执行文件。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

4047

2023.08.04

python eval
python eval

eval函数是Python中一个非常强大的函数,它可以将字符串作为Python代码进行执行,实现动态编程的效果。然而,由于其潜在的安全风险和性能问题,需要谨慎使用。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

4067

2023.08.04

scratch和python区别
scratch和python区别

scratch和python的区别:1、scratch是一种专为初学者设计的图形化编程语言,python是一种文本编程语言;2、scratch使用的是基于积木的编程语法,python采用更加传统的文本编程语法等等。本专题为大家提供scratch和python相关的文章、下载、课程内容,供大家免费下载体验。

1303

2023.08.11

python合并两个列表
python合并两个列表

Python是一种强大的编程语言,具有许多方便的功能和工具。在Python中,有多种方法可以合并两个列表。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

636

2023.08.10

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

0

2026.11.20

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn