Dijkstra 最短路径算法 Python 实现

article/2025/8/25 5:53:53

原文链接
问题描述
使用 Dijkstra 算法求图中的任意顶点到其它顶点的最短路径(求出需要经过那些点以及最短距离)。

以下图为例:

在这里插入图片描述

算法思想
可以使用二维数组来存储顶点之间边的关系
在这里插入图片描述

首先需要用一个一维数组 dis 来存储 初始顶点到其余各个顶点的初始路程,以求 1 顶点到其它各个顶点为例:

在这里插入图片描述

将此时 dis 数组中的值称为最短路的“估计值”。

既然是求 1 号顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。当选择了 2 号顶点后,dis[2] 的值就已经从“估计值”变为了“确定值”,即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。为什么呢?因为目前离 1 号顶点最近的是 2 号顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 1 号顶点到 2 号顶点的路程进一步缩短了。

既然选了 2 号顶点,接下来再来看 2 号顶点有哪些出边。有 2->3 和 2->4 这两条边。先讨论通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。也就是说现在比较 dis[3] 和 dis[2] + G[2][3]的大小。其中 dis[3] 表示 1 号顶点到 3 号顶点的路程。dis[2] + G[2][3] 中 dis[2] 表示 1 号顶点到 2 号顶点的路程,G[2][3] 表示 2->3 这条边。所以 dis[2] + G[2][3] 就表示从 1 号顶点先到 2 号顶点,再通过 2->3 这条边,到达 3 号顶点的路程。

在本例中 dis[3] = 12,dis[2] + G[2][3] = 1 + 9 = 10,dis[3] > dis[2] + G[2][3],所以 dis[3] 要更新为 10。这个过程有个专业术语叫做“松弛”。即 1 号顶点到 3 号顶点的路程即 dis[3],通过 2->3 这条边松弛成功。这是 Dijkstra 算法的主要思想:通过“边”来松弛初始顶点到其余各个顶点的路程。

同理通过 2->4(G[2][4]),可以将 dis[4]的值从 ∞ 松弛为 4(dis[4] 初始为 ∞,dis[2] + G[2][4] = 1 + 3 = 4,dis[4] > dis[2] + G[2][4],所以 dis[4] 要更新为 4)。

刚才对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为:

在这里插入图片描述
接下来,继续在剩下的 3、4、5 和 6 号顶点中,选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组,当前离 1 号顶点最近是 4 号顶点。此时,dis[4] 的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边(4->3,4->5 和 4->6)用刚才的方法进行松弛。松弛完毕之后 dis 数组为:

在这里插入图片描述
继续在剩下的 3、5 和 6 号顶点中,选出离 1 号顶点最近的顶点,这次选择 3 号顶点。此时,dis[3] 的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边(3->5)进行松弛。松弛完毕之后 dis 数组为:
在这里插入图片描述

继续在剩下的 5 和 6 号顶点中,选出离 1 号顶点最近的顶点,这次选择 5 号顶点。此时,dis[5] 的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边(5->4)进行松弛。松弛完毕之后 dis 数组为:
在这里插入图片描述

最后对 6 号顶点所有点出边进行松弛。因为这个例子中 6 号顶点没有出边,因此不用处理。到此,dis 数组中所有的值都已经从“估计值”变为了“确定值”。

