Graphs

图的类型定义 n(n≥0)个元素的有限集合

基 本 术 语

图是由一个顶点集V和一个弧集VR构 成的数据结构 Graph = (V , VR ) 其中:VR＝{<v,w>| v,w∈V 且 P(v,w)} <v,w>表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾 谓词 P(v,w) 定义了弧 <v,w>的意义或信息

B E C D 由于“弧”是有方向的，因此称由 顶点集和弧集构成的图为有向图 例如: 其中: G1 = (V1, VR1) V1={A, B, C, D, E} VR1={<A,B>,<A,E>, <B,C>,<C,D>, <D,B>,<D,A>, <E,C>} G1 = (V1, VR1) A B E C D

B C 由顶点集和边集构成的图称作无向图 若有<v, w>VR,必 有<w, v>VR,则称 A D F E 例如: G2=(V2,VR2) V2={A, B, C, D, E, F} VR2={<A,B>, <A,E>, <B,E>, <C,D>, <D,F>, <B,F>, <C,F> }

名词和术语 完全图、稀疏图、稠密图 网、子图 邻接点、度、入度、出度 路径、路径长度、简单路径、简单回路 连通图、连通分量、 强连通图、强连通分量 生成树、生成森林 关节点、重连通图 重连通分量、连通度

图G=( V, VR ),且VV, VRVR, 则 称 G 为 G 的子图 弧或边带权的图分别称作有向网或无向网 A B E C F 15 9 7 21 11 3 2 B 设图G=( V,VR )和 图G=( V, VR ),且VV, VRVR, 则 称 G 为 G 的子图 A B E C F

假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作无向完全图 含有 e=n(n-1) 条弧的有向图称作有向完全图 若边或弧的个数 e<nlogn，则称作稀疏图，否则称作稠密图

假若顶点v 和顶点w 之间存在一条边，则称顶点v和w互为邻接点，边(v,w) A C D F E B ID(B) = 3 ID(A) = 2

有向图 顶点的出度: 以顶点v为弧尾的弧的数目 顶点的入度: 以顶点v为弧头的弧的数目 顶点的度(TD)= A B E C F OD(B) = 1 顶点的度(TD)= 出度(OD)+入度(ID) ID(B) = 2 TD(B) = 3

设图G=(V,{VR})中的一个顶点序列 { u=vi,0,vi,1, …, vi,m=w}中， (vi,j-1,vi,j)VR 1≤j≤m, 则称从顶点u 到顶点w 之 间存在一条路径。路径上 边的数目称作路径长度 A B E C F 长度为3的路径{A,B,C,F}

简单回路:序列中第一个顶点和最后一个顶点相同的路径 简单路径:序列中顶点不重复出现的路径 A B E C F 简单回路:序列中第一个顶点和最后一个顶点相同的路径

若图G中任意两个顶点之间都有路径相通，则称此图为连通图 B A C D F E B A C D F E 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量

若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图, 对有向图， 否则，其各个强连通子 图称作它的强连通分量 A B E C F A B E C F

假设一个连通图有n个顶点和e条边，其中n-1 条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树 对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林 B A C D F E

若连通图中的某个顶点和其相关 联的边被删去之后，该连通图被分割 成两个或两个以上的连通分量，则称 此顶点为关节点 没有关节点的连通图被称为重连 通图

一个连通图G如果不是重连通图， 那么它可以包括几个重连通分量 若依次删除一个连通图中的 1, 2, …, k-1 个顶点后,该图仍连通,删除第k个顶 点后该图成为不连通的,则称该图的 连通度为k

基本操作 结构的建立和销毁 对顶点的访问操作 插入或删除顶点 插入和删除弧 对邻接点的操作 顶点的遍历

结构的建立和销毁 CreatGraph(&G, V, VR): //按定义(V, VR) 构造图 DestroyGraph(&G): //销毁图

对顶点的访问操作 LocateVex(G, u); //若G中存在顶点u，则返回该顶点在 //图中“位置”；否则返回其它信息 GetVex(G, v); //返回 v 的值 PutVex(&G, v, value); //对 v 赋值value

对邻接点的操作 FirstAdjVex(G, v); //返回v的“第一个邻接点”。若该顶点 //在G中没有邻接点，则返回“空” NextAdjVex(G, v, w); //返回v的（相对于w的）“下一个邻接 //点”。若w是v的最后一个邻接点，则 //返回“空”

插入或删除顶点 InsertVex(&G, v); //在图G中增添新顶点v DeleteVex(&G, v);

