,数据结构,
第七章 (下 )
数据结构
tjm
第七章 图
7.1 图的定义和术语
7.2 图的存储结构
7.2.1 数组表示法
7.2.2 邻接表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.3 最小生成树
7.5 有向无环图及其应用
7.5.1 拓扑排序
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
7.6.2 每一对顶点之间的最短路径
数据结构
tjm
7.3 图的遍历
7.3.1 深度优先搜索
方法：从图的某一顶点 V0出发，访问此顶点；
然后依次从 V0的未被访问的邻接点出发，深度优
先遍历图，直至图中所有和 V0相通的顶点都被访
问到；
若此时图中尚有顶点未被访问，则另选图中一个
未被访问的顶点作起点,重复上述过程，直至图
中所有顶点都被访问为止 。
数据结构
tjm
V1
V2
V4 V5
V3
V7V6
V8
例：
深度遍历,V1?V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7
深度优先遍历算法（递归算法）参见 P169。
V1
V2
V4
V5
V3
V7
V6
V8
深度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
数据结构
tjm
V1
V2
V4 V5
V3
V7V6
V8
例：
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvexnextarc
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
深度遍历,V1?V3 ?V7 ?V6 ?V2 ?V5 ?V8 ?V4
数据结构
tjm
7.3.2 广度优先搜索
方法：从图的某一顶点 V0出发，访问此顶点后，
依次访问 V0的各个未曾访问过的邻接点；然后
分别从这些邻接点出发，广度优先遍历图，直
至图中所有已被访问的顶点的邻接点都被访问
到；
若此时图中尚有顶点未被访问，则另选图中一
个未被访问的顶点作起点, 重复上述过程，直
至图中所有顶点都被访问为止。
数据结构
tjm
V1
V2
V4 V5
V3
V7V6
V8
例,
广度遍历,V1?V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8
广度优先遍历算法参见 P170。
V1
V2
V4 V5
V3
V7V6
V8
广度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
数据结构
tjm
例,
1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvexnextarc
5 5
1 ^5
1
1
4 3 ^
2
2
广度遍历序列,1 4 3 2 5
数据结构
tjm
7.4 图的连通性问题
问题提出：要在 n个城市间建立通信联络网，用
顶点表示城市；权表示城市间建立通信线路所需
花费代价。希望找到一棵生成树，它的每条边上
的权值之和（即建立该通信网所需花费的总代价）
最小 —— 最小 (代价 )生成树。
1
65
43
27
13
17
9
18
12
7 5
2410
7.4.3 最小生成树
数据结构
tjm
算法思想：设 N=(V,{E})是连通网,TE是 N上最
小生成树中边的集合。
初始令 U={u0},(u0?V),TE=?。
在所有 u?U,v?V-U的边 (u,v)?E中，找一条代
价最小的边 (u0,v0)。
将 (u0,v0)并入集合 TE,同时 v0并入 U。
重复上述操作直至 U=V为止，则 T=(V,{TE})为 N
的最小生成树。
方法一：普里姆 (Prim)算法
构造最小生成树的方法
数据结构
tjm
例,1
65
4
3
2
6 51
3
5
6 6 4 2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4 2
1
1
6
4
3
2 1
4 2
5
1
65
4
3
2 1
4 2
5
3
算法实现：图用邻接矩阵表示。
算法参见 P175。
数据结构
tjm
例,1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
方法二：克鲁斯卡尔 (Kruskal)算法
算法思想：设连通网 N=(V,{E}),令最小生成树 初始状
态为只有 n个顶点而无边的非连通图 T=(V,{?})，每个
顶点自成一个连通分量。
在 E中选取代价最小的边，若该边依附的顶点落在 T中
不同的连通分量上，则将此边加入到 T中；否则，舍去
此边，选取下一条代价最小的边。
依此类推，直至 T中所有顶点都在同一连通分量上为止。
数据结构
tjm
7.5 有向无环图及其应用
7.5.1 拓扑排序
问题提出：假设以有向图表示一个工程的施工图
或程序的数据流图，则图中不允许出现回路 。如
何检查有向图中是否存在回路的方法之一，是对
有向图进行拓扑排序。
什么是拓扑排序,把 AOV网络中各顶点按照它们
相互之间的优先关系排列成一个线性序列的过
程叫拓扑排序。
拓扑排序的方法,
在有向图中选一个没有前驱的顶点且输出之 。
从图中删除该顶点和所有以它为尾的弧 。
重复上述两步，直至全部顶点均已输出；或者当
图中不存在无前驱的顶点为止。
数据结构
tjm
例：
课程代号 课程名称 先修课
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
无
C1
C1,C2
C1
C3,C4
C11
C3.C5
C3,C6
无
C9
C9
C1,C9,C10
程序设计基础
离散数学
数据结构
汇编语言
语言设计和分析
计算机原理
编译原理
操作系统
高等数学
线性代数
普通物理
数值分析
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列：
C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
或 C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个 AOV网的拓扑序列不是唯一的。
数据结构
tjm
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1 -- C2 --C3
--C8
--C4 --C5 --C7 --C9
--C10 --C11 --C6 --C12
数据结构
tjm
算法参见 P182
算法实现：
以邻接表作存储结构。
把邻接表中所有入度为 0的顶点进栈。
栈非空时，输出栈顶元素 Vj并退栈；在邻接表中查
找 Vj的直接后继 Vk,把 Vk的入度减 1；若 Vk的入度为
0则进栈。
重复上述操作直至栈空为止。若栈空时输出的顶
点个数不是 n,则有向图有环；否则，拓扑排序完
毕。
数据结构
tjm
4
3
2
1
5
例：
1 2
34
56
1
6
输出序列,6
q q q=NULL
1
q
4
q
3
q q=NULL
3
q q
2
q=NULL
2
q=NULL
4
q
5
q=NULL
5
q=NULL
0
1
2
2
入度 指针
5
5
4 3 ^
^
^
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
2
10
0
1
1
0
0
数据结构
tjm
问题提出,把工程计划表示为有向图，用顶点表示
事件，弧表示活动；每个事件表示在它之前的活动
已完成，在它之后的活动可以开始。
例,设一个工程有 11项活动,9个事件。
事件 V1—— 表示整个工程开始
事件 V9—— 表示整个工程结束
问题：（ 1）完成整项工程至少需要多少时间？
（ 2）哪些活动是影响工程进度的关键？
9
8
7
64
5
3
2
1
a6=2
7.5.2 关键路径
数据结构
tjm
定义,
AOE网 (Activity On Edge),也叫边表示活动的网。
AOE网是一个带权的有向无环图，其中顶点表示事
件，弧表示活动，权表示活动持续时间。
路径长度：路径上各活动持续时间之和。
关键路径：路径长度最长的路径。
Ve(j),表示事件 Vj的最早发生时间。
Vl(j),表示事件 Vj的最迟发生时间 。
e(i),表示活动 ai的最早开始时间。
l(i),表示活动 ai的最迟开始时间。
l(i)-e(i),表示完成活动 ai的时间余量。
关键活动：关键路径上的活动，即 l(i)=e(i)的活
动。
数据结构
tjm
设活动 ai用弧 <j,k>表示，其持续时间记为,dut(<j,k>)
则有：（ 1） e(i)=Ve(j)
（ 2） l(i)=Vl(k)-dut(<j,k>) j k
ai
如何求 Ve(j)和 Vl(j)？
(1)从 Ve(1)=0开始向前递推
为头的弧的集合是所有以其中 jT
njTjijidutiVeM a xjVe
i
????????? 2,,) },,()({)(
(2)从 Vl(n)=Ve(n)开始向后递推
为尾的弧的集合是所有以其中 iS
niSjijid u tjVlM i niVl
j
11,,) },,()({)( ??????????
问题分析
如何找 e(i)=l(i)的关键活动？
数据结构
tjm
求关键路径步骤：
求 Ve(i)
求 Vl(j)
求 e(i)
求 l(i)
计算 l(i)-e(i)
9
8
7
64
5
3
2
1
a6=2
V1
V2
V3
V4
V5
V6
V7
V8
V9
顶点 Ve Vl
0
6
4
5
7
7
16
14
18
0
6
6
8
7
10
16
14
18
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
活动 e l l-e
?
?
?
?
?
?
0 0 0
0 2 2
6 6 0
4 6 2
5 8 3
7 7 0
7 7 0
7 10 3
16 16 0
14 14 0
0 3 3
数据结构
tjm
算法实现：
以邻接表作存储结构。
从源点 V1出发，令 Ve[1]=0,按拓扑序列求各顶点的 Ve[i]。
从汇点 Vn出发，令 Vl[n]=Ve[n],按逆拓扑序列求其余各顶点
的 Vl[i]。
根据各顶点的 Ve和 Vl值，计算每条弧的 e[i]和 l[i],找出
e[i]=l[i]的关键活动。
算法描述：
输入顶点和弧信息，建立其邻接表。
计算每个顶点的入度。
对其进行拓扑排序：
排序过程中求顶点的 Ve[i]；
将得到的拓扑序列进栈。
按逆拓扑序列求顶点的 Vl[i]。
计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动。
数据结构
tjm
用带权的有向图表示一个交通运输网，图中：
顶点：表示城市。
边：表示城市间的交通联系。
权：表示此线路的长度或沿此线路运输所花的时
间或费用等问题：从某顶点出发，沿图的边到达
另一顶点所经过的路径中，各边上权值之和最小
的一条路径 —— 最短路径。
7.6 最短路径
问题提出
1,单源点最短路径
—— 迪杰斯特拉（ Dijkstra）算法
2、所有顶点之间的最短路径
—— 弗洛伊德（ Floyd）算法
数据结构
tjm
7.6.1 从某个顶点到其余各顶点的最短路径
5
1
4
3
2
0
5
10
60
20
100
50
30
10
长度最短路径
无
<V0,V2>
<V0,V4,V3>
<V0,V4>
<V0,V4,V3,V5>
10
50
30
60
V1
V2
V3
V4
V5
终点
数据结构
tjm
迪杰斯特拉 (Dijkstra)算法思想：
按路径长度递增次序产生最短路径算法：
把 V分成两组：
（ 1） S,已求出最短路径的顶点的集合。
（ 2） V-S=T,尚未确定最短路径的顶点集合。
将 T中顶点按最短路径递增的次序加入到 S中，
保证：（ 1）从源点 V0到 S中各顶点的最短路径
长度都不大于从 V0到 T中任何顶点的最短路径长
度。
（ 2）每个顶点对应一个距离值：
S中顶点：从 V0到此顶点的最短路径长度。
T中顶点：从 V0到此顶点的只包括 S中顶点
作中间顶点的最短路径长度。
数据结构
tjm
依据：可以证明 V0到 T中顶点 Vk的最短路径，或是从
V0到 Vk的直接路径的权值；或是从 V0经 S中顶点到 Vk
的路径权值之和。（反证法可证）
求最短路径步骤：
初始时令 S={V0},T={其余顶点 },T中顶点对应的
距离值。
若存在 <V0,Vi>，为 <V0,Vi>弧上的权值；
若不存在 <V0,Vi>,为 ∞ 。
从 T中选取一个其距离值为最小的顶点 W，加入 S。
对 T中顶点的距离值进行修改：若加进 W作中间顶点，
从 V0到 Vi的距离值比不加 W的路径要短，则修改此距
离值。
重复上述步骤，直到 S中包含所有顶点，即 S=V为止。
数据结构
tjm
7.6.2 每一对顶点之间的最短路径
方法一：每次以一个顶点为源点，重复执行
Dijkstra算法 n次。
算法时间复杂度为 T(n)=O(n3)。
方法二：弗洛伊德 (Floyd)算法。
算法思想：逐个顶点试探法。
求最短路径步骤：
初始时设置一个 n阶方阵，令其对角线元素为 0，
若存在弧 <Vi,Vj>,则对应元素为权值；否则为
∞ 。 逐步试着在原直接路径中增加中间顶点，若
加入中间点后路径变短，则修改之；否则，维持
原值所有顶点 。 试探完毕，算法结束 。
数据结构
tjm
0 4 6
6 0 2
3 7 0
加入 V2,路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
例：
1
3
2
2
6
4
3 11
A B
C
0 4 11
6 0 2
3 ∞ 0
初始,路径,AB ACBA BC
CA 无
第七章 (下 )
数据结构
tjm
第七章 图
7.1 图的定义和术语
7.2 图的存储结构
7.2.1 数组表示法
7.2.2 邻接表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.3 最小生成树
7.5 有向无环图及其应用
7.5.1 拓扑排序
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
7.6.2 每一对顶点之间的最短路径
数据结构
tjm
7.3 图的遍历
7.3.1 深度优先搜索
方法：从图的某一顶点 V0出发，访问此顶点；
然后依次从 V0的未被访问的邻接点出发，深度优
先遍历图，直至图中所有和 V0相通的顶点都被访
问到；
若此时图中尚有顶点未被访问，则另选图中一个
未被访问的顶点作起点,重复上述过程，直至图
中所有顶点都被访问为止 。
数据结构
tjm
V1
V2
V4 V5
V3
V7V6
V8
例：
深度遍历,V1?V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7
深度优先遍历算法（递归算法）参见 P169。
V1
V2
V4
V5
V3
V7
V6
V8
深度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
数据结构
tjm
V1
V2
V4 V5
V3
V7V6
V8
例：
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvexnextarc
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
深度遍历,V1?V3 ?V7 ?V6 ?V2 ?V5 ?V8 ?V4
数据结构
tjm
7.3.2 广度优先搜索
方法：从图的某一顶点 V0出发，访问此顶点后，
依次访问 V0的各个未曾访问过的邻接点；然后
分别从这些邻接点出发，广度优先遍历图，直
至图中所有已被访问的顶点的邻接点都被访问
到；
若此时图中尚有顶点未被访问，则另选图中一
个未被访问的顶点作起点, 重复上述过程，直
至图中所有顶点都被访问为止。
数据结构
tjm
V1
V2
V4 V5
V3
V7V6
V8
例,
广度遍历,V1?V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8
广度优先遍历算法参见 P170。
V1
V2
V4 V5
V3
V7V6
V8
广度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
数据结构
tjm
例,
1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvexnextarc
5 5
1 ^5
1
1
4 3 ^
2
2
广度遍历序列,1 4 3 2 5
数据结构
tjm
7.4 图的连通性问题
问题提出：要在 n个城市间建立通信联络网，用
顶点表示城市；权表示城市间建立通信线路所需
花费代价。希望找到一棵生成树，它的每条边上
的权值之和（即建立该通信网所需花费的总代价）
最小 —— 最小 (代价 )生成树。
1
65
43
27
13
17
9
18
12
7 5
2410
7.4.3 最小生成树
数据结构
tjm
算法思想：设 N=(V,{E})是连通网,TE是 N上最
小生成树中边的集合。
初始令 U={u0},(u0?V),TE=?。
在所有 u?U,v?V-U的边 (u,v)?E中，找一条代
价最小的边 (u0,v0)。
将 (u0,v0)并入集合 TE,同时 v0并入 U。
重复上述操作直至 U=V为止，则 T=(V,{TE})为 N
的最小生成树。
方法一：普里姆 (Prim)算法
构造最小生成树的方法
数据结构
tjm
例,1
65
4
3
2
6 51
3
5
6 6 4 2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4 2
1
1
6
4
3
2 1
4 2
5
1
65
4
3
2 1
4 2
5
3
算法实现：图用邻接矩阵表示。
算法参见 P175。
数据结构
tjm
例,1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
方法二：克鲁斯卡尔 (Kruskal)算法
算法思想：设连通网 N=(V,{E}),令最小生成树 初始状
态为只有 n个顶点而无边的非连通图 T=(V,{?})，每个
顶点自成一个连通分量。
在 E中选取代价最小的边，若该边依附的顶点落在 T中
不同的连通分量上，则将此边加入到 T中；否则，舍去
此边，选取下一条代价最小的边。
依此类推，直至 T中所有顶点都在同一连通分量上为止。
数据结构
tjm
7.5 有向无环图及其应用
7.5.1 拓扑排序
问题提出：假设以有向图表示一个工程的施工图
或程序的数据流图，则图中不允许出现回路 。如
何检查有向图中是否存在回路的方法之一，是对
有向图进行拓扑排序。
什么是拓扑排序,把 AOV网络中各顶点按照它们
相互之间的优先关系排列成一个线性序列的过
程叫拓扑排序。
拓扑排序的方法,
在有向图中选一个没有前驱的顶点且输出之 。
从图中删除该顶点和所有以它为尾的弧 。
重复上述两步，直至全部顶点均已输出；或者当
图中不存在无前驱的顶点为止。
数据结构
tjm
例：
课程代号 课程名称 先修课
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
无
C1
C1,C2
C1
C3,C4
C11
C3.C5
C3,C6
无
C9
C9
C1,C9,C10
程序设计基础
离散数学
数据结构
汇编语言
语言设计和分析
计算机原理
编译原理
操作系统
高等数学
线性代数
普通物理
数值分析
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列：
C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
或 C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个 AOV网的拓扑序列不是唯一的。
数据结构
tjm
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1 -- C2 --C3
--C8
--C4 --C5 --C7 --C9
--C10 --C11 --C6 --C12
数据结构
tjm
算法参见 P182
算法实现：
以邻接表作存储结构。
把邻接表中所有入度为 0的顶点进栈。
栈非空时，输出栈顶元素 Vj并退栈；在邻接表中查
找 Vj的直接后继 Vk,把 Vk的入度减 1；若 Vk的入度为
0则进栈。
重复上述操作直至栈空为止。若栈空时输出的顶
点个数不是 n,则有向图有环；否则，拓扑排序完
毕。
数据结构
tjm
4
3
2
1
5
例：
1 2
34
56
1
6
输出序列,6
q q q=NULL
1
q
4
q
3
q q=NULL
3
q q
2
q=NULL
2
q=NULL
4
q
5
q=NULL
5
q=NULL
0
1
2
2
入度 指针
5
5
4 3 ^
^
^
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
2
10
0
1
1
0
0
数据结构
tjm
问题提出,把工程计划表示为有向图，用顶点表示
事件，弧表示活动；每个事件表示在它之前的活动
已完成，在它之后的活动可以开始。
例,设一个工程有 11项活动,9个事件。
事件 V1—— 表示整个工程开始
事件 V9—— 表示整个工程结束
问题：（ 1）完成整项工程至少需要多少时间？
（ 2）哪些活动是影响工程进度的关键？
9
8
7
64
5
3
2
1
a6=2
7.5.2 关键路径
数据结构
tjm
定义,
AOE网 (Activity On Edge),也叫边表示活动的网。
AOE网是一个带权的有向无环图，其中顶点表示事
件，弧表示活动，权表示活动持续时间。
路径长度：路径上各活动持续时间之和。
关键路径：路径长度最长的路径。
Ve(j),表示事件 Vj的最早发生时间。
Vl(j),表示事件 Vj的最迟发生时间 。
e(i),表示活动 ai的最早开始时间。
l(i),表示活动 ai的最迟开始时间。
l(i)-e(i),表示完成活动 ai的时间余量。
关键活动：关键路径上的活动，即 l(i)=e(i)的活
动。
数据结构
tjm
设活动 ai用弧 <j,k>表示，其持续时间记为,dut(<j,k>)
则有：（ 1） e(i)=Ve(j)
（ 2） l(i)=Vl(k)-dut(<j,k>) j k
ai
如何求 Ve(j)和 Vl(j)？
(1)从 Ve(1)=0开始向前递推
为头的弧的集合是所有以其中 jT
njTjijidutiVeM a xjVe
i
????????? 2,,) },,()({)(
(2)从 Vl(n)=Ve(n)开始向后递推
为尾的弧的集合是所有以其中 iS
niSjijid u tjVlM i niVl
j
11,,) },,()({)( ??????????
问题分析
如何找 e(i)=l(i)的关键活动？
数据结构
tjm
求关键路径步骤：
求 Ve(i)
求 Vl(j)
求 e(i)
求 l(i)
计算 l(i)-e(i)
9
8
7
64
5
3
2
1
a6=2
V1
V2
V3
V4
V5
V6
V7
V8
V9
顶点 Ve Vl
0
6
4
5
7
7
16
14
18
0
6
6
8
7
10
16
14
18
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
活动 e l l-e
?
?
?
?
?
?
0 0 0
0 2 2
6 6 0
4 6 2
5 8 3
7 7 0
7 7 0
7 10 3
16 16 0
14 14 0
0 3 3
数据结构
tjm
算法实现：
以邻接表作存储结构。
从源点 V1出发，令 Ve[1]=0,按拓扑序列求各顶点的 Ve[i]。
从汇点 Vn出发，令 Vl[n]=Ve[n],按逆拓扑序列求其余各顶点
的 Vl[i]。
根据各顶点的 Ve和 Vl值，计算每条弧的 e[i]和 l[i],找出
e[i]=l[i]的关键活动。
算法描述：
输入顶点和弧信息，建立其邻接表。
计算每个顶点的入度。
对其进行拓扑排序：
排序过程中求顶点的 Ve[i]；
将得到的拓扑序列进栈。
按逆拓扑序列求顶点的 Vl[i]。
计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动。
数据结构
tjm
用带权的有向图表示一个交通运输网，图中：
顶点：表示城市。
边：表示城市间的交通联系。
权：表示此线路的长度或沿此线路运输所花的时
间或费用等问题：从某顶点出发，沿图的边到达
另一顶点所经过的路径中，各边上权值之和最小
的一条路径 —— 最短路径。
7.6 最短路径
问题提出
1,单源点最短路径
—— 迪杰斯特拉（ Dijkstra）算法
2、所有顶点之间的最短路径
—— 弗洛伊德（ Floyd）算法
数据结构
tjm
7.6.1 从某个顶点到其余各顶点的最短路径
5
1
4
3
2
0
5
10
60
20
100
50
30
10
长度最短路径
无
<V0,V2>
<V0,V4,V3>
<V0,V4>
<V0,V4,V3,V5>
10
50
30
60
V1
V2
V3
V4
V5
终点
数据结构
tjm
迪杰斯特拉 (Dijkstra)算法思想：
按路径长度递增次序产生最短路径算法：
把 V分成两组：
（ 1） S,已求出最短路径的顶点的集合。
（ 2） V-S=T,尚未确定最短路径的顶点集合。
将 T中顶点按最短路径递增的次序加入到 S中，
保证：（ 1）从源点 V0到 S中各顶点的最短路径
长度都不大于从 V0到 T中任何顶点的最短路径长
度。
（ 2）每个顶点对应一个距离值：
S中顶点：从 V0到此顶点的最短路径长度。
T中顶点：从 V0到此顶点的只包括 S中顶点
作中间顶点的最短路径长度。
数据结构
tjm
依据：可以证明 V0到 T中顶点 Vk的最短路径，或是从
V0到 Vk的直接路径的权值；或是从 V0经 S中顶点到 Vk
的路径权值之和。（反证法可证）
求最短路径步骤：
初始时令 S={V0},T={其余顶点 },T中顶点对应的
距离值。
若存在 <V0,Vi>，为 <V0,Vi>弧上的权值；
若不存在 <V0,Vi>,为 ∞ 。
从 T中选取一个其距离值为最小的顶点 W，加入 S。
对 T中顶点的距离值进行修改：若加进 W作中间顶点，
从 V0到 Vi的距离值比不加 W的路径要短，则修改此距
离值。
重复上述步骤，直到 S中包含所有顶点，即 S=V为止。
数据结构
tjm
7.6.2 每一对顶点之间的最短路径
方法一：每次以一个顶点为源点，重复执行
Dijkstra算法 n次。
算法时间复杂度为 T(n)=O(n3)。
方法二：弗洛伊德 (Floyd)算法。
算法思想：逐个顶点试探法。
求最短路径步骤：
初始时设置一个 n阶方阵，令其对角线元素为 0，
若存在弧 <Vi,Vj>,则对应元素为权值；否则为
∞ 。 逐步试着在原直接路径中增加中间顶点，若
加入中间点后路径变短，则修改之；否则，维持
原值所有顶点 。 试探完毕，算法结束 。
数据结构
tjm
0 4 6
6 0 2
3 7 0
加入 V2,路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
例：
1
3
2
2
6
4
3 11
A B
C
0 4 11
6 0 2
3 ∞ 0
初始,路径,AB ACBA BC
CA 无
