2001 -- 12 -- 27/29
华中科技大学计算机学院 (9)数据结构
7.5 有向无环图及其应用一个无环的有向图称为 有向无环图 （ directed acycline graph),
简称 DAG图。
DA
C
EB
F
B
A
D
E
F
C
6
8
5
7
4 6
2
C
A
D
E
B
F
图 1 图 2 图 3（非 DAG）
7.5.1 拓扑排序
AOV网 （ Activity On Vertex network）：
以顶点表示活动，弧表示活动之间的优先关系的 DAG图。
课程编号 课程名称 先决条件
C1 程序设计基础 无
C2 离散数学 C1
C3 数据结构 C1,C2
C4 汇编语言 C1
C5 语言的设计和分析 C3,C4
C6 计算机原理 C11
C7 编译原理 C5,C3
C8 操作系统 C3,C6
C9 高等数学 无
C10 线性代数 C9
C11 普通物理 C9
C12 数值分析 C9,C10,C1
计算机软件专业课程
C1
C2
C4 C5
C3 C7
C12
C9 C
10
C11
C6
C8
表示课程间关系的有向图拓扑排序,是有向图的全部顶点的一个线性序列，该序列保持了原有向图中各顶点间的相对次序。例：
（ C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8)
（ C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)
拓扑排序算法思想：重复下列操作，直到所有顶点输出完。
（ 1） 在有向图中选一个没有前驱的顶点输出 (选择入度为 0的顶点 )；
（ 2）从图中删除该顶点和所有以它为尾的弧 (修改其它顶点入度 ) 。
V1 V2
V4
V6 V5
V3
V1 V2
V4
V5
V3
V2
V4
V5
V3
V2
V5
V3
V2
V5V5
输出 V1输出 V6 输出 V4
输出 V3输出 V2输出 V5
V2
V6
V4
V3
V1
V5
V2
V6
V4
V3
V5
V2
V6
V3V5
输出 V1 输出 V3 不能输出有回路的有向图不存在拓扑排序。
7.5.2 关键路径
AOE网 （ Activity On Edge）：
是一个带权的有向无环图，其中以顶点表示事件，弧表示活动，权表示活动持续的时间。
当 AOE网用来估算工程的完成时间时，只有一个开始点
（入度为 0,称为 源点 ） 和一个完成点（出度为 0，称为 汇点 ）
V2
V1
V6
V3
V4
V5
V7
V8
V9
AOE网研究的问题：
（ 1） 完成整项工程至少需要多少时间；
（ 2） 哪些活动是影响工程进度的关键。
在 AOE网中，部分活动可并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径长度。路径长度最长的路径称为 关键路径 （ Critical Path）。
(顶点）事件 vi的最早发生时间 ve(i)：
从开始点到 vi的最长路径长度 。（ ve(v1)=0）
既表示事件 vi的最早发生时间，也表示所有以 vi为尾的弧所表示的 活动 ak的最早发生时间 e(k)。 (如下例的 a7,a8)
V2
V1 V3
V4
V5
仅有一个前驱顶点,
ve(v2)=ve(v1)+6=0+6=6
ve(v3)=ve(v1)+4=0+6=4
ve(v4)=ve(v1)+6=0+5=5
有多个前驱顶点,
ve(v5)=max{ve(前驱顶点 )+
前驱活动时间 }
=max{6+1,4+1,5+5}=10
完成点（汇点）的 ve(vn)为工程完成所需要的时间。
不推迟整个工程完成的前提下,(顶点）事件 vi允许的最迟开始时间 vl(i),完成点（汇点） vn的 的最早发生时间 ve(n)
减去 vk到 vn的最长路径长度。
（ vn的 的最早发生时间 ve(n)等于 最迟开始时间 vl(n)）。
V6
V5
V7
V8
V9
仅有一个后继顶点,
假定工程 18天完成 (ve(v9)=18)
则,vl(v9)=18
vl(v7)= vl(v9)-2=16
vl(v8)= vl(v9)-4=14
vl(v6)= vl(v8)-4=10
有多个后继顶点,
vl(v5)= min{vl(v7)-9,vl(v8)-4}=min{7,10}=7
l(i)-e(i)意味着完成活动 ai的 时间余量 。
关键活动,l(i)=e(i)的活动。
确定了顶点 vi的最迟开始时间后，确定所有以 vi为弧头的 活动 ak的最迟开始时间 l(k),表示在不推迟整个工程完成的前提下，活动 ak最迟必须开始的时间。
l(ak)=vl(Vi)-活动 ak的持续时间
V6
V5
V7
V8
V9
vl(v7)= vl(v9)-2=16
vl(v8)= vl(v9)-4=14
vl(v9)=18
l(a11)=Vl(v9)-4=18-4=14
l(a10)=Vl(v9)-2=18-2=16
l(a9)=Vl(v8)-4=14-4=10
l(a7)=Vl(v7)-9=16-9=7
关键路径算法步骤：
（ 1）从开始点 v1出发，令 ve(1)=0,按拓朴排序序列求其它各顶点的最早发生时间
Ve(k)=max{ve(j)+dut(<j,k>)}
(vj为以顶点 vk为弧头的所有弧的弧尾对应的顶点集合 )
V2
V1
V6
V3
V4
V5
V7
V8
V9
顶点 ve(i) vl(i)
v1 0
v2 6
v3 4
v4 5
v5 7,5
v6 7
v7 16
v8 14,11
v9 18,18
该表次序为一拓朴排序序列关键路径算法步骤：
（ 2）从完成点 vn出发，令 vl(n)=ve(n),按 li逆拓朴排序序列求其它各顶点的最迟发生时间
Vl(j)=min{vl(k)-dut(<j,k>)}
(vk为以顶点 vj为弧尾的所有弧的弧头对应的顶点集合 )
V2
V1
V6
V3
V4
V5
V7
V8
V9
顶点 ve(i) vl(i)
v1 0 0,2,3
v2 6 6
v3 4 6
v4 5 8
v5 7 7,7
v6 7 10
v7 16 16
v8 14 14
v9 18 18
关键路径算法步骤：
（ 3）求每一项活动 ai(vj,vk):
e(i)=ve(j)
l(i)=vl(k)-dut(ai)
活动 e(i) l(i) l(i)-e(i)
a1 0 0 0
a2 0 2 2
a3 0 3 3
a4 6 6 0
a5 4 6 2
a6 5 8 3
a7 7 7 0
a8 7 7 0
a9 7 10 3
a10 16 16 0
a11 14 14 0
V2
V1
V6
V3
V4
V5
V7
V8
V9
顶点
ve(i) vl(i)
v1 0 0
v2 6 6
v3 4 6
v4 5 8
v5 7 7
v6 7 10
v7 16 16
v8 14 14
v9 18 18
V2
V1
V6
V3
V4
V5
V7
V8
V9
关键活动,选取 e(i)=l(i)的活动。
关键路径,
（ 1） v1? v2? v5? v7? v9
（ 2） v1? v2? v5? v8? v9
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
始点 终点 最短路径 路径长度
v0 v1 无
v2 v0,v2 10
v3 v0,v4,v3 50
v4 v0,v4 30
v5 v0,v4,v3,v5 60
20
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
Dijkstra的路径长度递增法：
∞ 10 ∞ 30 100
V0 V0 V0 V0 V0
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
初始化
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 ∞ 30 100
V0 V0 V2 V0 V0
+10
∞ 10 60 30 100
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
比较大小
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 60 30 100
V0 V0 V4 V0 V4
+30
∞ 10 50 30 90
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
比较大小
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 50 30 90
V0 V0 V4 V0 V3
+50
∞ 10 50 30 60
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
比较大小
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 50 30 60
+60
∞ 10 50 30 60
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
V0 V0 V4 V0 V3前驱顶点：
最短路径：
比较大小
1 2 3 4 5
∞ 10 50 30 60
V0 V0 V4 V0 V3前驱顶点：
V1,无路径
V2,10
最短路径：
1 2 3 4 5
V3,50
V4,30
V5,60
V1 V2 V3 V4 V5 前驱序列,
V2?V0 V0?V2
V3?V4?V0 V0?V4?V3
V4?V0 V0?V4
V5?V3?V4?V0 V0?V4?V3?V5
7.6.1 每一对顶点之间的最短路径算法 1（ Dijkstra算法）：
以每一个顶点为源点，重复执行 Dijkstra算法 n次，即可求出每一对顶点之间的最短路径。
算法 2（ Floyd算法）：
算法思想：
假设求 Vi到 Vj的最短路径，如果从 Vi到 Vj有弧，则存在一条长度为 arcs[i][j]的路径，该路径不一定是最短路径，
尚需进行 n次试探。
首先考虑 (Vi,V0,Vj)是否存在（即判断 (Vi,V0)和 ( V0,Vj)
是否存在 )，如果存在，比较 (Vi,Vj)和 (Vi,V0)+( V0,Vj)，
取长度较短的为 从 Vi到 Vj的中间顶点序号不大于 0的最短路径 。
VjVi
V0
60
20 10
VjVi
V0
30
20 50
再考虑路径上再增加一个顶点 V1,如果考虑 (Vi,… V1)和
(V1,…,Vj),(Vi,… V1)和 (V1,…,Vj)都是 中间顶点序号不大于 0的最短路径。 (Vi,… V1,…,Vj)可能是 从 Vi到 Vj的中间顶点序号不大于 1的最短路径 。
比较 Vi到 Vj的中间顶点序号不大于 0的最短路径 和
(Vi,… V1)+(V1,…,Vj),取长度较短的为 从 Vi到 Vj的中间顶点序号不大于 1的最短路径 。
以此类推，经过 n次比较后，求得 Vi到 Vj的最短路径。
VjVi
V1
70
20 20
算法 C程序：
for(k=0;k<N;k++) //依次选定中间顶点 V0,V1,… Vn-1
for(i=0; i<N;i++) //i,j配合处理所有顶点 Vi,Vj
for(j=0; j<N;j++)
if (cost[i][j]>cost[i][k]+cost[k][j])
cost[i][j]=cost[i][k]+cost[k][j]; //取较短路径假定邻接矩阵为 cost[N][N]
Floyd算法的基本思想是递推产生一个矩阵序列,
D(-1),D(0),D(1),…,.,D(k),…,D(n-1)
D(-1) [i][j] = cost[i][j]
D(k) [i][j] = Min{D(k-1) [i][j],D(k-1) [i][k]+ D(k-1) [k][j]}
0≤k≤n -1
华中科技大学计算机学院 (9)数据结构
7.5 有向无环图及其应用一个无环的有向图称为 有向无环图 （ directed acycline graph),
简称 DAG图。
DA
C
EB
F
B
A
D
E
F
C
6
8
5
7
4 6
2
C
A
D
E
B
F
图 1 图 2 图 3（非 DAG）
7.5.1 拓扑排序
AOV网 （ Activity On Vertex network）：
以顶点表示活动，弧表示活动之间的优先关系的 DAG图。
课程编号 课程名称 先决条件
C1 程序设计基础 无
C2 离散数学 C1
C3 数据结构 C1,C2
C4 汇编语言 C1
C5 语言的设计和分析 C3,C4
C6 计算机原理 C11
C7 编译原理 C5,C3
C8 操作系统 C3,C6
C9 高等数学 无
C10 线性代数 C9
C11 普通物理 C9
C12 数值分析 C9,C10,C1
计算机软件专业课程
C1
C2
C4 C5
C3 C7
C12
C9 C
10
C11
C6
C8
表示课程间关系的有向图拓扑排序,是有向图的全部顶点的一个线性序列，该序列保持了原有向图中各顶点间的相对次序。例：
（ C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8)
（ C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)
拓扑排序算法思想：重复下列操作，直到所有顶点输出完。
（ 1） 在有向图中选一个没有前驱的顶点输出 (选择入度为 0的顶点 )；
（ 2）从图中删除该顶点和所有以它为尾的弧 (修改其它顶点入度 ) 。
V1 V2
V4
V6 V5
V3
V1 V2
V4
V5
V3
V2
V4
V5
V3
V2
V5
V3
V2
V5V5
输出 V1输出 V6 输出 V4
输出 V3输出 V2输出 V5
V2
V6
V4
V3
V1
V5
V2
V6
V4
V3
V5
V2
V6
V3V5
输出 V1 输出 V3 不能输出有回路的有向图不存在拓扑排序。
7.5.2 关键路径
AOE网 （ Activity On Edge）：
是一个带权的有向无环图，其中以顶点表示事件，弧表示活动，权表示活动持续的时间。
当 AOE网用来估算工程的完成时间时，只有一个开始点
（入度为 0,称为 源点 ） 和一个完成点（出度为 0，称为 汇点 ）
V2
V1
V6
V3
V4
V5
V7
V8
V9
AOE网研究的问题：
（ 1） 完成整项工程至少需要多少时间；
（ 2） 哪些活动是影响工程进度的关键。
在 AOE网中，部分活动可并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径长度。路径长度最长的路径称为 关键路径 （ Critical Path）。
(顶点）事件 vi的最早发生时间 ve(i)：
从开始点到 vi的最长路径长度 。（ ve(v1)=0）
既表示事件 vi的最早发生时间，也表示所有以 vi为尾的弧所表示的 活动 ak的最早发生时间 e(k)。 (如下例的 a7,a8)
V2
V1 V3
V4
V5
仅有一个前驱顶点,
ve(v2)=ve(v1)+6=0+6=6
ve(v3)=ve(v1)+4=0+6=4
ve(v4)=ve(v1)+6=0+5=5
有多个前驱顶点,
ve(v5)=max{ve(前驱顶点 )+
前驱活动时间 }
=max{6+1,4+1,5+5}=10
完成点（汇点）的 ve(vn)为工程完成所需要的时间。
不推迟整个工程完成的前提下,(顶点）事件 vi允许的最迟开始时间 vl(i),完成点（汇点） vn的 的最早发生时间 ve(n)
减去 vk到 vn的最长路径长度。
（ vn的 的最早发生时间 ve(n)等于 最迟开始时间 vl(n)）。
V6
V5
V7
V8
V9
仅有一个后继顶点,
假定工程 18天完成 (ve(v9)=18)
则,vl(v9)=18
vl(v7)= vl(v9)-2=16
vl(v8)= vl(v9)-4=14
vl(v6)= vl(v8)-4=10
有多个后继顶点,
vl(v5)= min{vl(v7)-9,vl(v8)-4}=min{7,10}=7
l(i)-e(i)意味着完成活动 ai的 时间余量 。
关键活动,l(i)=e(i)的活动。
确定了顶点 vi的最迟开始时间后，确定所有以 vi为弧头的 活动 ak的最迟开始时间 l(k),表示在不推迟整个工程完成的前提下，活动 ak最迟必须开始的时间。
l(ak)=vl(Vi)-活动 ak的持续时间
V6
V5
V7
V8
V9
vl(v7)= vl(v9)-2=16
vl(v8)= vl(v9)-4=14
vl(v9)=18
l(a11)=Vl(v9)-4=18-4=14
l(a10)=Vl(v9)-2=18-2=16
l(a9)=Vl(v8)-4=14-4=10
l(a7)=Vl(v7)-9=16-9=7
关键路径算法步骤：
（ 1）从开始点 v1出发，令 ve(1)=0,按拓朴排序序列求其它各顶点的最早发生时间
Ve(k)=max{ve(j)+dut(<j,k>)}
(vj为以顶点 vk为弧头的所有弧的弧尾对应的顶点集合 )
V2
V1
V6
V3
V4
V5
V7
V8
V9
顶点 ve(i) vl(i)
v1 0
v2 6
v3 4
v4 5
v5 7,5
v6 7
v7 16
v8 14,11
v9 18,18
该表次序为一拓朴排序序列关键路径算法步骤：
（ 2）从完成点 vn出发，令 vl(n)=ve(n),按 li逆拓朴排序序列求其它各顶点的最迟发生时间
Vl(j)=min{vl(k)-dut(<j,k>)}
(vk为以顶点 vj为弧尾的所有弧的弧头对应的顶点集合 )
V2
V1
V6
V3
V4
V5
V7
V8
V9
顶点 ve(i) vl(i)
v1 0 0,2,3
v2 6 6
v3 4 6
v4 5 8
v5 7 7,7
v6 7 10
v7 16 16
v8 14 14
v9 18 18
关键路径算法步骤：
（ 3）求每一项活动 ai(vj,vk):
e(i)=ve(j)
l(i)=vl(k)-dut(ai)
活动 e(i) l(i) l(i)-e(i)
a1 0 0 0
a2 0 2 2
a3 0 3 3
a4 6 6 0
a5 4 6 2
a6 5 8 3
a7 7 7 0
a8 7 7 0
a9 7 10 3
a10 16 16 0
a11 14 14 0
V2
V1
V6
V3
V4
V5
V7
V8
V9
顶点
ve(i) vl(i)
v1 0 0
v2 6 6
v3 4 6
v4 5 8
v5 7 7
v6 7 10
v7 16 16
v8 14 14
v9 18 18
V2
V1
V6
V3
V4
V5
V7
V8
V9
关键活动,选取 e(i)=l(i)的活动。
关键路径,
（ 1） v1? v2? v5? v7? v9
（ 2） v1? v2? v5? v8? v9
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
始点 终点 最短路径 路径长度
v0 v1 无
v2 v0,v2 10
v3 v0,v4,v3 50
v4 v0,v4 30
v5 v0,v4,v3,v5 60
20
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
Dijkstra的路径长度递增法：
∞ 10 ∞ 30 100
V0 V0 V0 V0 V0
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
初始化
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 ∞ 30 100
V0 V0 V2 V0 V0
+10
∞ 10 60 30 100
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
比较大小
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 60 30 100
V0 V0 V4 V0 V4
+30
∞ 10 50 30 90
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
比较大小
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 50 30 90
V0 V0 V4 V0 V3
+50
∞ 10 50 30 60
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
前驱顶点：
最短路径：
比较大小
1 2 3 4 5
V2
V0
V3V1
V5
V4
5
30
50
10
10
60
∞ 10 50 30 60
+60
∞ 10 50 30 60
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
0 1 2 3 4 5
0
1
2
3
4
5
V0 V0 V4 V0 V3前驱顶点：
最短路径：
比较大小
1 2 3 4 5
∞ 10 50 30 60
V0 V0 V4 V0 V3前驱顶点：
V1,无路径
V2,10
最短路径：
1 2 3 4 5
V3,50
V4,30
V5,60
V1 V2 V3 V4 V5 前驱序列,
V2?V0 V0?V2
V3?V4?V0 V0?V4?V3
V4?V0 V0?V4
V5?V3?V4?V0 V0?V4?V3?V5
7.6.1 每一对顶点之间的最短路径算法 1（ Dijkstra算法）：
以每一个顶点为源点，重复执行 Dijkstra算法 n次，即可求出每一对顶点之间的最短路径。
算法 2（ Floyd算法）：
算法思想：
假设求 Vi到 Vj的最短路径，如果从 Vi到 Vj有弧，则存在一条长度为 arcs[i][j]的路径，该路径不一定是最短路径，
尚需进行 n次试探。
首先考虑 (Vi,V0,Vj)是否存在（即判断 (Vi,V0)和 ( V0,Vj)
是否存在 )，如果存在，比较 (Vi,Vj)和 (Vi,V0)+( V0,Vj)，
取长度较短的为 从 Vi到 Vj的中间顶点序号不大于 0的最短路径 。
VjVi
V0
60
20 10
VjVi
V0
30
20 50
再考虑路径上再增加一个顶点 V1,如果考虑 (Vi,… V1)和
(V1,…,Vj),(Vi,… V1)和 (V1,…,Vj)都是 中间顶点序号不大于 0的最短路径。 (Vi,… V1,…,Vj)可能是 从 Vi到 Vj的中间顶点序号不大于 1的最短路径 。
比较 Vi到 Vj的中间顶点序号不大于 0的最短路径 和
(Vi,… V1)+(V1,…,Vj),取长度较短的为 从 Vi到 Vj的中间顶点序号不大于 1的最短路径 。
以此类推，经过 n次比较后，求得 Vi到 Vj的最短路径。
VjVi
V1
70
20 20
算法 C程序：
for(k=0;k<N;k++) //依次选定中间顶点 V0,V1,… Vn-1
for(i=0; i<N;i++) //i,j配合处理所有顶点 Vi,Vj
for(j=0; j<N;j++)
if (cost[i][j]>cost[i][k]+cost[k][j])
cost[i][j]=cost[i][k]+cost[k][j]; //取较短路径假定邻接矩阵为 cost[N][N]
Floyd算法的基本思想是递推产生一个矩阵序列,
D(-1),D(0),D(1),…,.,D(k),…,D(n-1)
D(-1) [i][j] = cost[i][j]
D(k) [i][j] = Min{D(k-1) [i][j],D(k-1) [i][k]+ D(k-1) [k][j]}
0≤k≤n -1