最终 dis 数组如下,这便是 1 号顶点到其余各个顶点的最短路径。
在这里插入图片描述
总结一下刚才的算法。算法的基本思想是:每次找到离源点(上面例子的源点就是 1 号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。基本步骤如下:

将所有的顶点分为两部分:已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始,已知最短路径的顶点集合 P 中只有源点一个顶点。这里用一个 visited[ i ]数组来记录哪些点在集合 P 中。例如对于某个顶点 i,如果 visited[ i ]为 1 则表示这个顶点在集合 P 中,如果 visited[ i ]为 0 则表示这个顶点在集合 Q 中;
设置源点 s 到自己的最短路径为 0 即 dis = 0。若存在源点有能直接到达的顶点 i,则把 dis[ i ]设为 G[s][ i ]。同时把所有其它(源点不能直接到达的)顶点的最短路径为设为 ∞;
在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u(即 dis[u] 最小)加入到集合 P。并考察所有以点 u 为起点的边,对每一条边进行松弛操作。例如存在一条从 u 到 v 的边,那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径,这条路径的长度是 dis[u] + G[u][v]。如果这个值比目前已知的 dis[v] 的值要小,我们可以用新值来替代当前 dis[v] 中的值;
重复第 3 步,如果集合 Q 为空,算法结束。最终 dis 数组中的值就是源点到所有顶点的最短路径
注意
Dijkstra 算法不能应用于有负权重的图

Dijkstra 时间复杂度为 O(N2)
Python 实现

def Dijkstra(G, start):# 输入是从 0 开始,所以起始点减 1start = start - 1inf = float('inf')node_num = len(G)# visited 代表哪些顶点加入过visited = [0] * node_num# 初始顶点到其余顶点的距离dis = {node: G[start][node] for node in range(node_num)}# parents 代表最终求出最短路径后,每个顶点的上一个顶点是谁,初始化为 -1,代表无上一个顶点parents = {node: -1 for node in range(node_num)}# 起始点加入进 visited 数组visited[start] = 1# 最开始的上一个顶点为初始顶点last_point = startfor i in range(node_num - 1):# 求出 dis 中未加入 visited 数组的最短距离和顶点min_dis = inffor j in range(node_num):if visited[j] == 0 and dis[j] < min_dis:min_dis = dis[j]# 把该顶点做为下次遍历的上一个顶点last_point = j# 最短顶点假加入 visited 数组visited[last_point] = 1# 对首次循环做特殊处理,不然在首次循环时会没法求出该点的上一个顶点if i == 0:parents[last_point] = start + 1for k in range(node_num):if G[last_point][k] < inf and dis[k] > dis[last_point] + G[last_point][k]:# 如果有更短的路径,更新 dis 和 记录 parentsdis[k] = dis[last_point] + G[last_point][k]parents[k] = last_point + 1# 因为从 0 开始,最后把顶点都加 1return {key + 1: values for key, values in dis.items()}, {key + 1: values for key, values in parents.items()}if __name__ == '__main__':inf = float('inf')G = [[0, 1, 12, inf, inf, inf],[inf, 0, 9, 3, inf, inf],[inf, inf, 0, inf, 5, inf],[inf, inf, 4, 0, 13, 15],[inf, inf, inf, inf, 0, 4],[inf, inf, inf, inf, inf, 0]]dis, parents = Dijkstra(G, 1)print("dis: ", dis)print("parents: ", parents)

输出为

dis:  {1: 0, 2: 1, 3: 8, 4: 4, 5: 13, 6: 17}
parents:  {1: -1, 2: 1, 3: 4, 4: 2, 5: 3, 6: 5}

如果求 1 号顶点到 6 号顶点的最短距离,dis[6] = 17,所以最短距离为 17。

再看 parents[6] = 5,说明 6 号顶点的上一个顶点为 5,parents[5] = 3,说明 5 号顶点的上一个顶点为 3,以此类推,最终 1 号顶点到 6 号顶点的路径为 1->2->4->3->5->6。

优化思路

其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N),可以用“堆”来优化,使得这一部分的时间复杂度降低到 O(logN);
另外对于边数 M 少于 N2 的稀疏图来说(把 M 远小于 N2 的图称为稀疏图,而 M 相对较大的图称为稠密图),可以用邻接表来代替邻接矩阵,使得整个时间复杂度优化到 O((M+N)logN)。注意,在最坏的情况下 M 就是 N2,这样的话 MlogN 要比 N2 还要大。但是大多数情况下并不会有那么多边,所以 (M+N)logN 要比 N2 小很多


http://chatgpt.dhexx.cn/article/giLNwqf9.shtml

相关文章

神经网络最短路径算法,最短路径算法的原理

