前言
最短路径也是数据结构与算法中常见的问题，不同于最小生成树，最短路径问题则是需要找出起点到终点之间路途最短的路径，属于路径规划范畴的问题了。本篇文章将介绍两种最短路径的算法。
示例：如下图所示，找出V0到V8两点间距离最短的路径。
示例
迪杰斯特拉[Dijkstra]算法
邻接矩阵如下图所示：
思路：
- 初始化三个数组，final数组用于记录V0到Vw之间最短路径是否有结果，final[w] = 1；D数组表示V0到某个顶点Vw的路径；P数组表示各个顶点的前驱顶点的下标。
- 从V1开始，V8结束，利用k为当前顶点下标，循环遍历，每一次循环判断当前顶点到其余顶点最小路径。首先判断final数组中是否已经有结果，final[w] = 1，则跳过，final[w] = 0,则比较此时V0-->Vw之间距离最小值 与 邻接矩阵中arc[k][w] 的和 D[w]的大小，取较小者设为D[w]的值。即V0到Vw的最短距离。（条件：
!final[0~9] && min + G.arc[k][w] < D[w]）
执行过程：
初始化三个数组，默认final数组全为0，D数组为邻接矩阵第一行数据，代表V0到连接顶点的已知距离（并非最小距离），P数组值全为0。
-
从0开始，则(D)[v0] = 0，V0到V0距离为0; final[v0] = 1，表示V0到V0没有路径; (P)[v0] = -1，V0到V0没有路径，所以前驱顶点下标为-1;
-
来到V1顶点，k = 1, min = 1, 首先判断final[0~9]的情况，再判断min + G.arc[k][w] < D[w]条件是否满足，满足则将对应P[w]位置的值设为k，即前驱顶点为V1。
-
按照以上步骤k范围[0~8]，min 为当前D[k]的值，然后进行比对，最终得到如下结果：
最终所有的顶点都经过了。此时final数组全为1，D数组中表示V0到其余顶点最短的路径值，P数组则是表示每个顶点的前驱顶点下标。
V0--->V3：4-->2-->1-->0最短路径值为7
V0--->V6:3-->4-->2-->1-->0最短路径值为10
代码实现
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status;
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];
/*10.1 创建邻近矩阵*/
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITYC;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*10.2 求得网图中2点间最短路径
Dijkstra 算法
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;
/*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
int final[MAXVEX];
/*1.初始化数据*/
for(v=0; v<G.numVertexes; v++)
{
//全部顶点初始化为未知最短路径状态0
final[v] = 0;
//将与V0 点有连线的顶点最短路径值;
(*D)[v] = G.arc[v0][v];
//初始化路径数组p = 0;
(*P)[v] = 0;
}
//V0到V0的路径为0
(*D)[v0] = 0;
//V0到V0 是没有路径的.
final[v0] = 1;
//v0到V0是没有路径的
(*P)[v0] = -1;
//2. 开始主循环,每次求得V0到某个顶点的最短路径
for(v=1; v<G.numVertexes; v++)
{
//当前所知距离V0顶点最近的距离
min=INFINITYC;
/*3.寻找离V0最近的顶点*/
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (*D)[w]<min)
{
k=w;
//w顶点距离V0顶点更近
min = (*D)[w];
}
}
//将目前找到最近的顶点置为1;
final[k] = 1;
/*4.把刚刚找到v0到v1最短路径的基础上,对于v1 与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
for(w=0; w<G.numVertexes; w++)
{
//如果经过v顶点的路径比现在这条路径长度短,则更新
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
//找到更短路径, 则修改D[W],P[W]
//修改当前路径的长度
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
int main(void)
{
printf("最短路径-Dijkstra算法\n");
int i,j,v0;
MGraph G;
Patharc P;
ShortPathTable D;
v0=0;
CreateMGraph(&G);
ShortestPath_Dijkstra(G, v0, &P, &D);
printf("最短路径路线:\n");
for(i=1;i<G.numVertexes;++i)
{
printf("v%d -> v%d : ",v0,i);
j=i;
while(P[j]!=-1)
{
printf("%d ",P[j]);
j=P[j];
}
printf("\n");
}
printf("\n最短路径权值和\n");
for(i=1;i<G.numVertexes;++i)
printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
printf("\n");
return 0;
}
弗洛伊德[Floyd]算法
这种算法的大致含义就是利用中间过顶点K，计算出顶点V到顶点W(W=[0~8])之间的最短路径，利用邻接矩阵G，比较D[v][w] 和 D[v][k] + D[k][w] 之间的大小，更新二维数组D，并且利用二维数组P记下此时的k,公式如下：
D[v][w] = min{ D[v][w], D[v][k] + D[k][w] }
利用实时更新的二维数组D和一个记录顶点下标k的二维数组P来记录算法中涉及的信息。
以上是D数组和P数组默认初始值。
演算过程
k = 0 , v 的范围[0~8], w的范围 [0~8], 意思就是以V0顶点为中转点，比较此时D[v][w] 与 D[v][0]+ D[0][w] 的大小，发现并没有任何变化，D[v][w] < （D[v][0]+ D[0][w]）
-
k = 1, v 的范围[0~8], w的范围 [0~8]，意思就是以V1顶点为中转点，比较此时D[v][w] 与 D[v][0]+ D[0][w] 的大小，一圈比较下来，得到如下结果：
k=1
如上图中的结果，相应的也需要更改P数组红色区域值为1，如下所示：
k=1 -
k 由 2 -> 8, v 的范围[0~8], w的范围 [0~8]，意思就是以V1顶点为中转点，比较此时D[v][w] 与 D[v][0]+ D[0][w] 的大小，由此循环比较，最终得到的最终结果如下：
最终结果
如上图最终结果可知，D数组第一行即V0到各个顶点的最小距离，结果与上方第一种方法结果一样：
那么V0到各个顶点最短距离求出来了，但是怎么知道V0到各个顶点最短距离是怎么走的，例如V0-V8 经过哪些顶点呢？
解答：以V0～V8为例，从P数组中看出，P[0][8] = 1, 说明经过顶点V1，将1替代0，P[1][8] = 2， 说明经过顶点2，再将2替代1得到P[2][8] = 4, 则表示经过顶点4，依次类推，最终经过定顶点情况为：V0->V1->V2->V4->V3->V6->V7->V8
代码实现
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* 11.1 构成邻近矩阵 */
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITYC;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* 11. 2
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;
/* 1. 初始化D与P 矩阵*/
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
/* D[v][w]值即为对应点间的权值 */
(*D)[v][w]=G.arc[v][w];
/* 初始化P P[v][w] = w*/
(*P)[v][w]=w;
}
}
//2.K表示经过的中转顶点
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
/*如果经过下标为k顶点路径比原两点间路径更短 */
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{
/* 将当前两点间权值设为更小的一个 */
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
/* 路径设置为经过下标为k的顶点 */
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}
int main(void)
{
printf("Hello,最短路径弗洛伊德Floyd算法");
int v,w,k;
MGraph G;
Patharc P;
ShortPathTable D; /* 求某点到其余各点的最短路径 */
CreateMGraph(&G);
ShortestPath_Floyd(G,&P,&D);
//打印所有可能的顶点之间的最短路径以及路线值
printf("各顶点间最短路径如下:\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=v+1; w<G.numVertexes; w++)
{
printf("v%d-v%d weight: %d ",v,w,D[v][w]);
//获得第一个路径顶点下标
k=P[v][w];
//打印源点
printf(" path: %d",v);
//如果路径顶点下标不是终点
while(k!=w)
{
//打印路径顶点
printf(" -> %d",k);
//获得下一个路径顶点下标
k=P[k][w];
}
//打印终点
printf(" -> %d\n",w);
}
printf("\n");
}
//打印最终变换后的最短路径D数组
printf("最短路径D数组\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d\t",D[v][w]);
}
printf("\n");
}
//打印最终变换后的最短路径P数组
printf("最短路径P数组\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d ",P[v][w]);
}
printf("\n");
}
return 0;
}
