重复上述，直到S中包含V中其余各顶点的最短路径。
V0
100
V5 30
V1
D 终点
V4 10 20 10 V3 5 V 50
2
i=1
∞ 10{V0,2} ∞ 30{V0,4}
60
V0 V1 V2 V3 V4 V5
i=3
∞ 10 50{V0,4,3} 30 90{V0,4,5} V3
{V0,V2,V4,V3}
其中的最小值即为最短路径的长度。
2）修改其它各顶点的Dist[k]值。
假设求得最短路径的顶点为u， 若 Dist[u]+G.arcs[u][k]<Dist[k] 则将 Dist[k] 改为 Dist[u]+G.arcs[u][k]。
2018年12月26日星期三 第13页
求每一对顶点之间的最短路径
弗洛伊德算法的基本思想是：
V3 V2
50
路径长度最短的最短路径的特点：
在这条路径上，必定只含一条弧，并且
这条弧的权值最小。
下一条路径长度次短的最短路径的特点： 它只可能有两种情况：或者是直接从源
点到该点(只含一条弧)； 或者是从源点经
过顶点v1，再到达该顶点(由两条弧组成)。
2018年12月26日星期三 第6页
再下一条路径长度次短的最短路径的特点: 它可能有三种情况：或者是直接从源点到
最短路径、关键路径 及其应用
2018年12月26日星期三
第1页
最短路径问题
所谓最短路径问题是指：如果从图中某一 顶点（称为源点）出发到达另一顶点（称 为终点）的路径可能不止一条，如何找到 一条路径使得沿此路径上各边的权值总和 达到最小。
+ 求从某个源点到其余各点的
最短路径
每一对顶点之间的最短路径
该点(只含一条弧)； 或者是从源点经过顶点 v1，再到达该顶点(由两条弧组成)；或者是 从源点经过顶点v2，再到达该顶点。
其余最短路径的特点： 它或者是直接从源点到该点(只含一条弧 )； 或者是从源点经过已求得最短路径的 顶点，再到达该顶点。
第7页
2018年12月26日星期三
如何在计算机中 求得最短路径？
V5
10
60
V0 V1
5
30
V4
20
始点 终点
V0 V1 V2 V3 V4 V5
D[i]
∞
最短路径
(V0, V2)
10
10
60 50 ∞ 30 100 90 60
(V (V V ,4 V ,2 V )3) 0, 0
(V (V V ,4 V ,4 V )3) 0, 0 2 (V (V V ,4 V , 4V ) 3, 0, 0 (V (V V ,5 V ) ,5 V )5) 0, V 0 4
V1 V2 V3 V4 V5 Vj
S={V0}
100{V0,5} 100{V0,5}
60{V0,4,3,5} V5
{V0,V2,V4,V3,V5}
V2
{V0,V2}
V4
{V0,V2,V4}
{V0,V2,V4,V3,V5 ,V1}
1）在所有从源点出发的弧中选取一条权 值最小的弧，即为第一条最短路径。 G.arcs[v0][k ] V0和k之间存在弧 Dist[k ] INFINITY V0和k之间不存在弧
V0 ∞ ∞ ∞ ∞ ∞ ∞
V1 ∞ ∞ ∞ ∞ ∞ ∞
i=4
∞ 10 50 30
V2 V3 10 ∞ 5 ∞ ∞ 50 ∞ ∞ ∞ 20 ∞ ∞
V4 30 ∞ ∞ ∞ ∞ ∞
V5 100 ∞ ∞ 10 60 ∞
i=5
∞ 10 50 30 60 V1
i=2
∞ 10 60{V0,2,3} 30{V0,4}
பைடு நூலகம்
求最短路径的迪杰斯特拉算法： 设置辅助数组Dist，其中每个分量Dist[k]
表示 当前所求得的从源点到其余各顶点 k 的最短路径。
一般情况下， Dist[k] = <源点到顶点 k 的弧上的权值> 或者 = <源点到其它顶点的路径长度> + <其它顶点到顶点 k 的弧上的权值>。
2018年12月26日星期三 第9页
…
2018年12月26日星期三
依次类推，则 vi 至 vj 的最短路径应是 上述这些路径中，路径长度最小者。
第15页
问题描述： 已知一个各边权值均大于 0 的带权有向图， 对每对顶点 vi≠vj，要求求出每一对顶点之间 的最短路径和最短路径长度。
解决方案：
1. 每次以一个顶点为源点，重复执行迪杰 斯特拉算法n次。这样，便可求得每一对顶点之 间的最短路径。总的执行时间为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。 时间复杂度也为O(n3)。
从 vi 到 vj 的所有可能存在的 路径中，选出一条长度最短的路径。
2018年12月26日星期三
第14页
若<vi,vj>存在，则存在路径{vi,vj} // 路径中不含其它顶点 若<vi,v1>,<v1,vj>存在，则存在路径{vi,v1,vj} // 路径中所含顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在， 则存在一条路径{vi, …, v2, …vj} // 路径中所含顶点序号不大于2

另需一个一维数组D，每个顶点对应数组的一个单元， 记录从源点到其他各顶点当前的最短路径长度，其初值
为D[i]=cost[V0][i]，i=1…n。数组D中的数据随着算法
的逐步进行要不断地修改

定义了S集合和D数组并对其初始化后，迪杰斯特拉算法
在进行中，都是从S之外的顶点集合中选出一个顶点w，
使D[w]的值最小。于是从源点到达w只通过S中的顶点， 把 w 加入集合S中，并调整D中记录的从源点到集合中 每个顶点v的距离： 取D[v]和D[w]+cost[w][v]中值较小的作为新的D[v]
Dijkstra提出了一个按路径“长度”递增的
次序，逐步得到由给定源点到图的其余各点间的
最短路径的算法：

假设我们以邻接矩阵cost表示所研究的有向网。
迪杰斯特拉算法需要一个顶点集合，初始时集合内 只有一个源点V0 ，以后陆续将已求得最短路径的顶
点加入到集合中，到全部顶点都进入集合了，过程
就结束了。集合可用一维数组来表示，设此数组为 S，凡在集合S以外的顶点，其相应的数组元素S[i] 为 0 ，否则为 1 。
2018年12月26日星期三
第3页
求从源点到其余各点的最短路径
的算法的基本思想:
依最短路径的长度递增的次序求得 各条路径
v1 v2
源点
…
其中，从源点到 顶点v的最短路径 是所有路径中长 度最短者。
第4页
2018年12月26日星期三
给定带权有向图G和源点v, 求从v到G中其余 各顶点的最短路径。
100