节约里程法求解最短路问题 你只要记住2点之间直线最短。节约里程法是用来解决运输车辆数目不确定的问题的最有名的启发式算法。1、节约里程法优化过程分为并行方式和串行方式两种。 核心思想是依次将运输问题中的两个回路合并为一个回路&#xff0c;每次使合并后的总运输距离…

最短路径算法及Python实现

最短路径问题 在图论中&#xff0c;最短路径问题是指在一个有向或无向的加权图中找到从一个起点到一个终点的最短路径。这个问题是计算机科学中的一个经典问题&#xff0c;也是许多实际问题的基础&#xff0c;例如路线规划、通信网络设计和交通流量优化等。在这个问题中&#…

图论:图的四种最短路径算法

目录&#xff1a; 1.DFS&#xff08;单源最短路径算法&#xff09; 例题1&#xff1a; DFS题目分析&#xff1a; 代码DFS&#xff1a; 2.Floyed&#xff08;时间复杂度On^3&#xff09; 1.应用场景&#xff1a; 2.解析算法&#xff1a; 核心代码1&#xff1a; 我的笔…

图的五种最短路径算法

本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,费罗伊德算法,迪杰斯特拉算法,Bellman-Ford 算法。 1)深度或广度优先搜索算法(解决单源最短路径) 从起点开始访问所有深度遍历路径或广度优先路径,则到达终点节点的路径有多条,取其中路径权值最短的一…

最短路径算法——Dijkstra算法——python3实现

本文参考来自数据结构与算法分析 java语言描述。 文章目录 问题描述问题分析实现过程如何使用数据变化表代码实现优先队列中的堆排序使用set代替优先队列得到最短路径 负权边算法改进&#xff08;若为无圈图&#xff09; 问题描述 现有一个有向赋权图。如下图所示&#xff1a;…

最短路径算法的编程与实现 C语言

一 、目的&#xff1a; 1.掌握最短路径算法的基本原理及编程实现&#xff1b; 二 、环境&#xff1a; operating system version&#xff1a;Win11 CPU instruction set: x64 Integrated Development Environment&#xff1a;Viusal Studio 2022 三 、内容&#xff1a; 1…

图的四种最短路径算法

本文总结了图的几种最短路径算法的实现&#xff1a;深度或广度优先搜索算法&#xff0c;弗洛伊德算法&#xff0c;迪杰斯特拉算法&#xff0c;Bellman-Ford算法 1&#xff09;&#xff0c;深度或广度优先搜索算法&#xff08;解决单源最短路径&#xff09; 从起始结点开始访问所…

算法之几个常见的经典最短路径算法

目录 1. Dijkstra算法2. Floyd算法3. Bellman-Ford 算法 1. Dijkstra算法 是解单源最短路径问题的贪心算法。 有一向带权图 G (V, E)&#xff0c;包含右n个顶点&#xff0c;其中每条边的权是非负实数&#xff0c;定义数组 dist 为原点到G中各个顶点的距离&#xff0c;初始化为…

最短路径的四种算法

最短路径四种算法 1234FloydDijkstraBellman-Ford队列优化的Bellman-Ford 一&#xff0c;只有四行的算法——Floyd-Warshall 假设求顶点 V i Vi Vi到 V j Vj Vj的最短路径。弗洛伊德算法依次找从 V i Vi Vi到 V j Vj Vj&#xff0c;中间经过结点序号不大于 0 0 0的最短路径&…

最短路径算法

1.最短路径算法分为单源最短路径算法和多源最短路径算法 &#xff08;a&#xff09;单源最短路径算法&#xff0c;可以计算出从起点到任意一个起点的最短路径。 例如&#xff1a;Dijkstra算法 &#xff0c;SPFA算法 &#xff08;b&#xff09;多源最短路径算法&#xff0c;可…

哈夫曼树及其应用

