1
§ 6.6 拓扑排序
? 目的
– 根据结点间的关系求得结点的一个线性排列。
? 在有关工程进度 /次序规划之类问题中，有着大量应用。
– 一般的大型工程，都可以划分为多个工序 /步骤 /子工程，这
些工序有的可独立进行，但大多数和其他工序关联，即某工
序的进行，要等到其他一些工序的完成才能开始。这类问题
都可归结到拓扑排序。
2
§ 6.6.1 拓扑序列与 AOV网
? 对有向图 G,若它的一个结点序列
LS,v1,v2,...,vn
满足这样的条件,<vi,vj>是 G的边时，在 LS中 vi位于 vj之
前（即 i<j），否则在 LS中 vi与 vj的前后次序任意，则称 LS为
图 G的一个 拓扑序列,求拓扑序列的操作称为 拓扑排序
（ Topological Sorting）。
某一图的拓扑序
列可能不唯一
3
§ 6.6.1 拓扑序列与 AOV网
? 拓扑排序主要用在一类称为 AOV网 （ Activity on Vertex
networks） 的有向图中 。
? AOV网是给有向图的结点与边赋予一定的语义的图, 具
体地：
– 结点 ──代表活动 。 如工程中的工序 /子任务, 状态等
– 边 ──代表活动之间的进行次序 。 边 <i,j>表示活动 i先于 j进行 。
? AOV网常用来表达流程图, 如一个工程中各子任务间的
流程图, 产品生产加工流程图, 程序流程图, 信息 （ 数据 ）
流程图, 活动安排流程图等
4
§ 6.6.1 拓扑序列与 AOV网
? 学生的选课次序就是一个 AOV网应用问题 。 例如, 假定某计算机专
业的主要课程如表 6-2所示, 则对应的 AOV网如图 6-1所示 。
10
1 2 3
9 6 4
5
7
8
11
图 - 对应的 AOV网
10 人工智能原理 1,2,3
7,9
表 6-2 课程进行关系
课程编号 课程名称 先行课
1 高等数学 -
2 离散数学 -
3 高级语言 -
4 数据结构 3,2
5 操作系统 4,6
6 计算机组成原理 2
7 数据库原理 5
8 编译原理 4,7
9 计算机网络 5,1
11 软件工程
5
§ 6.6.1 拓扑序列与 AOV网
? 图 6-1可有多个拓扑序列, 下面给出了它的两个
不同的拓扑序列：
1 2 3 4 6 5 9 7 8 11
1 2 3 4 6 5 7 9 8 11
? 如果采用串行修课方式, 则可完全按拓扑序列进
行, 但往往是一段时间内需同时修多门课, 这就需
识别出哪些课可同时修, 这是一个 识别可并行成份
的问题 。 例如, 在 图 6-1中, 可并行的课程有
(1,2,3)→ (4,6,10)→ (5)→ (9,7)→ (8,11)等几组 。
10
1 2 3
9 6 4
5
7
8
11
图 - 对应的 AOV网
6
§ 6.6.2 拓扑排序算法与实现
(一）基本方法
? 进行拓扑排序的基本方法是简单而直观的, 其包含下列几个步骤：
[1] 从有向图中找一个没有前趋的结点 v,若 v不存在, 则表明不可进
行拓扑排序 （ 图中有环路 ）, 结束 （ 不完全成功 ） ；
[2] 将 v输出；
[3] 将 v从图中删除, 同时删除关联于 v的所有的边
[4] 若图中全部结点均已输出，则结束（成功），否则转 [1]继续进行。
7
§ 6.6.2 拓扑排序算法与实现
(一）基本方法
? 通过对此方法做适当扩充, 就可在求拓扑序列的过程中
标识出可并行活动 （ 结点 ） 。
? 具体做法是, 初始时将所有无前趋结点标为一组可并行
结点 。 然后, 每次执行步骤 [3]后, 将新产生的无前趋结点
标为新的一组可并行结点 。 为了将同组并行结点连续排列,
在步骤 [1]中应优先选取并行组号与上次选择结点的并行组
号相同的结点 （ 若有的话 ）
8
§ 6.6.2 拓扑排序算法与实现
(二）数据结构的选取
? 邻接表的图结点的定义修改为：
template <class TElem>
struct TGrphNode
{
longnodeIdx; //结点编号
TElem nodeInfo; //结点信息
longinDegree; //结点的入度
TGrphEdge * firstOutEdge; //第一条出边的指针
};
9
§ 6.6.2 拓扑排序算法与实现
(二）数据结构的选取
? 而图边的定义仍为：
template <class TEdgeInfo>
struct TGrphEdge
{
longedgeEndIdx; //边终点编号
TEdgeInfo edgeInfo; //边信息
TGrphEdge *next; //链指针
};
10
§ 6.6.2 拓扑排序算法与实现
(二）算法实现
for (每个结点 v)
if (v入度为 0) v进栈 ;
while (栈不空 )
{
从栈中弹出一个元素送 v;
输出 v;
求出 v的第 1个直接可达邻接点 w;
while (w存在 )
{
将 w的入度域减 1;
if (w的入度域为 0) w进栈 ;
求出 v的下个直接可达邻接点 w;
} //while
} //while
11
(二）算法实现
下面是具体的 C++程序 。
longTopoSort(TGrphNode *g,long n,long *resu)
{ //对图 g求拓朴序列, 存入 sesu(结点编号 ),n为图结点数目 。
//返回所求得的结点数 。 若返回值小于 n,则表示未能完全拓扑排序 。
long*s,top,k,i;
TGrphEdge *p;
s = new long[n+1];
top=0;
k=0;
for (i=0; i<=n; i++)
if (g[i].inDegree == 0) {top++; s[top]=i; }
12
(二）算法实现
while (top>0)
{
i=s[top]; top--;
resu[k]=i; k++;
p=g[i].firstOutEdge;
while ( p!=NULL )
{
i=p->edgeEndIdx;
g[i].inDegree--;
if (g[i].inDegree==0) { top++; s[top]=i;}
p=p->next;
} //while (p!=…
}
delete [] s;
return k;
}
时间复杂度为 O(n+m)
13
§ 6.7 AOE网与关键路径
? 求关键路径是对边加权的有向图的一种操作。
? AOE网与 AOV网类似，也是一种被赋予了抽象语义的有
向图，是许多实际问题的模型。
14
§ 6.7.1 AOE网与关键路径的概念
(一） AOE网
? 如果将有向图的结点与边按下列所述赋予抽象意义,
则该种有向图就称为 AOE网 (Activity On Edge network)
– 边 （ 弧 ）,代表活动 （ 操作 ） ；
– 边权,代表活动的持续时间 。 记边 ak=<i,j>的权为 len(ak)或
len(i,j)；
– 结点,代表事件 （ 状态 ） 。 它表示它的各入边代表的活动均已完
成, 而它的出边代表的活动可以开始 。
? AOE网中没有入边的结点称为始点, 没有出边的结点
称为终点 。
15
AOE一般用来描述工程进度，结点表示工程进展中的状态，边表示子任务。图
6-1就是一个 AOE网，它可以看作是一个具有 11项子任务和 9个状态的假想工程的
进度图
a7=9
a9=4a6=2
a5=1a2=4
a1=6 a8=7
a3=5
a4=1 a10=2
a11=4v1
v2
v3
v4
v5
v6
v7
v8
v9
事件 含义
v1 开工
v2 活动 a1完成, 活动 a4可以开始
v3 活动 a2完成, 活动 a5可以开始
v4 活动 a3完成, 活动 a6可以开始
v5 活动 a4与 a5完成, 活动 a7和 a8可开始
,
v6 活动 a6完成, 活动 a9可以开始
v7 活动 a7完成, 活动 a10可以开始
v8 活动 a8完成, 活动 a11可以开始
v9 活动 a10和 a11完成, 整个工程完成
图 - AOE网举例
16
§ 6.7.1 AOE网与关键路径的概念
(二） AOE网的操作
? 针对 AOE网的操作一般有下列几种,
– 关键路径 CPM(Critical Path Method)。 这种操作最早用于
维修与建筑行业中工期进度估算。
– 性能估计与复审 PERT(Performance Evaluation and Review
Technique)：该项操作最初是为了研制北极星式导弹系统而引
入的
– 资源分配与多工程调度 RAMPS(Resource Allocation and Multi-
Project Scheduling)
17
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
? 下面的阐述中，设 AOE网的起点为 v0终点为 vn
1,关键路径
? AOE网中, 从事件 i到 j的路径中, 加权长度最大者称为
i到 j的 关键路径 （ Critical Path） 。 记为 cp(i,j).特别
地, 始点 0到终点 n的关键路径 cp(0,n)是整个 AOE的关键
路径 。
? 显然，关键路径决定着 AOE网的工期，关键路径的长
度就是 AOE网代表的工程所需的最小工期。
18
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
2,事件最早 /晚发生时间
事件 vi的最早发生时间 ve(i)定义为：从始点到 vi的最
长 （ 加权 ） 路径长度, 即 cp(0,i)
事件 vi的最晚发生时间 vl(i)定义为：在不拖延整个工
期的条件下, vi的可能的最晚发生时间 。 即
vl(i) = ve(n) - cp(i,n)
19
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
3,活动最早 /晚开始时间
活动 ak=<vi,vj>的 最早开始时间 e(k)：等于事件 vi的最早发生时
间, 即
e(k) = ve(i) = cp(0,i)
活动 ak=<vi,vj>的 最晚开始时间 l(k)定义为：在不拖延整个工期
的条件下, 该活动的允许的最迟开始时间, 即
l(k) = vl(j) – len(i,j)
这里, vl(j)是事件 j的允许的最晚发生时间, len(i,j)是 ak的权 。
活动 ak的 最大可利用时间,定义为 l(k)-e(k)
20
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
4,关键活动
若活动 ak的最大可利用时间等于 0（ 即 (l(k)=e(k)）,
则称 ak 为 关键活动, 否则为 非关键活动 。
显然, 关键活动的延期, 会使整个工程延期 。 但非关
键活动不然, 只要它的延期量不超过它的最大可利用时
间, 就不会影响整个工期 。
21
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
? 关键路径的概念, 也可以用这里的关键活动定义, 即
有下面的：
定理 6-2 某路径为关键路径的充分必要条件是, 它上
的各活动均为关键活动 。
22
§ 6.7.2 关键路径的识别
(三） 关键路径的若干基本概念
? 进行关键路径分析, 目的是寻找合理的资源调配方案
（ 这里的资源是指能使活动进行的人力或物力 ）, 使
AOE网代表的工程尽快完成 。
? 只有缩短关键路径上的活动 （ 关键活动 ） 才有可能缩
短整个工期
? 识别关键路径的公共点就变得很重要
23
§ 6.7.2 关键路径的识别
(一） 基本算法
? 设图 G=(V,E)是个 AOE网, 结点编号为 1,2,...,n,其
中结点 1与 n 分别为始点和终点, ak=<i,j>∈ E是 G的一个
活动 。
? 根据前面给出的定义, 可推出活动的最早及最晚发生
时间的计算方法：
e(k) = ve(i)
l(k) = ve(j) - len(i,j)
24
§ 6.7.2 关键路径的识别
(一） 基本算法
? 结点的最早发生时间的计算, 需按拓扑次序递推
ve(1) = 0
ve(j) = MAX{ ve(i)+len(i,j) } 对所有 <i,j> ∈ E的 i
25
§ 6.7.2 关键路径的识别
(一） 基本算法
? 结点的最晚发生时间的计算, 需按逆拓扑次序递推：
vl(n) = ve(n)
vl(i) = MIN{vl(j) - len(i,j)} 对所有 <i,j>∈ E的 j
…
j
…
i i …
…
j
图 - 计算 ve和 vl的示意
26
§ 6.7.2 关键路径的识别
(一） 基本算法
? 这种计算方法, 依赖于拓扑排序
? 计算 ve( j) 前, 应已求得 j 的各前趋结点的 ve值, 而计算 vl(i)
前, 应已求得 i的各后继结点的 vl值 。
? ve的计算可在拓扑排序过程中进行, 即在每输出一个结点 i后, 在
删除 i的每个出边 <i,j>（ 即入度减 1） 的同时, 执行
if ( ve[i]+len(i,j)) > ve[j] )
ve[j] = ve[i] + len(i,j)
27
§ 6.7.2 关键路径的识别
(一） 基本算法
? 通过逆方向使用拓扑序列即可递推出各 vl的值, 假定拓扑序列是 topoSeq，
则 vl 的值的求法为 （ 结点编号为 1~n） 。
for (k=1; k<=n; k++) vl[k] = ve[n]; //初始化
for ( k=n; k>=1; k--)
{
i=topoSeq[k];
j=（ i的第 1个直接射出点 ） ;
while (j存在 )
{
if (vl[j]-len(i,j)<vl[i])
vl[i]=vl[j]-len(i,j);
j = （ i的下一个直接射出点 ） ;
}
}
28
§ 6.8 最短路径
? 路径问题是有向图及无向图中的另一基本问题, 它涉及
下列两点：
– 对图中任两结点 u与 v,它们之间有路径吗？
– 若 u到 v之间有不止一条路径, 那么, 哪一条是最短路径 （ 代
价最小路径 ）？
? 对路径问题, 有两个著名算法,
– Dijkstra 单源最短路径算法
– Floyd每对结点最短路径算法 。
§ 6.8.1 路径问题
29
(一）基本方法
? Dijkstra单源最短路径算法是求图中任一结点到其余各结
点的最短路径 （ 路径表示与长度 ） 。
§ 6.8.2 Dijkstra单源最短路径算法
30
(二）基本策略
? 设图共有 n个不同的结点, 则从某一点出发达到其他各点
的最短路径有 (n-1) 条
? Dijkstra的基本策略是, 按长度不减次序构造这 (n-1)条最
短路径, 即先求出长度最小的一条最短路径, 然后求出长
度第二小的最短路径, 最后求出长度最大的最短路径
§ 6.8.2 Dijkstra单源最短路径算法
31
例如，对图 6-1所示有向图，若求结点 1到其它各结点的
最短路径，则求得的次序为,1-2,1-3,1-5,1-6,1-4,1-7.
3010 100
20
20
10 40
10 20
255
1
2 3
5 6
7
4
图 - 有向图的单源最短路径
(a) 一个有向图 (b) 有向图 (a)中 1到其他各点的最短路径
始点 终点 最短路径 最短路径长
度
长 度 次
序
1 2 (1,2) 10 1
3 (1,3) 30 2
4 (1,2,5,6,4) 60 5
5 (1,2,5) 30 3
6 (1,2,5,6) 40 4
7 无 ∞ 6
32
(二）基本策略
? 另外，设立两种数据结构：
1.集合 s：存放当前已找出的各最短路径的终点。即若 v∈ s，则表示
始点到 v的 最短路径已被求出
2.路径数组 dist：它的含意为：
– 若 i ∈ s，则 dis[i]等于始点 v0到 i的距离
– 若 i不属于 s，则 dis[i]等于始点 v0到 i的中间只经过 s中元素，且长度
最小的路径的长度（若无此种路径，则视长度为 ∞ ）
? 这两个数据结构是生成最短路径的关键。其中 dist充当候选集
§ 6.8.2 Dijkstra单源最短路径算法
33
? Dijkstra单源最短路径算法及其正确性均基于下列几点事实 。
(1),如果下一条 （ 即长度递增序列中的下一条 ） 最短路径的终点
是 u,则这条路径是从起点 v0开始, 中间只经过 s中结点, 而最后到达 u
的路径 。
(2),从 v0出发的长度最小的最短路径, 必为 v0的出边中权值最小者 。
(3),下一条最短路径的终点 u,必定是尚未进入 s中的那些结点
u1,...,um对应的 dist[u1],...,dist[um]中值最小者所对应的那个 uk，
即 u必满足：
dist[u]=min{dist[w]}，其中 w∈ s。
§ 6.8.3 Dijkstra算法的正确性
34
（一）算法实现基本框架
Dijkstra(g,n,v0,dist)
{ //对图 g求从源点 v0到其余各点的最短路径，结果存于 dist中。 n为图中结点个数
根据 g与 v0初始化 dist与 s;
while (未完 )
{
求满足 dist[u]=MIN{dist[w]}的 u，这里 w∈ s;
将 u加入到集合 s中 ;
调整候选集 dist
}
} //Dijkstra
§ 6.8.4 Dijkstra算法实现
35
（一）算法实现基本框架
? 根据 s与 dist的定义，在初始时，令 s只含源点 v0，而对每个 v≠ v0，置
dist[v]为 v0到 v的边的权值（ v0到 v无边时置为 ∞ ）
? 将新造出的结点 u加入 s后，某些结点的 dist值可能变得不满足 dist的定
义，故应调整 dist，使它重新满足定义
? 调整的方法为
for (每个不在 s中的 w)
if (dist[u]+cost(u,w) <dist[w] )
dist[w]=dist[u]+cost(u,w);
§ 6.8.4 Dijkstra算法实现
36
§ 6.8.4 Dijkstra算法实现
w
w
uv0
图 - Dijkstra算法调整候选集
37
（二）数据结构设计
? (1) 图：输入量，为待求最短路径的图。根据 Dijkstra算法的特点，
采用邻接矩阵为好。具体定义如下：
边 <i,j>的权值,若 i到 j有边
g[i][j] =
∞,若 i到 j无边
§ 6.8.4 Dijkstra算法实现
38
（二）数据结构设计
? (2) 路径与候选集 dist
? 为了能同时得到最短路径的构成（即路径上的结点序列），这里对
dist作适当的扩充，使得能从它得到各最短路径的结点序列
? 源点 v0到任一点 u 的最短路径构成形式为下列两种情形之一：
(v0,u) 或
(v0,u1,...,uk,u) (k≥ 1)
其中，路径 (v0,u1,...,um)为 v0到 um的最短路径 (1≤ m≤ k)
? 亦即，最短路径上结点序列的任一最左子序列均为某结点的最短路径
结点序列
? 我们称 (v0,u1,...,uk)或 (v0)为 v0到 u 的最短路径的 前趋路径
§ 6.8.4 Dijkstra算法实现
39
（二）数据结构设计
? 最短路径的此性质启发我们，对任一结点 u，只需设立它的前趋路径
的指示器就可推出源点到它的最短路径结点序列
? 据此，我们为 dist 的元素增设一个 pre字段，令它存放对应结点的前趋
路径的终点编号，即 dist[i].pre的值为源点到 i的最短路径的前趋路径的终
点编号
? 该字段相当于一个链指针，顺着它搜索的结果是最短路径的结点的逆
序
§ 6.8.4 Dijkstra算法实现
40
（二）数据结构设计
§ 6.8.4 Dijkstra算法实现
3010 100
20
20
10 40
10 20
255
1
2 3
5 6
7
4 结点 i 1 2 3 4 5 6 7
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 0
41
（二）数据结构设计
(3) 集合 s
集合 s为中间量，用一维数组表示，其元素含意为：
若 i！ ∈ s,s[i]=0
若 i∈ s,s[i]=1
? 如果图 g邻接矩阵的对角线元素不使用，则也可用对角线
元素 g[i][i]充当 s[i]。
§ 6.8.4 Dijkstra算法实现
42
（三）算法程序
struct TDijkPath
{
float len;
long pre;
};
§ 6.8.4 Dijkstra算法实现
43
§ 6.8.4 Dijkstra算法实现
long DijkstraPath(TGrphEdge **g,long n,long v0,TDijkPath *dist)
{
char *s;
long i,j,k;
float minW;
s = new char[n+1];
for (i=1; i<n; i++) //初始化
{
s[i] = 0;
dist[i].len = g[v0][i];
if (dist[i].len !=无边标志 ) dist[i].pre = v0;
else dist[i].pre = -1; //表示不存在
} //for
s[v0] = 1; //将源点 v0放入 s
44
§ 6.8.4 Dijkstra算法实现
for (i=1; i<n; i++) //每次求出一条最短路径
{
k=1;
for (j=k+1; j<n; j++) //求下条最短路径
if (s[j] )
if (dist[j].len < dist[k].len) k=j;
s[k] = 1; //将 k加入 s
45
§ 6.8.4 Dijkstra算法实现
for (j=1; j<n; j++) //调整候选集
if (!s[j])
if (dist[k]+g[k][j] < dist[j] )
{
dist[j] = dist[k]+g[k][j];
dist[j].pre = k; //将 k的前驱路径改为 k
}
}//for (i=1; …)
detele [] s;
return n;
}; // DijkstraPath
46
§ 6.8.4 Dijkstra算法实现
for (j=1; j<n; j++) //调整候选集
if (!s[j])
if (dist[k]+g[k][j] < dist[j] )
{
dist[j] = dist[k]+g[k][j];
dist[j].pre = k; //将 k的前驱路径改为 k
}
}//for (i=1; …)
detele [] s;
return n;
}; // DijkstraPath
算法的时间复
杂度为 O(n2)
47
表 6-3 Dijkstra算法对图 6-1的执行过程
结点 I 1 2 3 4 5 6 7
0
s[i] 1 0 0 0 0 0 0
dist[i].len 0 10 30 100 ∞ ∞ ∞
dis[i].pre 1 1 1 1 -1 -1 -1
1
s[i] 1 1 0 0 0 0 0
dist[i].len 0 10 30 100 30 ∞ ∞
dist[i].pre 1 1 1 1 2 -1 -1
2
s[i] 1 1 1 0 0 0 0
dist[i].len 0 10 30 100 30 70 ∞
dist[i].pre 1 1 1 1 2 3 -1
3
s[i] 1 1 1 0 1 0 0
dist[i].len 0 10 30 100 30 40 ∞
dist[i].pre 1 1 1 1 2 5 -1
4
s[i] 1 1 1 0 1 1 0
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 -1
5
s[i] 1 1 1 1 1 1 0
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 -1
6
s[i] 1 1 1 1 1 1 1
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 -1
3010 100
20
20
10 40
10 20
255
1
2 3
5 6
7
4
48
§ 6.8.5 Floyd每对顶点间最短路径
?Dijkstra单源最短路径算法每次只求一个源点到其余各点
间的最短路径，若要求每对顶点间的最短路径，则需调用
n次 Dijkstra算法，时间复杂度为 O(n3)
?但对此问题,Floyd发现了一个更为直接的算法，我们称
之为 Floyd每对顶点间最短路径，它的时间复杂度也是
O(n3)
49
§ 6.8.5 Floyd每对顶点间最短路径
（一）基本方法
? Floyd算法实质上是一种迭代法，它在图的邻接矩阵上做 n次迭代
?第 n 次迭代后，邻接矩阵 i行 j列上元素值即为 i到 j的最短路径值
?具体地讲, Floyd算法递推地产生一个矩阵序列 （ 逻辑上 ） 。
A1,A2,...,An
?其中,A0=g（即图的邻接矩阵）,Ak[i][j]表示结点 i到 j的中间结点序号
不大于 k的最短路径长度 (k=1,...,n)
?显然,An[i][j]是 i到 j的最短路径长度，因为它中间经过的结点没受限
制（即允许为 1~n）
?事实上，对每个 k,Ak[i][j]都表示 i到 j的最短路径长，但该最短路径有
个条件限制：中间结点序号不大于 k。随着 k的增大，条件越来越放宽
（对中间结点限制越来越少），直至 k=n时，限制完全取消。
50
§ 6.8.5 Floyd每对顶点间最短路径
（一）基本方法
?现在讨论一下如何递推 Ak
?从 i到 j中间结点序号不大于 k的最短路径有两种情况：
(1)中间不经过结点 k，那么有
Ak[i][j]=Ak-1[i][j]
(2)中间经过结点 k：此时有
Ak[i][j] < Ak-1[i][j]
?对这后一种情况，该路径有两段连成，一段是 i到 k的中间结点序号不
大于 (k-1)的最短路径,其长度为 Ak-1[i][k]；另一段为 k到 j的中间结点序
号不大于 (k-1)的最短路径,其长度为 Ak-1[k][j]
51
§ 6.8.5 Floyd每对顶点间最短路径
（一）基本方法
?因此有
Ak[i][j] = Ak-1[i][k]+Ak-1[k][j]
?至于如何识别是属于情况 (1)还是 (2)，只要判别
Ak[i][j] < Ak-1[i][k]+Ak-1[k][j]
是否成立，若成立，则属于情况 (2)，否则属于情况 (1)
52
（二）算法实现
void FlordPath(TGrphEdge **g,long n,float **A,long **path)
{//g----输入量，表示图的邻接矩阵。 n---图结点个数；
//A----输出量，规模同 g的二维数组，存放各对顶点间的最短路径的值；
//path----输出量，规模同 g的二维数组，为各对顶点间的最短路径的结点序列的
链接。
long i,j,k;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
{
A[i][j] = g[i][j];
if (A[i][j] < 最大权值 ) path[i][j] = i;
else path[i][j] = -1;
}
53
（二）算法实现
for (k=1; k<=n; k++)
for (i=1;i<=n; i++)
for (j=1; j<=n; j++)
if (A[i][k] + A[k][j] < A[i][j] )
{
A[i][j] = A[i][k] + A[k][j];
path[[i][j] = path[k][j];
}
}
54
图 - 一个有向图
6
8
1
23 4
9
5
3 4
1 2
表 6-4 Floyd算法求解迭代过程示例 (对 图 6-2)
A0 A1 A2 A3 A4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1
2
3
4
0 1 ∞ 4
∞ 0 9 2
3 5 0 8
∞ ∞ 6 0
0 1 ∞ 4
∞ 0 9 2
3 4 0 7
∞ ∞ 6 0
0 1 10 3
∞ 0 9 2
3 4 0 6
∞ ∞ 6 0
0 1 10 3
12 0 9 2
3 4 0 6
9 10 6 0
0 1 9 3
11 0 8 2
3 4 0 6
9 10 6 0
path0 path1 path2 path3 path4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1
2
3
4
-1 -1 -1 -1
-1 -1 1 1
2 2 -1 2
-1 -1 3 -1
-1 -1 -1 -1
-1 -1 1 1
2 -1 -1 -1
-1 -1 3 -1
-1 -1 1 1
-1 -1 1 1
2 -1 -1 1
-1 -1 3 -1
-1 -1 1 1
2 -1 1 1
2 -1 -1 1
2 -1 3 -1
-1 -1 3 1
2 -1 3 1
2 -1 -1 1
2 -1 3 -1
§ 6.6 拓扑排序
? 目的
– 根据结点间的关系求得结点的一个线性排列。
? 在有关工程进度 /次序规划之类问题中，有着大量应用。
– 一般的大型工程，都可以划分为多个工序 /步骤 /子工程，这
些工序有的可独立进行，但大多数和其他工序关联，即某工
序的进行，要等到其他一些工序的完成才能开始。这类问题
都可归结到拓扑排序。
2
§ 6.6.1 拓扑序列与 AOV网
? 对有向图 G,若它的一个结点序列
LS,v1,v2,...,vn
满足这样的条件,<vi,vj>是 G的边时，在 LS中 vi位于 vj之
前（即 i<j），否则在 LS中 vi与 vj的前后次序任意，则称 LS为
图 G的一个 拓扑序列,求拓扑序列的操作称为 拓扑排序
（ Topological Sorting）。
某一图的拓扑序
列可能不唯一
3
§ 6.6.1 拓扑序列与 AOV网
? 拓扑排序主要用在一类称为 AOV网 （ Activity on Vertex
networks） 的有向图中 。
? AOV网是给有向图的结点与边赋予一定的语义的图, 具
体地：
– 结点 ──代表活动 。 如工程中的工序 /子任务, 状态等
– 边 ──代表活动之间的进行次序 。 边 <i,j>表示活动 i先于 j进行 。
? AOV网常用来表达流程图, 如一个工程中各子任务间的
流程图, 产品生产加工流程图, 程序流程图, 信息 （ 数据 ）
流程图, 活动安排流程图等
4
§ 6.6.1 拓扑序列与 AOV网
? 学生的选课次序就是一个 AOV网应用问题 。 例如, 假定某计算机专
业的主要课程如表 6-2所示, 则对应的 AOV网如图 6-1所示 。
10
1 2 3
9 6 4
5
7
8
11
图 - 对应的 AOV网
10 人工智能原理 1,2,3
7,9
表 6-2 课程进行关系
课程编号 课程名称 先行课
1 高等数学 -
2 离散数学 -
3 高级语言 -
4 数据结构 3,2
5 操作系统 4,6
6 计算机组成原理 2
7 数据库原理 5
8 编译原理 4,7
9 计算机网络 5,1
11 软件工程
5
§ 6.6.1 拓扑序列与 AOV网
? 图 6-1可有多个拓扑序列, 下面给出了它的两个
不同的拓扑序列：
1 2 3 4 6 5 9 7 8 11
1 2 3 4 6 5 7 9 8 11
? 如果采用串行修课方式, 则可完全按拓扑序列进
行, 但往往是一段时间内需同时修多门课, 这就需
识别出哪些课可同时修, 这是一个 识别可并行成份
的问题 。 例如, 在 图 6-1中, 可并行的课程有
(1,2,3)→ (4,6,10)→ (5)→ (9,7)→ (8,11)等几组 。
10
1 2 3
9 6 4
5
7
8
11
图 - 对应的 AOV网
6
§ 6.6.2 拓扑排序算法与实现
(一）基本方法
? 进行拓扑排序的基本方法是简单而直观的, 其包含下列几个步骤：
[1] 从有向图中找一个没有前趋的结点 v,若 v不存在, 则表明不可进
行拓扑排序 （ 图中有环路 ）, 结束 （ 不完全成功 ） ；
[2] 将 v输出；
[3] 将 v从图中删除, 同时删除关联于 v的所有的边
[4] 若图中全部结点均已输出，则结束（成功），否则转 [1]继续进行。
7
§ 6.6.2 拓扑排序算法与实现
(一）基本方法
? 通过对此方法做适当扩充, 就可在求拓扑序列的过程中
标识出可并行活动 （ 结点 ） 。
? 具体做法是, 初始时将所有无前趋结点标为一组可并行
结点 。 然后, 每次执行步骤 [3]后, 将新产生的无前趋结点
标为新的一组可并行结点 。 为了将同组并行结点连续排列,
在步骤 [1]中应优先选取并行组号与上次选择结点的并行组
号相同的结点 （ 若有的话 ）
8
§ 6.6.2 拓扑排序算法与实现
(二）数据结构的选取
? 邻接表的图结点的定义修改为：
template <class TElem>
struct TGrphNode
{
longnodeIdx; //结点编号
TElem nodeInfo; //结点信息
longinDegree; //结点的入度
TGrphEdge * firstOutEdge; //第一条出边的指针
};
9
§ 6.6.2 拓扑排序算法与实现
(二）数据结构的选取
? 而图边的定义仍为：
template <class TEdgeInfo>
struct TGrphEdge
{
longedgeEndIdx; //边终点编号
TEdgeInfo edgeInfo; //边信息
TGrphEdge *next; //链指针
};
10
§ 6.6.2 拓扑排序算法与实现
(二）算法实现
for (每个结点 v)
if (v入度为 0) v进栈 ;
while (栈不空 )
{
从栈中弹出一个元素送 v;
输出 v;
求出 v的第 1个直接可达邻接点 w;
while (w存在 )
{
将 w的入度域减 1;
if (w的入度域为 0) w进栈 ;
求出 v的下个直接可达邻接点 w;
} //while
} //while
11
(二）算法实现
下面是具体的 C++程序 。
longTopoSort(TGrphNode *g,long n,long *resu)
{ //对图 g求拓朴序列, 存入 sesu(结点编号 ),n为图结点数目 。
//返回所求得的结点数 。 若返回值小于 n,则表示未能完全拓扑排序 。
long*s,top,k,i;
TGrphEdge *p;
s = new long[n+1];
top=0;
k=0;
for (i=0; i<=n; i++)
if (g[i].inDegree == 0) {top++; s[top]=i; }
12
(二）算法实现
while (top>0)
{
i=s[top]; top--;
resu[k]=i; k++;
p=g[i].firstOutEdge;
while ( p!=NULL )
{
i=p->edgeEndIdx;
g[i].inDegree--;
if (g[i].inDegree==0) { top++; s[top]=i;}
p=p->next;
} //while (p!=…
}
delete [] s;
return k;
}
时间复杂度为 O(n+m)
13
§ 6.7 AOE网与关键路径
? 求关键路径是对边加权的有向图的一种操作。
? AOE网与 AOV网类似，也是一种被赋予了抽象语义的有
向图，是许多实际问题的模型。
14
§ 6.7.1 AOE网与关键路径的概念
(一） AOE网
? 如果将有向图的结点与边按下列所述赋予抽象意义,
则该种有向图就称为 AOE网 (Activity On Edge network)
– 边 （ 弧 ）,代表活动 （ 操作 ） ；
– 边权,代表活动的持续时间 。 记边 ak=<i,j>的权为 len(ak)或
len(i,j)；
– 结点,代表事件 （ 状态 ） 。 它表示它的各入边代表的活动均已完
成, 而它的出边代表的活动可以开始 。
? AOE网中没有入边的结点称为始点, 没有出边的结点
称为终点 。
15
AOE一般用来描述工程进度，结点表示工程进展中的状态，边表示子任务。图
6-1就是一个 AOE网，它可以看作是一个具有 11项子任务和 9个状态的假想工程的
进度图
a7=9
a9=4a6=2
a5=1a2=4
a1=6 a8=7
a3=5
a4=1 a10=2
a11=4v1
v2
v3
v4
v5
v6
v7
v8
v9
事件 含义
v1 开工
v2 活动 a1完成, 活动 a4可以开始
v3 活动 a2完成, 活动 a5可以开始
v4 活动 a3完成, 活动 a6可以开始
v5 活动 a4与 a5完成, 活动 a7和 a8可开始
,
v6 活动 a6完成, 活动 a9可以开始
v7 活动 a7完成, 活动 a10可以开始
v8 活动 a8完成, 活动 a11可以开始
v9 活动 a10和 a11完成, 整个工程完成
图 - AOE网举例
16
§ 6.7.1 AOE网与关键路径的概念
(二） AOE网的操作
? 针对 AOE网的操作一般有下列几种,
– 关键路径 CPM(Critical Path Method)。 这种操作最早用于
维修与建筑行业中工期进度估算。
– 性能估计与复审 PERT(Performance Evaluation and Review
Technique)：该项操作最初是为了研制北极星式导弹系统而引
入的
– 资源分配与多工程调度 RAMPS(Resource Allocation and Multi-
Project Scheduling)
17
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
? 下面的阐述中，设 AOE网的起点为 v0终点为 vn
1,关键路径
? AOE网中, 从事件 i到 j的路径中, 加权长度最大者称为
i到 j的 关键路径 （ Critical Path） 。 记为 cp(i,j).特别
地, 始点 0到终点 n的关键路径 cp(0,n)是整个 AOE的关键
路径 。
? 显然，关键路径决定着 AOE网的工期，关键路径的长
度就是 AOE网代表的工程所需的最小工期。
18
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
2,事件最早 /晚发生时间
事件 vi的最早发生时间 ve(i)定义为：从始点到 vi的最
长 （ 加权 ） 路径长度, 即 cp(0,i)
事件 vi的最晚发生时间 vl(i)定义为：在不拖延整个工
期的条件下, vi的可能的最晚发生时间 。 即
vl(i) = ve(n) - cp(i,n)
19
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
3,活动最早 /晚开始时间
活动 ak=<vi,vj>的 最早开始时间 e(k)：等于事件 vi的最早发生时
间, 即
e(k) = ve(i) = cp(0,i)
活动 ak=<vi,vj>的 最晚开始时间 l(k)定义为：在不拖延整个工期
的条件下, 该活动的允许的最迟开始时间, 即
l(k) = vl(j) – len(i,j)
这里, vl(j)是事件 j的允许的最晚发生时间, len(i,j)是 ak的权 。
活动 ak的 最大可利用时间,定义为 l(k)-e(k)
20
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
4,关键活动
若活动 ak的最大可利用时间等于 0（ 即 (l(k)=e(k)）,
则称 ak 为 关键活动, 否则为 非关键活动 。
显然, 关键活动的延期, 会使整个工程延期 。 但非关
键活动不然, 只要它的延期量不超过它的最大可利用时
间, 就不会影响整个工期 。
21
§ 6.7.1 AOE网与关键路径的概念
(三） 关键路径的若干基本概念
? 关键路径的概念, 也可以用这里的关键活动定义, 即
有下面的：
定理 6-2 某路径为关键路径的充分必要条件是, 它上
的各活动均为关键活动 。
22
§ 6.7.2 关键路径的识别
(三） 关键路径的若干基本概念
? 进行关键路径分析, 目的是寻找合理的资源调配方案
（ 这里的资源是指能使活动进行的人力或物力 ）, 使
AOE网代表的工程尽快完成 。
? 只有缩短关键路径上的活动 （ 关键活动 ） 才有可能缩
短整个工期
? 识别关键路径的公共点就变得很重要
23
§ 6.7.2 关键路径的识别
(一） 基本算法
? 设图 G=(V,E)是个 AOE网, 结点编号为 1,2,...,n,其
中结点 1与 n 分别为始点和终点, ak=<i,j>∈ E是 G的一个
活动 。
? 根据前面给出的定义, 可推出活动的最早及最晚发生
时间的计算方法：
e(k) = ve(i)
l(k) = ve(j) - len(i,j)
24
§ 6.7.2 关键路径的识别
(一） 基本算法
? 结点的最早发生时间的计算, 需按拓扑次序递推
ve(1) = 0
ve(j) = MAX{ ve(i)+len(i,j) } 对所有 <i,j> ∈ E的 i
25
§ 6.7.2 关键路径的识别
(一） 基本算法
? 结点的最晚发生时间的计算, 需按逆拓扑次序递推：
vl(n) = ve(n)
vl(i) = MIN{vl(j) - len(i,j)} 对所有 <i,j>∈ E的 j
…
j
…
i i …
…
j
图 - 计算 ve和 vl的示意
26
§ 6.7.2 关键路径的识别
(一） 基本算法
? 这种计算方法, 依赖于拓扑排序
? 计算 ve( j) 前, 应已求得 j 的各前趋结点的 ve值, 而计算 vl(i)
前, 应已求得 i的各后继结点的 vl值 。
? ve的计算可在拓扑排序过程中进行, 即在每输出一个结点 i后, 在
删除 i的每个出边 <i,j>（ 即入度减 1） 的同时, 执行
if ( ve[i]+len(i,j)) > ve[j] )
ve[j] = ve[i] + len(i,j)
27
§ 6.7.2 关键路径的识别
(一） 基本算法
? 通过逆方向使用拓扑序列即可递推出各 vl的值, 假定拓扑序列是 topoSeq，
则 vl 的值的求法为 （ 结点编号为 1~n） 。
for (k=1; k<=n; k++) vl[k] = ve[n]; //初始化
for ( k=n; k>=1; k--)
{
i=topoSeq[k];
j=（ i的第 1个直接射出点 ） ;
while (j存在 )
{
if (vl[j]-len(i,j)<vl[i])
vl[i]=vl[j]-len(i,j);
j = （ i的下一个直接射出点 ） ;
}
}
28
§ 6.8 最短路径
? 路径问题是有向图及无向图中的另一基本问题, 它涉及
下列两点：
– 对图中任两结点 u与 v,它们之间有路径吗？
– 若 u到 v之间有不止一条路径, 那么, 哪一条是最短路径 （ 代
价最小路径 ）？
? 对路径问题, 有两个著名算法,
– Dijkstra 单源最短路径算法
– Floyd每对结点最短路径算法 。
§ 6.8.1 路径问题
29
(一）基本方法
? Dijkstra单源最短路径算法是求图中任一结点到其余各结
点的最短路径 （ 路径表示与长度 ） 。
§ 6.8.2 Dijkstra单源最短路径算法
30
(二）基本策略
? 设图共有 n个不同的结点, 则从某一点出发达到其他各点
的最短路径有 (n-1) 条
? Dijkstra的基本策略是, 按长度不减次序构造这 (n-1)条最
短路径, 即先求出长度最小的一条最短路径, 然后求出长
度第二小的最短路径, 最后求出长度最大的最短路径
§ 6.8.2 Dijkstra单源最短路径算法
31
例如，对图 6-1所示有向图，若求结点 1到其它各结点的
最短路径，则求得的次序为,1-2,1-3,1-5,1-6,1-4,1-7.
3010 100
20
20
10 40
10 20
255
1
2 3
5 6
7
4
图 - 有向图的单源最短路径
(a) 一个有向图 (b) 有向图 (a)中 1到其他各点的最短路径
始点 终点 最短路径 最短路径长
度
长 度 次
序
1 2 (1,2) 10 1
3 (1,3) 30 2
4 (1,2,5,6,4) 60 5
5 (1,2,5) 30 3
6 (1,2,5,6) 40 4
7 无 ∞ 6
32
(二）基本策略
? 另外，设立两种数据结构：
1.集合 s：存放当前已找出的各最短路径的终点。即若 v∈ s，则表示
始点到 v的 最短路径已被求出
2.路径数组 dist：它的含意为：
– 若 i ∈ s，则 dis[i]等于始点 v0到 i的距离
– 若 i不属于 s，则 dis[i]等于始点 v0到 i的中间只经过 s中元素，且长度
最小的路径的长度（若无此种路径，则视长度为 ∞ ）
? 这两个数据结构是生成最短路径的关键。其中 dist充当候选集
§ 6.8.2 Dijkstra单源最短路径算法
33
? Dijkstra单源最短路径算法及其正确性均基于下列几点事实 。
(1),如果下一条 （ 即长度递增序列中的下一条 ） 最短路径的终点
是 u,则这条路径是从起点 v0开始, 中间只经过 s中结点, 而最后到达 u
的路径 。
(2),从 v0出发的长度最小的最短路径, 必为 v0的出边中权值最小者 。
(3),下一条最短路径的终点 u,必定是尚未进入 s中的那些结点
u1,...,um对应的 dist[u1],...,dist[um]中值最小者所对应的那个 uk，
即 u必满足：
dist[u]=min{dist[w]}，其中 w∈ s。
§ 6.8.3 Dijkstra算法的正确性
34
（一）算法实现基本框架
Dijkstra(g,n,v0,dist)
{ //对图 g求从源点 v0到其余各点的最短路径，结果存于 dist中。 n为图中结点个数
根据 g与 v0初始化 dist与 s;
while (未完 )
{
求满足 dist[u]=MIN{dist[w]}的 u，这里 w∈ s;
将 u加入到集合 s中 ;
调整候选集 dist
}
} //Dijkstra
§ 6.8.4 Dijkstra算法实现
35
（一）算法实现基本框架
? 根据 s与 dist的定义，在初始时，令 s只含源点 v0，而对每个 v≠ v0，置
dist[v]为 v0到 v的边的权值（ v0到 v无边时置为 ∞ ）
? 将新造出的结点 u加入 s后，某些结点的 dist值可能变得不满足 dist的定
义，故应调整 dist，使它重新满足定义
? 调整的方法为
for (每个不在 s中的 w)
if (dist[u]+cost(u,w) <dist[w] )
dist[w]=dist[u]+cost(u,w);
§ 6.8.4 Dijkstra算法实现
36
§ 6.8.4 Dijkstra算法实现
w
w
uv0
图 - Dijkstra算法调整候选集
37
（二）数据结构设计
? (1) 图：输入量，为待求最短路径的图。根据 Dijkstra算法的特点，
采用邻接矩阵为好。具体定义如下：
边 <i,j>的权值,若 i到 j有边
g[i][j] =
∞,若 i到 j无边
§ 6.8.4 Dijkstra算法实现
38
（二）数据结构设计
? (2) 路径与候选集 dist
? 为了能同时得到最短路径的构成（即路径上的结点序列），这里对
dist作适当的扩充，使得能从它得到各最短路径的结点序列
? 源点 v0到任一点 u 的最短路径构成形式为下列两种情形之一：
(v0,u) 或
(v0,u1,...,uk,u) (k≥ 1)
其中，路径 (v0,u1,...,um)为 v0到 um的最短路径 (1≤ m≤ k)
? 亦即，最短路径上结点序列的任一最左子序列均为某结点的最短路径
结点序列
? 我们称 (v0,u1,...,uk)或 (v0)为 v0到 u 的最短路径的 前趋路径
§ 6.8.4 Dijkstra算法实现
39
（二）数据结构设计
? 最短路径的此性质启发我们，对任一结点 u，只需设立它的前趋路径
的指示器就可推出源点到它的最短路径结点序列
? 据此，我们为 dist 的元素增设一个 pre字段，令它存放对应结点的前趋
路径的终点编号，即 dist[i].pre的值为源点到 i的最短路径的前趋路径的终
点编号
? 该字段相当于一个链指针，顺着它搜索的结果是最短路径的结点的逆
序
§ 6.8.4 Dijkstra算法实现
40
（二）数据结构设计
§ 6.8.4 Dijkstra算法实现
3010 100
20
20
10 40
10 20
255
1
2 3
5 6
7
4 结点 i 1 2 3 4 5 6 7
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 0
41
（二）数据结构设计
(3) 集合 s
集合 s为中间量，用一维数组表示，其元素含意为：
若 i！ ∈ s,s[i]=0
若 i∈ s,s[i]=1
? 如果图 g邻接矩阵的对角线元素不使用，则也可用对角线
元素 g[i][i]充当 s[i]。
§ 6.8.4 Dijkstra算法实现
42
（三）算法程序
struct TDijkPath
{
float len;
long pre;
};
§ 6.8.4 Dijkstra算法实现
43
§ 6.8.4 Dijkstra算法实现
long DijkstraPath(TGrphEdge **g,long n,long v0,TDijkPath *dist)
{
char *s;
long i,j,k;
float minW;
s = new char[n+1];
for (i=1; i<n; i++) //初始化
{
s[i] = 0;
dist[i].len = g[v0][i];
if (dist[i].len !=无边标志 ) dist[i].pre = v0;
else dist[i].pre = -1; //表示不存在
} //for
s[v0] = 1; //将源点 v0放入 s
44
§ 6.8.4 Dijkstra算法实现
for (i=1; i<n; i++) //每次求出一条最短路径
{
k=1;
for (j=k+1; j<n; j++) //求下条最短路径
if (s[j] )
if (dist[j].len < dist[k].len) k=j;
s[k] = 1; //将 k加入 s
45
§ 6.8.4 Dijkstra算法实现
for (j=1; j<n; j++) //调整候选集
if (!s[j])
if (dist[k]+g[k][j] < dist[j] )
{
dist[j] = dist[k]+g[k][j];
dist[j].pre = k; //将 k的前驱路径改为 k
}
}//for (i=1; …)
detele [] s;
return n;
}; // DijkstraPath
46
§ 6.8.4 Dijkstra算法实现
for (j=1; j<n; j++) //调整候选集
if (!s[j])
if (dist[k]+g[k][j] < dist[j] )
{
dist[j] = dist[k]+g[k][j];
dist[j].pre = k; //将 k的前驱路径改为 k
}
}//for (i=1; …)
detele [] s;
return n;
}; // DijkstraPath
算法的时间复
杂度为 O(n2)
47
表 6-3 Dijkstra算法对图 6-1的执行过程
结点 I 1 2 3 4 5 6 7
0
s[i] 1 0 0 0 0 0 0
dist[i].len 0 10 30 100 ∞ ∞ ∞
dis[i].pre 1 1 1 1 -1 -1 -1
1
s[i] 1 1 0 0 0 0 0
dist[i].len 0 10 30 100 30 ∞ ∞
dist[i].pre 1 1 1 1 2 -1 -1
2
s[i] 1 1 1 0 0 0 0
dist[i].len 0 10 30 100 30 70 ∞
dist[i].pre 1 1 1 1 2 3 -1
3
s[i] 1 1 1 0 1 0 0
dist[i].len 0 10 30 100 30 40 ∞
dist[i].pre 1 1 1 1 2 5 -1
4
s[i] 1 1 1 0 1 1 0
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 -1
5
s[i] 1 1 1 1 1 1 0
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 -1
6
s[i] 1 1 1 1 1 1 1
dist[i].len 0 10 30 60 30 40 ∞
dist[i].pre 1 1 1 6 2 5 -1
3010 100
20
20
10 40
10 20
255
1
2 3
5 6
7
4
48
§ 6.8.5 Floyd每对顶点间最短路径
?Dijkstra单源最短路径算法每次只求一个源点到其余各点
间的最短路径，若要求每对顶点间的最短路径，则需调用
n次 Dijkstra算法，时间复杂度为 O(n3)
?但对此问题,Floyd发现了一个更为直接的算法，我们称
之为 Floyd每对顶点间最短路径，它的时间复杂度也是
O(n3)
49
§ 6.8.5 Floyd每对顶点间最短路径
（一）基本方法
? Floyd算法实质上是一种迭代法，它在图的邻接矩阵上做 n次迭代
?第 n 次迭代后，邻接矩阵 i行 j列上元素值即为 i到 j的最短路径值
?具体地讲, Floyd算法递推地产生一个矩阵序列 （ 逻辑上 ） 。
A1,A2,...,An
?其中,A0=g（即图的邻接矩阵）,Ak[i][j]表示结点 i到 j的中间结点序号
不大于 k的最短路径长度 (k=1,...,n)
?显然,An[i][j]是 i到 j的最短路径长度，因为它中间经过的结点没受限
制（即允许为 1~n）
?事实上，对每个 k,Ak[i][j]都表示 i到 j的最短路径长，但该最短路径有
个条件限制：中间结点序号不大于 k。随着 k的增大，条件越来越放宽
（对中间结点限制越来越少），直至 k=n时，限制完全取消。
50
§ 6.8.5 Floyd每对顶点间最短路径
（一）基本方法
?现在讨论一下如何递推 Ak
?从 i到 j中间结点序号不大于 k的最短路径有两种情况：
(1)中间不经过结点 k，那么有
Ak[i][j]=Ak-1[i][j]
(2)中间经过结点 k：此时有
Ak[i][j] < Ak-1[i][j]
?对这后一种情况，该路径有两段连成，一段是 i到 k的中间结点序号不
大于 (k-1)的最短路径,其长度为 Ak-1[i][k]；另一段为 k到 j的中间结点序
号不大于 (k-1)的最短路径,其长度为 Ak-1[k][j]
51
§ 6.8.5 Floyd每对顶点间最短路径
（一）基本方法
?因此有
Ak[i][j] = Ak-1[i][k]+Ak-1[k][j]
?至于如何识别是属于情况 (1)还是 (2)，只要判别
Ak[i][j] < Ak-1[i][k]+Ak-1[k][j]
是否成立，若成立，则属于情况 (2)，否则属于情况 (1)
52
（二）算法实现
void FlordPath(TGrphEdge **g,long n,float **A,long **path)
{//g----输入量，表示图的邻接矩阵。 n---图结点个数；
//A----输出量，规模同 g的二维数组，存放各对顶点间的最短路径的值；
//path----输出量，规模同 g的二维数组，为各对顶点间的最短路径的结点序列的
链接。
long i,j,k;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
{
A[i][j] = g[i][j];
if (A[i][j] < 最大权值 ) path[i][j] = i;
else path[i][j] = -1;
}
53
（二）算法实现
for (k=1; k<=n; k++)
for (i=1;i<=n; i++)
for (j=1; j<=n; j++)
if (A[i][k] + A[k][j] < A[i][j] )
{
A[i][j] = A[i][k] + A[k][j];
path[[i][j] = path[k][j];
}
}
54
图 - 一个有向图
6
8
1
23 4
9
5
3 4
1 2
表 6-4 Floyd算法求解迭代过程示例 (对 图 6-2)
A0 A1 A2 A3 A4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1
2
3
4
0 1 ∞ 4
∞ 0 9 2
3 5 0 8
∞ ∞ 6 0
0 1 ∞ 4
∞ 0 9 2
3 4 0 7
∞ ∞ 6 0
0 1 10 3
∞ 0 9 2
3 4 0 6
∞ ∞ 6 0
0 1 10 3
12 0 9 2
3 4 0 6
9 10 6 0
0 1 9 3
11 0 8 2
3 4 0 6
9 10 6 0
path0 path1 path2 path3 path4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1
2
3
4
-1 -1 -1 -1
-1 -1 1 1
2 2 -1 2
-1 -1 3 -1
-1 -1 -1 -1
-1 -1 1 1
2 -1 -1 -1
-1 -1 3 -1
-1 -1 1 1
-1 -1 1 1
2 -1 -1 1
-1 -1 3 -1
-1 -1 1 1
2 -1 1 1
2 -1 -1 1
2 -1 3 -1
-1 -1 3 1
2 -1 3 1
2 -1 -1 1
2 -1 3 -1
