一、最短路径的概念：从有向图中某一顶点（起始顶点）到达另一顶点（终止顶点）的路径中，其权值之和最小的路径
二、算法一：Dijkstra算法
单源最短路径问题：给定一个带权有向图 D 与源点 v ，求从v 到 D 中其它顶点的最短路径。限定各边上的权值大于0。
如何求得这些路径？迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点 v 到其它各顶点的最短路径全部求出为止。
解决步骤描述：
- 设置辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点 v0到终点 vi的最短路径的长度；
- 初始状态：
2.1. 若从源点 v0 到顶点 vi有边：dist[i]为该边上的权值；
2.2. 若从源点 v0 到顶点 vi无边：dist[i]为∞。
根据以上描述，可以得到如下描述的算法：
假设用带权的邻接矩阵Edge[i][j]表示边(vi,vj)上的权值。若(vi,vj)不存在，则置Edge[i][j]为∞。S为已.找到从v出发的最短路径的终点的集合，它的初始状态为空集。
1.初始化： S ← {v0 };dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
2.找出最短路径所对应的点 K：dist[k] == min { dist[i] }, i ∈ V- S ;S ← S U { k };
3.对于每一个 i ∈ V- S 修改：dist[i] ← min{ dist[i],dist[k] + Edge[k][i] }；
4.判断：若 S = V, 则算法结束，否则转2。
算法的精髓：S 集内的顶点是已经找到最短路径的顶点，V0 到 w 的最短路径只能通过 S 集内的顶点,迪杰斯特拉算法的时间复杂度为O(n*n)。
算法实现
G: 网图;
v0: V0开始的顶点;
p[v]: 前驱顶点下标;
D[v]: 表示从V0到V的最短路径长度和;
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
k = 0;
int final[MAXVEX];
for(v=0; v<G.numVertexes; v++)
{
final[v] = 0;
(*D)[v] = G.arc[v0][v];
(*P)[v] = 0;
}
(*D)[v0] = 0;
final[v0] = 1;
(*P)[v0] = -1;
for(v=1; v<G.numVertexes; v++)
{
min=INFINITYC;
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (*D)[w]<min)
{
k=w;
min = (*D)[w];
}
}
final[k] = 1;
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
三、算法二：Floyd算法
所有顶点之间的最短路径：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi≠vj，要求求出vi与vj之间的最短路径和最短路径长度。
解决这个问题的一个方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。虽然能实现，但是明显实现起来比较复杂。
下面介绍一下由弗洛伊德提出的另一个算法。这个算法的时间复杂度也是O(n3),但形势上简单些。
弗洛伊德算法仍从图的带权邻接矩阵Edge[i][j]出发，其基本思想是：假设求顶点vi到vj的最短路径。如果从vi到vj有弧（无向图称为边），则从vi到vj存在一条长度为Edge[i][j]的路径，该路径不一定是最短路径，尚需n次试探。首先考虑路径（vi ，v0 ，vj）是否存在（即判别弧(vi ，v0 )和弧(v0 ，vj)是否存在）。如果存在,则比较(vi ，vj)和(vi ，v0 ，vj)的路径长度取长度较短者为从vi到vj的中间定点序号不大于0的最短路径。假如在路径上再增加一个顶点v1，也就是说，如果（vi ，…，v1）和（v1，…，vj）分别是当前找到的中间顶点的序号不大于0的最短路径,那么（vi ，…，v1，…，vj）就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进行试探。依次类推，若vi ，…，vk）和（vk，…，vj）分别是从vi到vk和从vk到vj中间顶点的序号不大于k-1的最短路径,则将（vi ，…，vk，…，vj）和已经找到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者是从vi到vj的中间顶点序号不大于k的最短路径。这样，经过n次比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。
定义一个 n 阶方阵序列：A(-1), A(0), …, A(n-1)
其中:A(-1)[i][j] = Edge[i][j]
A(k) [i][j] = min { A(k-1)[i][j],A(k-1)[i][k] + A(k-1)[k][j]}
k = 0, 1, …, n-1
A(0)[i][j]是从顶点vi到vj, 中间顶点是v0的最短路径的长度；
A(k) [i][j]是从顶点vi 到vj, 中间顶点的序号不大于k的最短路径的长度；
A(n-1)[i]j]是从顶点 vi 到 vj的最短路径长度。
算法实现
Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
Patharc 和 ShortPathTable 都是二维数组;
*/
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
(*D)[v][w]=G.arc[v][w];
(*P)[v][w]=w;
}
}
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}
网友评论