1、哈夫曼树的基本概念 ---- 哈夫曼&#xff08;Huffman&#xff09;树又称作最优二叉树&#xff0c;它是n个带权叶子结点构成的所有二叉树中&#xff0c;带权路径长度最小的二叉树。 ---- “路径”就是从树中的一个结点到另一个结点之间的分支构成的部分&#xff0c;而分支…

哈夫曼树的C语言实现

什么是哈夫曼树 当用 n 个结点&#xff08;都做叶子结点且都有各自的权值&#xff09;试图构建一棵树时&#xff0c;如果构建的这棵树的带权路径长度最小&#xff0c;称这棵树为“最优二叉树”&#xff0c;有时也叫“赫夫曼树”或者“哈夫曼树”。 在构建哈弗曼树时&#xff0…

哈夫曼树的构建及编码

哈夫曼树的构建及编码 文章目录 哈夫曼树的构建及编码一、什么是哈夫曼树二、什么是哈夫曼编码三、怎么建哈夫曼树、求哈夫曼编码四、为什么哈夫曼编码能实现压缩 声明&#xff1a;关于文件压缩&#xff0c;不是本文的重点&#xff0c;本文只说明并讨论哈夫曼树的构建和编码&am…

如何构建一棵哈夫曼树

给一个数列{10,7,8,3,26,5,1},要求转成为一棵哈夫曼树。 分析思路以及图解&#xff1a; 第一步&#xff1a;将数列进行排序&#xff0c;按从小到大的顺序。最终结果为{1,3,5,7,8,10,26}&#xff0c;根据每个数值创建结点&#xff0c;组成结点数组 第二步&#xff1a;取出权值最…

哈夫曼树 (100分)哈夫曼树

4-1 哈夫曼树 (100分)哈夫曼树 第一行输入一个数n&#xff0c;表示叶结点的个数。 需要用这些叶结点生成哈夫曼树&#xff0c;根据哈夫曼树的概念&#xff0c;这些结点有权值&#xff0c;即weight&#xff0c;题目需要输出哈夫曼树的带权路径长度&#xff08;WPL&#xff09;。…

哈夫曼树的编码和解码

哈夫曼树的作用&#xff1a;在数据通信中&#xff0c;需要将传送的文字转换成二进制的字符串&#xff0c;用0&#xff0c;1码的不同排列来表示字符。例如&#xff0c;需传送的报文为“AFTER DATA EAR ARE ART AREA”&#xff0c;这里用到的字符集为“A&#xff0c;E&#xff0c…

哈夫曼树与哈夫曼编码

哈夫曼树 给定n个权值作为n个叶子结点&#xff0c;构造一棵二叉树&#xff0c;若带权路径长度达到最小&#xff0c;称这样的二叉树为最优二叉树&#xff0c;也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树&#xff0c;权值较大的结点离根较近。 树节点间的边…

【例题】哈夫曼树

【例1】由五个分别带权值为9&#xff0c;2&#xff0c;3&#xff0c;5&#xff0c;14的叶子结点构成的一棵哈夫曼树&#xff0c;该树的带权路径长度为_______________。 A、60 B、66 C、67 D、50 答案&#xff1a;C 解析&#xff1a; 关键点在于要学会如何构造哈夫曼树 已知有5…

哈夫曼树以及哈夫曼算法

目录 一、哈夫曼树的定义 二、哈夫曼树的特点 三、哈夫曼算法(构造哈夫曼树的方法) 四、哈夫曼树的构造过程 五、哈夫曼树构造算法的实现 一、哈夫曼树的定义 1、哈夫曼树:最优树即带权路径长度(WPL)最短的树 “带权路径长度最短”是在"度相同”的树中比较而得的结果…

哈夫曼树的绘制

数据结构之哈夫曼树绘制 本人还是一个年轻的程序猿(还是个学生)&#xff0c;请大家多多指教&#xff01; 哈夫曼树 已知权重绘制哈夫曼树 开始我的表演 Step 1. 已知权重&#xff1a;2&#xff0c;3&#xff0c;3&#xff0c;4&#xff0c;7&#xff0c;6 Step 2. 选取其中…