图的最短路径
之前我们说过图的存储、图的遍历和图的最短路径，并用代码和不同的方法去实现；这次我们同样采用两种方法去实现图的最短路径求解。
首先明白一点：求图的最短路径问题，不需要所有顶点都经过一次，而是求两点之间经过顶点权值和的最小值。
下面我将介绍Dijkstra算法和Floyd算法去求图的最短路径问题。
Dijkstra算法
这个算法的核心思想就是利用两个数组，一个数组记录v0到其他顶点的最短路径的权值和，一个数组记录与当前节点的上一个节点相连的顶点；那么如何实现两个数组呢？
以下面的图为例
15889942211197.png
我们这里再用一个数组记录当前顶点是否被记录
final记录各顶点是否被记录
D数组记录v0到其他顶点的权值和
P数组记录当前顶点的前驱顶点
记录第一个顶点时，我们需要先进行初始化:
final[0] = 1，D[0] = 0,p[0] = -1;
从第二个顶点开始，我们先用D数组记录与第一个顶点相连的权值
D[0] = 0
D[1] = 1
D[2] = 5
然后判断min+arc[0][1]或min+arc[0][2]的值是否小于D[1],D[2]的值的大小
从v0到其他任一一个顶点的权值和都是根据上一个顶点的权值和加上与该顶点相连的权值和最小的，当到其中一个顶点权值的和小于记录的最小和，那么就替换
代码
图的定义、数组定义，图的数据存储代码
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
//图的存储
typedef struct {
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes,numEdges;
}MGraph;
//用于存储最短路径下标的数组
typedef int Patharc[MAXVEX];
//用于存储到个点最短路径权值的和
typedef int ShortPath[MAXVEX];
void CreateMGraph(MGraph *G){
int i,j;
G->numEdges = 15;
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 = 0; j<G->numVertexes; j++) {
G->arc[j][i] = G->arc[i][j];
}
}
}
Dijkstra算法核心代码
/* 求得网图中2点间最短路径
Dijkstra 算法
G: 网图;
v0: V0开始的顶点;
p[v]: 前驱顶点下标;
D[v]: 表示从V0到V的最短路径长度和;
*/
void ShortPath_Dijkstra(MGraph G,int v0,Patharc *p,ShortPath *D){
int v,w,k,min;
k = 0;
/*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
int final[MAXVEX];
//初始化数据
for (v = 0; v<G.numVertexes; v++) {
//全部顶点初始化为未知最短路径状态
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;
//开始主循环，每次求得v0到某个顶点的最短距离
for (v = 1; v<G.numVertexes; v++) {
//当前所知距离v0顶点最近的距离
min = INFINITYC;
//寻找离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;
//把刚刚找到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;
}
}
}
}
实现函数的调用和数据的打印输出
p数组记录的是与当前顶点相连的上一个顶点，通过顶点下标值对应p数组的值来找到路径最短所经历过的顶点
int main(int argc, const char * argv[]) {
// insert code here...
printf("最短路径-Dijkstra算法!\n");
int i,j,v0;
MGraph G;
Patharc P;
ShortPath D;
v0=0;
CreateMGraph(&G);
ShortPath_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;
}
打印结果
最短路径-Dijkstra算法!
最短路径:
(v0 -> V1) : 1 0
(v0 -> V2) : 2 1 0
(v0 -> V3) : 3 4 2 1 0
(v0 -> V4) : 4 2 1 0
(v0 -> V5) : 5 4 2 1 0
(v0 -> V6) : 6 3 4 2 1 0
(v0 -> V7) : 7 6 3 4 2 1 0
(v0 -> V8) : 8 7 6 3 4 2 1 0
最短路径权值和
(v0 -> v1) : 1
(v0 -> v2) : 4
(v0 -> v3) : 7
(v0 -> v4) : 5
(v0 -> v5) : 8
(v0 -> v6) : 10
(v0 -> v7) : 12
(v0 -> v8) : 16
Program ended with exit code: 0
Floyd算法
这个算法理解起来比较繁琐，但是代码很短。
这个算法可以记录任意一个顶点与其他顶点相连的最短路径和所经历的顶点，因此，D数组和p数组都使用的是二维数组。
D数组开始存储的就是图的邻接矩阵的所有元素，P数组存储的每一行都是顶点的下标。
其实D数组的第一次记录的是D[n][1]（顶点数） 到 D[1][n]（n<顶点数）的权值和
第二次记录的是D[n][2]（顶点数） 到 D[2][n]（n<顶点数）的权值和
第三次记录的是D[n][3]（顶点数） 到 D[3][n]（n<顶点数）的权值和
……
第n次记录的是D[n][n]（顶点数） 到 D[n][n]（n<顶点数）的权值和
k=1 V=0 W=[0~8] 算法执行过程分析
D[0][0] = 0, D[0][1] + D[1][0] = 0, 所以不更新;
D[0][1] = 1, D[0][1] + D[1][1] = 1, 所以不更新
D[0][2] = 5, D[0][1] + D[1][2] = 1 + 3 = 4, 因为4<5, 所以更新D[0][2] = 4;
D[0][3] = ∞, D[0][1] + D[1][3] = 1+7 = 8; 所以8<∞, 所以更新D[0][3] = 8;
D[0][4] =∞, D[0][1] + D[1][4] = 1+5= 6; ,所以6<∞,所以更新D[0][4] = 6;
D[0][5] =∞, D[0][1] + D[1][5] =1+∞; 所以不更新;
D[0][6] =∞, D[0][1] + D[1][6] =1+∞; 所以不更新;
D[0][7] =∞, D[0][1] + D[1][7] =1+∞; 所以不更新;
D[0][8] =∞, D[0][1] + D[1][8] =1+∞; 所以不更新;
k=1 V=1 W=[0~8] 算法执行过程分析
D[1][0] = 1, D[1][1] + D[1][0] = 1, 所以不更新;
D[1][1] = 0, D[1][1] + D[1][1] = 0, 所以不更新
D[1][2] = 3, D[1][1] + D[1][2] = 0 + 3 = 3 , 所以不更新
D[1][3] = 7, D[1][1] + D[1][3] = 0+7 = 7; 所以不更新
D[1][4] = 5, D[1][1] + D[1][4] = 0+5= 5;所以不更新
D[1][5] =∞, D[1][1] + D[1][5] =0+∞; 所以不更新;
D[1][6] =∞, D[1][1] + D[1][6] =0+∞; 所以不更新;
D[1][7] =∞, D[1][1] + D[1][7] =0+∞; 所以不更新;
D[1][8] =∞, D[1][1] + D[1][8] =0+∞; 所以不更新;
……
k=1 V=8 W=[0~8] 算法执行过程分析
D[8][0] = ∞, D[8][1] + D[1][0] = ∞+1; 所以不更新;
D[8][1] = ∞, D[8][1] + D[1][1] = ∞+0; 所以不更新
D[8][2] = ∞, D[8][1] + D[1][2] = ∞ + 3 ; 所以不更新;
D[8][3] = ∞, D[8][1] + D[1][3] = ∞+7 ; 所以不更新
D[8][4] = ∞, D[8][1] + D[1][4] = ∞+5; 所以不更新;
D[8][5] = ∞, D[8][1] + D[1][5] =∞+∞; 所以不更新;
D[8][6] = 7, D[8][1] + D[1][6] =∞+∞; 所以不更新;
D[8][7] = 4, D[8][1] + D[1][7] =∞+∞; 所以不更新;
D[8][8] = 0, D[8][1] + D[1][8] =∞+∞; 所以不更新;
从结构可以看出，需要遍历三层循环去实现这个算法
代码
图的结构设计和存储数组，图的数据存储和之前的一样，这边不再写了
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
//图的存储
typedef struct {
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes,numEdges;
}MGraph;
//用于存储最短路径下标的数组
typedef int Patharc[MAXVEX][MAXVEX];
//用于存储到个点最短路径权值的和
typedef int ShortPath[MAXVEX][MAXVEX];
/*
Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
Patharc 和 ShortPathTable 都是二维数组;
*/
void ShortPath_Floyd(MGraph G,Patharc *P,ShortPath *D){
int v,w,k;
//初始化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;
}
}
//k表示经过中转顶点
for (k = 1; 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];
}
}
}
}
}
函数的调用和打印输出,函数的调用和Dijkstra算法的函数调用意思差不多，读者自行理解
int main(int argc, const char * argv[]) {
// insert code here...
printf("最短路径Floyd算法!\n");
int v,w,k;
MGraph G;
Patharc P;
ShortPath D;
CreateMGraph(&G);
ShortPath_Floyd(G, &P, &D);
//打印所有可能的顶点之间的最短路径以及路线值
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");
}
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");
}
printf("最短路径P数组\n");
for (v = 0; v<G.numVertexes; v++) {
for (w = 0; w<G.numVertexes; w++) {
printf("%d\t",P[v][w]);
}
printf("\n");
}
return 0;
}
输出打印
最短路径Floyd算法!
V0-V1 weight: 1 path: 0 -> 1
V0-V2 weight: 4 path: 0 -> 1 -> 2
V0-V3 weight: 7 path: 0 -> 1 -> 2 -> 4 -> 3
V0-V4 weight: 5 path: 0 -> 1 -> 2 -> 4
V0-V5 weight: 8 path: 0 -> 1 -> 2 -> 4 -> 5
V0-V6 weight: 10 path: 0 -> 1 -> 2 -> 4 -> 3 -> 6
V0-V7 weight: 12 path: 0 -> 1 -> 2 -> 4 -> 3 -> 6 -> 7
V0-V8 weight: 16 path: 0 -> 1 -> 2 -> 4 -> 3 -> 6 -> 7 -> 8
V1-V2 weight: 3 path: 1 -> 2
V1-V3 weight: 6 path: 1 -> 2 -> 4 -> 3
V1-V4 weight: 4 path: 1 -> 2 -> 4
V1-V5 weight: 7 path: 1 -> 2 -> 4 -> 5
V1-V6 weight: 9 path: 1 -> 2 -> 4 -> 3 -> 6
V1-V7 weight: 11 path: 1 -> 2 -> 4 -> 3 -> 6 -> 7
V1-V8 weight: 15 path: 1 -> 2 -> 4 -> 3 -> 6 -> 7 -> 8
V2-V3 weight: 3 path: 2 -> 4 -> 3
V2-V4 weight: 1 path: 2 -> 4
V2-V5 weight: 4 path: 2 -> 4 -> 5
V2-V6 weight: 6 path: 2 -> 4 -> 3 -> 6
V2-V7 weight: 8 path: 2 -> 4 -> 3 -> 6 -> 7
V2-V8 weight: 12 path: 2 -> 4 -> 3 -> 6 -> 7 -> 8
V3-V4 weight: 2 path: 3 -> 4
V3-V5 weight: 5 path: 3 -> 4 -> 5
V3-V6 weight: 3 path: 3 -> 6
V3-V7 weight: 5 path: 3 -> 6 -> 7
V3-V8 weight: 9 path: 3 -> 6 -> 7 -> 8
V4-V5 weight: 3 path: 4 -> 5
V4-V6 weight: 5 path: 4 -> 3 -> 6
V4-V7 weight: 7 path: 4 -> 3 -> 6 -> 7
V4-V8 weight: 11 path: 4 -> 3 -> 6 -> 7 -> 8
V5-V6 weight: 7 path: 5 -> 7 -> 6
V5-V7 weight: 5 path: 5 -> 7
V5-V8 weight: 9 path: 5 -> 7 -> 8
V6-V7 weight: 2 path: 6 -> 7
V6-V8 weight: 6 path: 6 -> 7 -> 8
V7-V8 weight: 4 path: 7 -> 8
最短路径D数组
0 1 4 7 5 8 10 12 16
1 0 3 6 4 7 9 11 15
4 3 0 3 1 4 6 8 12
7 6 3 0 2 5 3 5 9
5 4 1 2 0 3 5 7 11
8 7 4 5 3 0 7 5 9
10 9 6 3 5 7 0 2 6
12 11 8 5 7 5 2 0 4
16 15 12 9 11 9 6 4 0
最短路径P数组
0 1 1 1 1 1 1 1 1
0 1 2 2 2 2 2 2 2
1 1 2 4 4 4 4 4 4
4 4 4 3 4 4 6 6 6
2 2 2 3 4 5 3 3 3
4 4 4 4 4 5 7 7 7
3 3 3 3 3 7 6 7 7
6 6 6 6 6 5 6 7 8
7 7 7 7 7 7 7 7 8
Program ended with exit code: 0
