一、最短路径问题的抽象
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径
- 这条路径就是两点之间的最短路径（Shortest Path）
- 第一个顶点为源点（Source）
- 最后一个顶点为终点（Destination）
二、问题分类
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。
- （有向）无权图
- （有向）有权图
多源最短路径问题：求任意两项顶点间的最短路径。
三、无权图的单源最短路算法
按照递增（非递减）的顺序找出到各个顶点的最短路
一层一层找点
1 /* 邻接表存储 - 无权图的单源最短路算法 */ 2 3 /* dist[]和path[]全部初始化为-1 */ 4 void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S ) 5 { 6 Queue Q; 7 Vertex V; 8 PtrToAdjVNode W; 9 10 Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */ 11 dist[S] = 0; /* 初始化源点 */ 12 AddQ (Q, S); 13 14 while( !IsEmpty(Q) ){ 15 V = DeleteQ(Q); 16 for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */ 17 if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */ 18 dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */ 19 path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */ 20 AddQ(Q, W->AdjV); 21 } 22 } /* while结束*/ 23 }
四、有权图的单源最短路算法
按照递增的顺序找出到各个顶点的最短路径（Dijkstra算法）
- 令S={源点S+已经确定了最短路径的顶点vi}
- 对任一未收录的顶点v，定义dist[v]为s到v的最短路进长度，但该路径仅经过s中的顶点。即路径{s->（Vi∈S）->v}的最小长度
- 若路径是按照递增（非递减）的顺序生成的，则
- 真正的最短路径必须只经过S中的顶点（为什么？）
- 每次从未收录的顶点中选一个dist最小的收录（贪心）
- 增加一个v进入s，可能影响另外一个w的dist值！
- dist[w] = min{dist[w], dist[v] + <v, w>的权重}
1 /* 邻接矩阵存储 - 有权图的单源最短路算法 */ 2 3 Vertex FindMinDist( MGraph Graph, int dist[], int collected[] ) 4 { /* 返回未被收录顶点中dist最小者 */ 5 Vertex MinV, V; 6 int MinDist = INFINITY; 7 8 for (V=0; V<Graph->Nv; V++) { 9 if ( collected[V]==false && dist[V]<MinDist) { 10 /* 若V未被收录，且dist[V]更小 */ 11 MinDist = dist[V]; /* 更新最小距离 */ 12 MinV = V; /* 更新对应顶点 */ 13 } 14 } 15 if (MinDist < INFINITY) /* 若找到最小dist */ 16 return MinV; /* 返回对应的顶点下标 */ 17 else return ERROR; /* 若这样的顶点不存在，返回错误标记 */ 18 } 19 20 bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S ) 21 { 22 int collected[MaxVertexNum]; 23 Vertex V, W; 24 25 /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */ 26 for ( V=0; V<Graph->Nv; V++ ) { 27 dist[V] = Graph->G[S][V]; 28 if ( dist[V]<INFINITY ) 29 path[V] = S; 30 else 31 path[V] = -1; 32 collected[V] = false; 33 } 34 /* 先将起点收入集合 */ 35 dist[S] = 0; 36 collected[S] = true; 37 38 while (1) { 39 /* V = 未被收录顶点中dist最小者 */ 40 V = FindMinDist( Graph, dist, collected ); 41 if ( V==ERROR ) /* 若这样的V不存在 */ 42 break; /* 算法结束 */ 43 collected[V] = true; /* 收录V */ 44 for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */ 45 /* 若W是V的邻接点并且未被收录 */ 46 if ( collected[W]==false && Graph->G[V][W]<INFINITY ) { 47 if ( Graph->G[V][W]<0 ) /* 若有负边 */ 48 return false; /* 不能正确解决，返回错误标记 */ 49 /* 若收录V使得dist[W]变小 */ 50 if ( dist[V]+Graph->G[V][W] < dist[W] ) { 51 dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */ 52 path[W] = V; /* 更新S到W的路径 */ 53 } 54 } 55 } /* while结束*/ 56 return true; /* 算法执行完毕，返回正确标记 */ 57 }
五、多源最短路算法
方法1：直接将单源最短路算法调用|V|遍
- T=O(|V|3+|E|x|V|) 对于稀疏图效果好
方法2：Floyd算法
T=O(|V|3) 对于稠密图效果好
Floyd算法
- Dk[i][j] = 路径{ i -> { l ≤ k } -> j }的最小长度
- D0, D1, …, D|V|-1[i][j]即给出了i到j的真正最短距离
- 最初的D-1是什么？
- 当Dk-1已经完成，递推到Dk时：
- 或者k ￠ 最短路径{ i -> { l ≤ k } -> j }，则Dk = Dk-1
- 或者k ￠ 最短路径{ i -> { l ≤ k } -> j }，则该路径必定由两段最短路径组成： Dk[i][j]=Dk-1[i][k]+Dk-1[k][j]
1 /* 邻接矩阵存储 - 多源最短路算法 */ 2 3 bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] ) 4 { 5 Vertex i, j, k; 6 7 /* 初始化 */ 8 for ( i=0; i<Graph->Nv; i++ ) 9 for( j=0; j<Graph->Nv; j++ ) { 10 D[i][j] = Graph->G[i][j]; 11 path[i][j] = -1; 12 } 13 14 for( k=0; k<Graph->Nv; k++ ) 15 for( i=0; i<Graph->Nv; i++ ) 16 for( j=0; j<Graph->Nv; j++ ) 17 if( D[i][k] + D[k][j] < D[i][j] ) { 18 D[i][j] = D[i][k] + D[k][j]; 19 if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */ 20 return false; /* 不能正确解决，返回错误标记 */ 21 path[i][j] = k; 22 } 23 return true; /* 算法执行完毕，返回正确标记 */ 24 }