专栏文章

Dijkstra算法

lliyao2025
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqjnru7
此快照首次捕获于
2025/12/04 05:53
3 个月前
此快照最后确认于
2025/12/04 05:53
3 个月前
查看原文

最短路径

  • 路径长度: 当图是带权图时，把从一个顶点i到图中其余任意一个顶点j的一条路径(可能不止一条)所经过边上的权值之和，定义为该路径的带权路径长度。
  • 最短路径: 把带权路径长度最短的那条路径称为最短路径。
备注:求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。
  • 带权有向图G的最短路径问题一般可分为两类: (1)单源最短路径:求图中某一顶点到其他各顶点的最短路径。 (2)多源最短路径:求每对顶点间的最短路径。

单源最短路径-Dijkstra算法(迪杰斯特拉)

(1) Dijkstra整体思路:

Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0v_0放入SS，集合SS每并入一个新顶点viv_i，都要修改源点v0v_0到集合V−SV-S中顶点当前的最短路径长度值

(2) 些符号说明:

  • dist[]:dist[]:记录从源点vo到其他各顶点当前的最短路径长度，它的初态为:若从v0v_0到viv_i有弧，则dist[i]dist[i]为弧上的权值;否则置dist[i]dist[i]为∞∞。 邻接矩阵arcsarcs表示带权有向图，arcs[i][j]arcs[i][j]表示有向边<i,j><i,j>的权值，若不存在有向边<i,j><i,j>则arcs[i][j]arcs[i][j]为∞∞。

(3) Dijkstra算法流程: (求解vo到其他节点的最短路径)

  1. 初始化:集合S初始为0{0}，dist[]dist[]的初始值dist[i]=arcs[0][i]dist[i]=arcs[0][i], i=1,2…,n−1i=1,2…, n-1
  2. 2)从顶点集合V−SV-S中选出vjvj,满足dist[j]=Mindist[i]∣i∈V−S,vjdist[j]=Min{dist[i] | i \in V-S},v_j就是当前求得的一条从v_0出发的最短路径的终点，令S=SUjS=S U {j}
  3. 修改从v0v_0出发到集合V−SV-S上任一顶点vkv_k可达的最短路径长度:若 dist[j]+arcs[j][k]<dist[k],则更新dist[k]=dist[j]+arcs[j][k]dist[j]+arcs[j][k]<dist[k],则更新dist[k]=dist[j]+arcs[j][k]。 4)重复2)-3)操作共n-1次，直到所有的顶点都包含在S中。
备注:步骤3举例:
如下图所示，源点为vo，初始时S={vo},dist[1]=3,dist[2]=7,当将v1并入集合S后， dist[2]需要更新为4。

(4)模拟Dijkstra的过程

  • 图解
  • 表格方式
  • 文字描述
初始化:集合SS初始为vi{v_i}，v1v_1可达v2v_2和v3v_3,v1v_1不可达v3v_3和v4v_4，因此dist[]dist[]数组各元素的初 值依次设置为dist[2]=10，dist[3]=∞,dist[4]=∞,dist[5]=5dist[2]=10， dist[3]=∞,dist[4]=∞,dist[5]=5。
第一轮:选出最小值dist[5]dist[5]，将顶点v5v_5并入集合SS，即此时已找到v1v_1到v5的最短路径。当v_5的最短路径。 当v_5加入加入S后,从后,从v_1到集合到集合V-S中可达顶点的最短路径长度可能会产生变化,因此需要更新中可达顶点的最短路径长度可能会产生变化,因此需要更新dist[]数组。 数组。v_5可达可达v_2,因,因v_1→v_5→v_2的距离8比的距离8比dist[2]=10小,更新小,更新dist[2]=8;;v_5可达可达v_3,, V_1→V_5→V_2→V_3的距离14，更新的距离 14，更新dist[3]=14; ;v_5可达可达 v_4，，V_1→V_5→V_4的距离7，更新的距离 7，更新 dist[4]=7$.
第二轮:选出最小值dist[4]dist[4]，将顶点v4v_4并入集合SS。继续更新dist[]dist[]数组。v4v_4不可达 v2v_2,dist[2]dist[2]不变;v4v_4可达v3v_3，V1→V5→V4→V3V_1→V_5→V_4→V_3的距离1313 比dist[3]dist[3]小，故更新dist[3]=13dist[3]=13.
第三轮:选出最小值dist[2]dist[2]，将顶点v2v_2并入集合SS。继续更新dist[]dist[]数组。v2v_2可达V3V_3,v1→v5→v2→v3v_1→v_5→v_2→v_3的距离99比dist[3]dist[3]小，更新 dist[3]=9dist[3]=9
第四轮:选出唯一最小值dist[3]dist[3]，将顶点v3v_3并入集合SS，此时全部顶点都已包含在SS中。

(5)时间复杂度分析

邻接矩阵存储图:0(∣V∣2):0(|V|^2) 邻接表存储图:0(∣V∣2)0(|V|^2)(虽然修改dist[]dist[]的时间可以减少，但由于在dist[]dist[]中选 择最小分量的时间不变)

(6)不适用条件

当图中含有负权边时，DijkstraDijkstra算法将不适用。(Dijkstra算法Dijkstra算法是基于贪心的)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...