一、迪杰斯特拉算法
通常用迪杰斯特拉算法求图中某一顶点到其他各个顶点的
最短路径
。
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)
写在最后
码字不易，点个赞或者评个论再走可好？