文档介绍：13 十一月 2017
第1页
最短路径、关键路径及其应用
所谓最短路径问题是指:如果从图中某一顶点(称为源点)出发到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和达到最小。
最短路径问题
求从某个源点到其余各点的最短路径
13 十一月 2017
第3页
每一对顶点之间的最短路径
13 十一月 2017
第4页
求从源点到其余各点的最短路径的算法的基本思想:
依最短路径的长度递增的次序求得各条路径
源点
v1
…
其中,从源点到顶点v的最短路径是所有路径中长度最短者。
v2
给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。
V5
V0
V2
V4
V1
V3
100
30
10
60
10
20
50
5
V0
V2
V4
V3
V5
V0
始点终点 D[i] 最短路径
V1
V2
V3
V4 V5
∞
10
∞
30
100
∞
10
∞
30
100
∞
10
60
30
100
∞
10
60
30
100
∞
10
50
30
100
(V0, V2)
(V0, V4)
(V0, V5)
(V0, V2)
(V0, V4)
(V0, V5)
(V0, V2)
(V0, V2, V3)
(V0, V4)
(V0, V5)
(V0, V2)
(V0, V2, V3)
(V0, V4)
(V0, V5)
(V0, V2)
(V0, V4, V3)
(V0, V4)
(V0, V5)
∞
10
50
30
90
(V0, V2)
(V0, V4, V3)
(V0, V4)
(V0, V4, V5)
∞
10
50
30
90
(V0, V2)
(V0, V4, V3)
(V0, V4)
(V0, V4, V5)
∞
10
50
30
60
(V0, V2)
(V0, V4, V3)
(V0, V4)
(V0, V4, V3, V5)
∞
10
50
30
60
(V0, V2)
(V0, V4, V3)
(V0, V4)
(V0, V4, V3, V5)
13 十一月 2017
第6页
在这条路径上,必定只含一条弧,并且这条弧的权值最小。
下一条路径长度次短的最短路径的特点:
路径长度最短的最短路径的特点:
它只可能有两种情况:或者是直接从源点到该点(只含一条弧); 或者是从源点经过顶点v1,再到达该顶点(由两条弧组成)。
13 十一月 2017
第7页
其余最短路径的特点:
再下一条路径长度次短的最短路径的特点:
它可能有三种情况:或者是直接从源点到该点(只含一条弧); 或者是从源点经过顶点v1,再到达该顶点(由两条弧组成);或者是从源点经过顶点v2,再到达该顶点。
它或者是直接从源点到该点(只含一条弧); 或者是从源点经过已求得最短路径的顶点,再到达该顶点。
如何在计算机中求得最短路径?
13 十一月 2017
第9页
求最短路径的迪杰斯特拉算法:
一般情况下,
Dist[k] = <源点到顶点 k 的弧上的权值>
或者= <源点到其它顶点的路径长度>
+ <其它顶点到顶点 k 的弧上的权值>。
设置辅助数组Dist,其中每个分量Dist[k] 表示当前所求得的从源点到其余各顶点 k 的最短路径。
Dijkstra提出了一个按路径“长度”递增的次序,逐步得到由给定源点到图的其余各点间的最短路径的算法:
假设我们以邻接矩阵cost表示所研究的有向网。
迪杰斯特拉算法需要一个顶点集合,初始时集合内只有一个源点V0 ,以后陆续将已求得最短路径的顶点加入到集合中,到全部顶点都进入集合了,过程就结束了。集合可用一维数组来表示,设此数组为S,凡在集合S以外的顶点,其相应的数组元素S[i] 为 0 ,否则为 1 。