详细论述最短路径（迪杰斯特拉算法和弗洛依德算法）

一、迪杰斯特拉算法

通常用迪杰斯特拉算法求图中某一顶点到其他各个顶点的最短路径。

1、算法思想

设有两个集合S、T，集合S中存放图中已找到最短路径的顶点，集合T存放图中剩余顶点。初始状态时，集合S中只包含源点v0，然后不断地从集合T中选取到顶点v0路径最短长度的顶点vu并入到集合S中。集合S每并于一个新的顶点vu，都要修改顶点v0到集合T中顶点的最短路径长度。 不断重复此过程，直到集合T的顶点全部并入到S中。

2、算法执行过程

引入三个辅助数组dist[]、path[]和set[]。

dist[vi]表示当前已找到的从v0到vi的最短路径长度。它的初始状态为：若v0到vi有边，则dist[vi]为边上的权值，否则置为无穷。

path[vi]保存从v0到vi最短路径上vi的前一个顶点。它的初始状态为：若v0到vi有边，则path[vi] = v0，否则path[vi] = -1。

set[]为标识数组，set[vi] = 1则表示已经并入到S中，set[vi] = 0则表示还未并入最短路径。它的初始状态为：set[v0] = 1,其他全为0。

迪杰斯特拉算法的执行过程如下：

1）从当前的dist[]数组中选取最小值，假设为dist[vu]，则将set[vu]置为1，表示当前新并入的顶点是vu。

2）循环扫描图中的顶点，对每个顶点进行检测：

假设当前顶点为vj，检测set[vj]是否等于1，等于1则表示已经并入到S中，则不再进行任何操作。若等于0，则比较dist[vj]和dist[vu]+w的值，其中w为边vj和vu的权值。如果dist[vj]较大，则用新的路径长度更新旧的，并把vu加入路径中。

3）对前两个步骤循环n-1次（n为图的边数），即可得到v0到其余顶点的最短路径长度。

下面将以一个例子来体会迪杰斯特拉算法求解最短路径长度的过程。

对于下图所示的有向图，初始态为：

dist[0] = 0, dist[1] = 4, dist[2] = 6, dist[3] = 6,其余全为无穷

path[1] = 0, path[2] = 0, path[3] = 0,其余全为-1

set[0] = 1，其余全为0

1） 从通往其余顶点的路径中选出最短路径长度，即0—>1，长度为dist[1] = 4，因此将顶点1并入到最短路径中，set[1] = 1，结果如下图：

以1为中间点检测其他剩余的顶点2，3，4，5，6

（1）dist[2] = 6 > dist[1] + g[1][2] = 5，因此将dist[2]置为5，path[2]置为1

（2）dist[3] = 6 < dist[1] + g[1][3] = 无穷，因此dist[3]不变，path[3]不变

（3）dist[4] = 无穷 > dist[1] + g[1][4] = 11，将dist[4]置为11，path[4]置为1

（4）dist[5] = 无穷 = dist[1] + g[1][5] = 无穷，因此dist[5]不变，path[5]不变

（5）dist[6] = 无穷 = dist[1] + g[1][6] = 无穷，因此dist[6]不变，path[6]不变

（6）dist[3] = 6 < dist[1] + g[1][3] = 无穷，因此dist[3]不变，path[3]不变

2） 从通往剩余顶点的路径中选出最短的是0—>1—>2，长度为dist[2] = 5，因此将顶点2并入最短路径中，set[2] = 1 ,结果如下图所示：

以2为中间点检测剩余顶点3，4，5，6

（1）dist[3] = 6 < dist[2] + g[2][3] = 无穷，因此dist[3]不变，path[3]不变

（2）dist[4] = 11 = dist[2] + g[2][4] = 11，因此dist[4]不变，path[4]不变

（3）dist[5] = 无穷 > dist[2] + g[2][5] = 9，因此将dist[5]置为9，path[5]置为2

（4）dist[6] = 无穷 = dist[2] + g[2][6] = 无穷，因此dist[6]不变，path[6]不变

