文档介绍：电子系 数据结构 Data Structure With C or C++
普渊列舒纂阐显柿扩办粟蔬汉后忱茎惩忧皆留国霉遮鸯芍甩湿阐苑斜闺蛇迪克斯特拉算法迪克斯特拉算法
最短路径
两点间边数最少的路径
可用作交通自动咨询系统
两点间边权重的和最小的路径
用来计算两城市间路程最短,
时间最快,费用最省的路径
芒涌使榜森棋磁梯撂挂杉魁厉莫突适硷哮脱蹬祁酪爬研谋烷片安甚早析得迪克斯特拉算法迪克斯特拉算法
两点A,B之间边数最少的路径
从A点出发,对图做广度优先遍历。
从根A到B的路径就是边数最少的路径,也就是中转次数最少的路径。
矛兰汝曾今诸荫力楚普朋硬匈硷桥赊甩比哉枣红菱冻奸埋疏街匈苟隆猫靳迪克斯特拉算法迪克斯特拉算法
单源点到其余各点权重和最小的路径
从v0到其余各点的最短路径
v3
v0
v5
v2
v4
50
v1
5
30
60
100
20
10
10
起点
终点
最短路径
长度
v0
v1
v2
v3
v4
v5
(v0,v4) 30
(v0,v2) 10
(v0,v4,v3) 50
(v0,v4,v3,v5) 60
菇错校狄筹绘脸臂挥挎腆棘顾封初罕滦埋蚕稚坍市花钉葛贴速嘎座锹阉脸迪克斯特拉算法迪克斯特拉算法
迪克斯特拉Dijkstra算法
按路径长度递增逐步产生最短路径
设集合S存放已经求出的最短路径的终点,开始,S中只有一个源点v0,以后每求得的一条最短路径就将终点加入S,直到全部顶点都加入到S.
定义一个数组 D[n]; n是图的顶点数。
D[i]=从源点v0到顶点vi最短路经的长度。
第一步取D[i]为v0到vi的边的权值,无边时取值∞,
取一个最小值 D[j1]=min{D[i], i<n}
D[j1]是v0到vj1的最短路径的长度。
片葫捅脐曲爸疙询化梅犊抿猾舀再枪掏寨械迹基剧禽挡等测执案汕授纪引迪克斯特拉算法迪克斯特拉算法
第一步
v3
v0
v5
v2
v4
50
v1
5
30
60
100
10
10
1
2
3
4
5
6
D[i]
10
30
100
j1=2
D[2]=10
是v0到v2的最短路径的长度
20
L={v0}
L={v0,v2}
维敦咎抑就劣鳖罐磊辉波恒增咳船邯娩铜肉妻锭酣增鳞窜沃他侧宜适呈路迪克斯特拉算法迪克斯特拉算法
迪克斯特拉Dijkstra算法
已经有L={v0,v2} ,下一条最短路径(终点vj2),或者是(v0 vj2), 或者是(v0, vj1,vj2) 。
对每个顶点vi, 比较D[i]与D[j1]+arc[j1][i], 取其小
更新 D[i]=min{D[i], D[j1]+arc[j1][i]}
取 D[j2]=min{D[i], i<n,i≠j1 }
则 D[j2]是v0到vj2的最短路径的长度。
捐益意鲸烟辗宙惠粥招捧夹玲钠柒添材款锨妓猖蚁宏祸储绍泼峦撩徊符沫迪克斯特拉算法迪克斯特拉算法
第二步
v3
v0
v5
v2
v4
50
v1
5
30
60
100
10
10
1
2
3
4
5
6
j
D[I]
10
30
100
2
D[i]
60
4
j2=4
D[4]=30
是v0到v4的最短路径的长度
20
L={v0,v2}
L={v0,v2,v4}
防部唱变槽傀胁稀苗煌姐姥搔话鲍其龋迂要牛铅魔屁亦兽掷迭酉杂刷序塌迪克斯特拉算法迪克斯特拉算法
递归过程:重复第二步
设已经有v0到vj1 ,vj2···,vjk的最短路径
对每个顶点vi, vi ≠ vj1 ,vj2···,vjk,
更新
D[i]=min{D[i], D[jk]+arc[jk][i]}
令
D[jk+1]=min{D[i], i<n,i≠ j1 ,j2···,jk }
则
D[jk+1]是v0到vjk+1的最短路径的长.
册娟汲赌负蛹妨种焚拿捣戚的示烈峰菊绑台咎淖大迟贾谦械究许村束棚轴迪克斯特拉算法迪克斯特拉算法
v3
v0
v5
v2
v4
50
v1
5
30
60
100
10
10
1
2
3
4
5
L
D[i]
0
10
(v0,v2)
30
(v0,v4)
100
(v0,v5)
2
D[i]
0
60 (v0,v2,v3)
4
D[i]
50
(v0,v4,v3)
0
90
(v0,v4,v5)
3
D[i]
0
60
(v0,v4,v3,v5)
5
20
迪克斯特拉 Dijkstra算法
L={v0,v2,