插入和删除弧 InsertArc(&G, v, w); //则还增添对称弧<w,v> DeleteArc(&G, v, w); //在G中增添弧<v,w>，若G是无向的， //则还增添对称弧<w,v> DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的， //则还删除对称弧<w,v>

遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次

图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、图的逆邻接表存储表示 四、有向图的十字链表存储表示 五、无向图的邻接多重表存储表示 六、图的数组(关联矩阵)存储表示

图的数组(邻接矩阵)存储表示 Aij={ 0 (i,j)VR 定义:矩阵的元素为 1 (i,j)VR 无向图的邻接矩阵是对称矩阵 B A C D F E

有向图的邻接矩阵为非对称矩阵 A B E C D

　　在有向图中, 统计第 i 行 1 的个 数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度 　　在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度

图的邻接表存储表示 0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3 B C A D F E

可见，在有向图的邻接表中不易找到指向该顶点的弧 1 4 2 3 0 1 A B C D E  A B E C D 0 1 2 3 4  可见，在有向图的邻接表中不易找到指向该顶点的弧 

图的逆邻接表存储表示 在有向图的 邻接表中， 对每个顶点，链接的是指 向该顶点的 弧 A B E C D A B C D E 1  3 4 3 4 2  1

在用邻接表表示有向图时, 有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表(十字链表)可把两个表结合起来表示。 边结点的结构 mark vertex1 vertex2 path1 path2 其中，mark是处理标记；vertex1和vertex2指明该有向边始顶点和终顶点的位置。

path1是指向始顶点与该边相同的下一条边的指针；path2是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域cost。 顶点结点的结构 每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员data存放与该顶点相关的信息，指针Firstin指示以该顶点为始顶点的出边表的第一条边，Firstout指示以该顶点为终顶点的入边表的第一条边。 data Firstin Firstout

有向图的十字链表表示法 例 b d a c a b c d 1 2 3 4 1 3 1 2 3 4 3 1 4 3 4 2 4 1 ^ ^ 1 3 1 2 3 4 3 1 4 3 4 2 4 1 ^ ^ ^ ^ ^ ^ ^ ^

         邻接多重表的结构 e6 e1 A 0 1  e2 e5 0 3 1 B e2 e1 e4 2 C data Fin Fout mark vtx1 vtx2 path1 path2 e6 e1 A 0 1  A E e2 e5 0 3  1 B e2 e1 D e4 2 C 1 2   e3 e3 B C 3 D e4 2 3   4 E e5   3 4 e6 4 0  

无向图的邻接多重表表示法 例 a e c b d 1 2 3 4 a c d b 5 e 1 2 1 4 3 4 3 2 3 5 5 2 ^ 1 2 1 4 3 4 3 2 3 5 5 2 ^ ^ ^ ^ ^

定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵 关联矩阵——表示顶点与边的关联关系的矩阵 定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵

例 G1 2 4 1 3     4 3 2 1      4 3 2 1 5 6 例 1 5 3 2 4 G2 6

例 B D A C 1 2 3 4 5 6 A B C D 4 3 2 1 5 6

特点 关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大 无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行中“1”的个数 顶点Vi的入度是A中第i行中“-1”的个数

图的遍历 深度优先遍历 DFS (Depth First Search)　 广度优先遍历 BFS (Breadth First Search)

深度优先遍历DFS(Depth First Search) 深度优先遍历的示例 A C D E G B F I H 1 2 3 4 5 6 7 8 9 前进 回退 深度优先遍历过程 深度优先生成树

广度优先遍历BFS(Breadth First Search) 广度优先遍历的示例 1 2 5 1 2 5 A B E A B E 4 3 7 D C G 4 3 D C G 7 6 6 F H I F H I 8 9 8 9 广度优先遍历过程 广度优先生成树

邻接表表示的 图的类定义

#define MAXSIZE 100 template <class Type> class Node { int vertex; Node * next; } template <class Type> class Headnode { Type data; Node *link; } template <class Type> class Graph { Headnode head[MAXSIZE]; }; int visit[MAXSIZE];

void comp ( int n, Graph g ) { for ( i = 0; i < n; i++ ) visit[ i ] = 0; for ( i = 0; i < n; i++ ) if ( !visit[ i ] ) dfs ( i, g ) 或 bfs ( i ,g ); }

void dfs ( int i, Graph g ) { cout << g.head[ i ].data; Push ( s, i ); visit[ i ] = 1; do { p = g.head[ Top ( s ) ].link; while ( ( p != NULL ) && ( visit[ p->vertex ] ) ) p = p->next;

if ( p == Null ) Pop ( s ); else { i = p->vertex; cout << g.head[ i ].data; Push ( s, i ); visit[ i ] = 1; } } while ( !Empty ( s ) ); }

void bfs ( int i, Graph g ) { cout << g.head[ i ].data; Inqueue ( q, i ); visit[ i ] = 1; do { p = g.head[ Gethead ( q ) ].link; while ( p != NULL ) { i = p->vertex;

if ( !visit[ i ] ) { cout << g.head[ i ].data; Inqueue ( q, i ); visit[ i ] = 1; } p = p->next; Outqueue ( q ); } while ( !Empty ( q ) );

最小代价生成树 (minimum cost spanning tree)

n-1 条线路，如何在最节省经费的前提下建立这个通讯网？ 问题 　假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1 条线路，如何在最节省经费的前提下建立这个通讯网？

该问题等价于 构造网的一棵最小生成树，即： 在 e 条带权的边中选取n-1条边（不 构成回路），使“权值之和”为最小

使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边

构造最小生成树的准则 必须使用且仅使用该网络中的n-1 条边来联结网络中的 n 个顶点 不能使用产生回路的边 各边上的权值的总和达到最小

算法一：普里姆算法 (Prim) 算法二：克鲁斯卡尔算法 (Kruskal)

普里姆算法的 基本思想

1.取图中任意一个顶点 v 作为 生成树的根，之后往生成树 上添加新的顶点 w

2.在添加的顶点 w 和已经在生 成树上的顶点 v 之间必定存 在一条边，并且该边的权值 在所有连通顶点 v 和 w 之间 的边中取值最小

3.之后继续往生成树上添加顶 点，直至生成树上含有 n-1 个顶点为止

所得生成树权值和 = 14+8+3+5+16+21 = 67 a a b b c c e e g g d d f f 19 5 5 12 18 e e 8 8 16 16 3 3 g g d d 27 21 21 所得生成树权值和 f f = 14+8+3+5+16+21 = 67

一般情况下所添加的顶点应满足下列条件: 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

25 10 5 4 6 1 3 2 28 14 24 22 16 18 原图 (a) (b) (c) (d) (e) (f) 12

克鲁斯卡尔算法的 基本思想

考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止

19 19 a a b b 5 5 12 12 14 14 c c 7 7 18 18 e e 16 16 8 8 3 3 g g d d 27 21 21 f f

10 5 4 6 1 3 2 28 25 14 24 22 16 18 12 原图 (a) (b)

10 12 5 4 6 1 3 2 28 25 14 24 22 16 18 原图 (c) (d) (e) (f) (g)

比较两种算法 克鲁斯卡尔 算法名 普里姆 时间复杂度 O(n2) O(eloge) 适应范围 稠密图 稀疏图

活动网络 ( Activity Network ) 用顶点表示活动的网络( AOV网络 ) ( Activity On Vertices ) 用边表示活动的网络( AOE网络 ) ( Activity On Edges ) 有向无环图

C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 课程代号 课程名称 先修课程 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8

C8 C9 C1 C7 C3 C4 C2 C6 C5 学生课程学习工程图

拓扑排序(TopologicalSort) 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系 由此所得顶点的线性序列 称之为拓扑有序序列

例如：对于下列有向图 B D A C 可求得拓扑有序序列： A B C D 或 A C B D

反之，对于下列有向图 B A D C 不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D}

进行拓扑排序的步骤 一、从有向图中选取一个没有前驱 的顶点，并输出之 二、从有向图中删去此顶点以及所 有以它为尾的弧 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止

c a d g e b f h a b h c d g f e

在算法中需要用定量的描述替代定性的概念 没有前驱的顶点  入度为零的顶点 删除顶点及以它为尾的弧  弧头顶点的入度减1

对学生选课图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 C8 C3 C5 C4 C9 C6 C7 C1 C2

C0 C1 C2 C3 C4 C5 (a) 有向无环图 (b) 输出顶点C4 (c) 输出顶点C0 (d) 输出顶点C3

C4 , C0 , C3 , C2 , C1 , C5 (e) 输出顶点C2 (f) 输出顶点C1 (g) 输出顶点C5 (h) 拓扑排序完成 C4 , C0 , C3 , C2 , C1 , C5

AOV网邻 接表表示 count data adj 1 3 0 1 3 2 5 3 C3 0 4 5 0 5 C5 0 C0 C1 C2 dest link 3 0 5 5 0 1 2 3 4 5 AOV网邻 接表表示

在算法中, 使用一 个堆栈或队列存放入度 为零的顶点, 供选择和 输出无前驱的顶点

拓扑排序算法描述

建立入度为零的顶点栈 当入度为零的栈不空时, 重复执行 从栈中退出一个顶点, 并输出之 从AOV网中删去这个顶点和它发出的边, 边的终点入度减一 如果边的终点入度减至0, 则该顶点进入入度为零的顶点栈 如果输出顶点个数少于AOV网的顶点个数, 则报告网络中存在有向环

建立入度为零的顶点队 当入度为零的队不空时, 重复执行 从队中退出一个顶点, 并输出之 从AOV网中删去这个顶点和它发出的边, 边的终点入度减一 如果边的终点入度减至0, 则该顶点进入入度为零的顶点队 如果输出顶点个数少于AOV网的顶点个数, 则报告网络中存在有向环

在算法实现时, 为了建立入度为零的顶点栈,可以不另外分配存储空间, 直接利用入度为零的顶点的count[ ]数组元素。设立一个栈顶指针 top, 指示当前栈顶位置, 即某一个入度为零的顶点。栈初始化时置top = -1

将顶点i 进栈时执行以下指针的修改： count[i] = top; top = i ; // top指向新栈顶i, 原栈顶元素在count[i]中 退栈操作可以写成： j = top; top = count[top]; //位于栈顶的顶点记于 j, top退到次 栈顶

拓扑排序时入度为零的顶点栈在count[]中的变化 1 3 -1 2 4 5 top 建栈 顶点4 出栈 顶点0

拓扑排序时入度为零的顶点栈在count[]中的变化 top top top 1 2 3 4 5 2 1 -1 1 2 3 4 5 2 -1 1 1 2 3 4 5 2 -1 1 2 3 4 5 2 -1 top top 顶点3 出栈 顶点2 出栈 顶点1 出栈 顶点5 出栈 top

拓扑排序的算法

void Graph :: TopologicalSort ( ) { int top=-1; //入度为零的顶点栈初始化 for ( int i=0; i<n; i++ ) //入度为零顶点 if ( count[i]==0 ) //进栈 { count[i]=top; top=i; } for ( i=0; i<n; i++ ) //期望输出n个顶点 if ( top==-1 ) //中途栈空,转出 { cout<<“网络中有回路！"<<endl; return; };

else //继续拓扑排序 { int j=top; top=count[top]; //退栈 cout<<j<<endl; //输出 Edge * p=NodeTable[j].adj; while ( p!=NULL ) //扫描出边表 { int k=p->dest; //另一顶点

if ( --count[k]==0 ) //顶点入度减一 { count[k]=top; top=k; } //顶点的入度减至零, 进栈 p = p->link; }

分析此拓扑排序算法可知，如果AOV网 络有n 个顶点，e 条边，在拓扑排序的过 程中，搜索入度为零的顶点，建立链式 栈所需要的时间是O(n)。在正常的情况 下，有向图有 n 个顶点，每个顶点进一 次栈，出一次栈，共输出 n 次。顶点入 度减一的运算共执行了 e 次。所以总的 时间复杂度为O(n+e)

关键路径(Critical Path) 假设以有向网表示一个施工流程 问题: 图，弧上的权值表示完成该项子 工程所需时间。 　　　假设以有向网表示一个施工流程 图，弧上的权值表示完成该项子 工程所需时间。 问：哪些子工程项是“关键工程”？ 即：哪些子工程项将影响整个工程的 完成期限 问题:

整个工程完成的时间为：从有向图的源点到汇点的最长路径 例如: 汇点 b g 2 6 6 1 1 8 a e k 4 1 7 7 4 4 源点 5 c h 4 2 d f

用有向边表示一个工程中的活动 (Activity), 用边上权值表示活动持续 时间 (Duration), 用顶点表示事件 (Event) “关键活动”指的是： 该弧上的 权值增加 将使有向图上的最长路径的 长度增加

完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径

如何求关键活动？

“事件(顶点)”的最早发生时间 ve(j) “事件(顶点)”的最迟发生时间 vl(k) 假设第 i 条弧为 <j, k> 对第 j 个顶点而言 “事件(顶点)”的最早发生时间 ve(j) “事件(顶点)”的最迟发生时间 vl(k) 对第 i 项活动而言 “活动(弧)”的最早开始时间 ee(i) “活动(弧)”的最迟开始时间 el(i)

ee(i) = ve(j) el(i) = vl(k) – dut(<j,k>) ve(源点) = vl(源点) = 0 vl(汇点) = ve(汇点) 关键活动:el(i) = ee(i)

ve(源点) = 0； ve(k) = Max{ve(j) + dut(<j, k>)} (2<=k<=n, <j, k>属于所有以k为 头的弧的集合) vl(汇点) = ve(汇点)； vl(j) = Min{vl(k) – dut(<j, k>)} (1<=j<=n-1, <j, k>属于所有以j为 尾的弧的集合)

这两个递推公式的计 算必须分别在拓扑有序及 逆拓扑有序的前提下进行

b g 2 6 1 8 a e k 4 1 7 4 5 c h 4 2 d f 拓扑有序序列: a - d - f - c - b - e - h - g - k 6 4 5 5 7 7 15 14 11 18 18 18 6 18 6 18 8 8 7 18 18 10 16 18 18 14 18

6 4 5 7 7 15 14 18 6 6 8 7 10 16 14 18 6 4 5 7 7 7 15 14 2 3 6 6 8 8 7 10 16 14

显然 求ve的顺序应该是按拓扑有序的 次序 而 求vl的顺序应该是按拓扑逆序的 次序 因为 拓扑逆序序列即为拓扑有序序列 的逆序列 因此 应该在拓扑排序的过程中， 另设一个“栈”记下拓扑有序序列

要找出关键路径，必须找出关键活 动, 即不按期完成就会影响整个工程完 成的活动关键路径上的所有活动都是关 键活动 因此, 只要找到了关键活动, 就可以 找到关键路径

1 2 3 4 5 6 7 8 ve vl 0 8 12 22 28 40 46 58 1 2 3 4 5 6 7 8 9 10 ee el 0 0 8 12 12 22 22 28 40 46 0 0 8 12 12 32 22 28 40 46 2 5 a7=6 a8=18 a1=8 a3=14 a10=12 1 4 7 8 a6=8 a4=10 a9=6 a2=12 3 a5=28 6

注 意 所有顶点按拓扑有序的次序编号 仅计算 ve[i] 和 vl[i] 是不够的，还须计算 ee[k] 和 el[k] 注 意 所有顶点按拓扑有序的次序编号 仅计算 ve[i] 和 vl[i] 是不够的，还须计算 ee[k] 和 el[k] 不是任一关键活动加速一定能使整个工程提前 想使整个工程提前，要考虑各个关键路径上所有关键活动

一个工程实例： 施工阶段 1 2 3 挖土 8 6 垫层 5 砌基 10 7 回填 4 挖土 垫层 回填 砌基 20 10 16 25 总工期 =20+16+25+10=61 分阶段施工缩短后的工期=42 挖1 挖2 挖3 6 6 8 6 垫1 垫2 垫3 5 5 10 砌1 砌2 8 7 砌3 回2 回3 回1 4 3 3

最短路径 (Shortest Path)

最短路径问题 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小

问题解法 边上权值非负情形的单源最短路径 问题 — Dijkstra算法 所有顶点之间的最短路径 — Floyd算法

为求得这些最短路径, Dijkstra提出按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止

其中，从源点到顶点v的最短路径是所有最短路径中长度最短者 依最短路径的长度递增的次序求得各条路径 其中，从源点到顶点v的最短路径是所有最短路径中长度最短者 v1 v2 … 源点

路径长度最短的最短路径的特点 在这条路径上，必定只含一条弧，并且这条弧的权值最小

下一条路径长度次短的最短路径 的特点 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)

再下一条路径长度次短的最短 路径的特点 从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点 它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是 从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点

其余最短路径的特点 它或者是直接从源点到该点(只 含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点

10 100 1 30 10 4 50 60 2 3 20 Dijkstra逐步求解的过程 源点 终点 最短路径 路径长度 v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2) ,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60

1.引入辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点 v0到终点 vi 的最短路径的长度。初始状态： 若从源点v0到顶点 vi 有边, 则dist[i]为该边上的权值 若从源点v0到顶点 vi 无边, 则dist[i]为

2.假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过 S 中的顶点便可到达的那些顶点vx (vxV-S )的路径中的一条 3.每次求得一条最短路径后, 其终点vk 加入集合S，然后对所有的vi V-S，修改其 dist[i]值

Dijkstra算法中各辅助数组的最终结果 10 100 从表中读取源点0到终点v的最短路径的方法 : 举顶点4为例 path[4] = 2 path[2] = 3 path[3] = 0，反过来排列，得到路径 0, 3, 2, 4，这就是源点0到终点4的最短路径。 30 4 1 10 60 50 2 3 20

求每一对顶点之间的最短路径 弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径

若<vi,vj>存在，则存在路径{vi,vj} // 路径中不含其它顶点 若<vi,v1>,<v1,vj>存在，则存在路径{vi,v1,vj} // 路径中所含顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在， 则存在一条路径{vi, …, v2, …vj} // 路径中所含顶点序号不大于2 …

依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者