重复上述步骤，直到所有顶点并入到最短路径中 ，结果为：

3、算法代码

void Dijkstra(M g,int v int dist[],int path[]){int set[maxSize];int min , i , j , u;//初始化for(i = 0;i<g.n;i++){dist[i] = g,edges[v][i];set[i] = 0;if(g.edges[v][i] < INF) path[i] = v;else path[i] = -1;}set[v] = 1;path[v] = -1;for(i = 0;i<g.n-1;i++){min = INF;for(j = 0;j<g.n;j++){if(set[j] == 0&dist[j]<min){u = j;min = dist[j];}}set[u] = 1;//将选出的顶点并入最短路径for(j = 0;j<g.n;j++){if(set[j] == 0&&dist[u]+g.edges[u][j] < dist[j]){dist[j] = dist[u]+g.edges[u][j];path[j] = u;}}}
}//时间复杂度为O(n^2)

二、弗洛伊算法

迪杰斯特拉算法是求图中某一顶点到其余各顶点的最短路径，如果求图中任意一对顶点的最短路径，则通常用弗洛伊算法。

弗罗伊算法的求解步骤为：

1）设置两个矩阵A和Path，初始时将图的邻接矩阵赋值给A，将矩阵Path中的元素全部置为 -1

2）以顶点k为中间顶点，k取0~n-1(n为图的顶点数)，对图中所有顶点对进行如下检测：

如果A[ i ][ j ] > A[ i ][ k ] + A[ k ][ j ]，则将A[ i ] [ j ]改为A[ i ][ k ] + A[ k ][ j ]的值，将Path[ i ][ j ]改为k，否则不进行任何操作。

下面将将一个例子，如下图所示一个有向图：

对于上图，对应的邻接矩阵为：

初始时设置两个矩阵A和Path，矩阵A用来记录当前已经求得的任意两个顶点最短路径的长度，Path用来记录当前两个顶点间最短路径上要经过的中间点。

1）初始时有：

2)以0为中间点，参照上一步矩阵中的结果，检测的所有顶点对：{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}，假设当前所检测的顶点对位{i，j}，如果A[ i ][ j ] > A[ j ][ 0 ] + A[ 0 ][ j ]，则将A[ i ][ j ]改为[ j ][ 0 ] + A[ 0 ][ j ]的值，并将Path[ i ][ j ]改为0。经过检测与修改后，所得矩阵如下：

3）以1为中间点，参照上一步的结果，检测所有顶点对，其中A[ 0 ][ 2 ] > A[ 1 ][ 2 ] = 5 + 4 = 9，因此将A[ 0 ][ 2 ]改为9，Path[ 0 ][ 2 ]改为1。经过检测与修改后，所得矩阵如下：

重复上述步骤，得到最终的矩阵如下：

由矩阵A可以查出图中任意两个顶点之间的最短路径长度，如顶点1到顶点3的最短路径长度为A[ 1 ][ 3 ] = 2

由矩阵Path可以算出任意两点间最短路径上的顶点序列，如顶点1到顶点0最短路径可以按下面步骤求得：

（1）由Path[ 1 ][ 0 ] = 3，可知经过顶点3，把顶点3作为下一步起点

（2）由Path[ 3 ][ 0 ] = 2，可知经过顶点2，把顶点2作为下一步起点

（1）由Path[ 2 ][ 0 ] = -1，可知顶点2有到顶点0的边，求解结束

从顶点1到顶点0最短路径为1—> 3 —> 2 —> 0

void Floyd(M g , int Path[][maxSize]){int i , j , k;int A[maxSize][maxSize];//初始化for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){A[i][j] = g.edges[i][j];Path[i][j] = -1; } //检测与修改for(k=0;k<g.n;k++)for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){if(A[i][j] > A[i][k]+A[k][j]){A[i][j] = A[i][k]+A[k][j];Path[i][j] = k;}	}
}//时间复杂度为O(n^3)

写在最后

码字不易，点个赞或者评个论再走可好？