文档介绍：电子系 数据结构 Data Structure With C or C++
精选ppt
最短路径
两点间边数最少的路径
可用作交通自动咨询系统
两点间边权重的和最小的路径
用来计算两城市间路程最短，
时间最快，费用最省的路径
精选ppt
两点A,B之间边数最少的路径
从A点出发，对图做广度优先遍历。
从根A到B的路径就是边数最少的路径，也就是中转次数最少的路径。
精选ppt
单源点到其余各点权重和最小的路径
从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
精选ppt
迪克斯特拉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的最短路径的长度。
精选ppt
第一步
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}
精选ppt
迪克斯特拉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的最短路径的长度。
精选ppt
第二步
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}
精选ppt
递归过程：重复第二步
设已经有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的最短路径的长.
精选ppt
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,v4,v3,v5}
时间复杂性O(n2)
精选ppt