最短路径：对于非网图来说，最短路径指两顶点之间经过的边数最少的路径。而对于网图来说，最短路径指的是两顶点之间经过的边上权值之和最少的路径。
这里介绍两种网图的最短路径算法：迪杰斯特拉算法（Dijkstra）和弗洛伊德算法（Floyd）。
Dijkstra算法：
算法并不是一下子就求出v0到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求出更远顶点的最短路径，最终得到你要的结果。
代码：
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes,numEdges; }MGraph; typedef int Patharc[MAXVEX]; /* 用于存储最短路径下标的数组 */ typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */ /* 构件图 */ 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] = INFINITY; } } 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]; } } } /* Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */ /* P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */ void ShortestPath_Dijkstra(MGraph G,int v0,Patharc *P,ShortPathTable *D) { int v,w,k,min; int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */ for(v=0; v<G.numVertexes; v++) /* 初始化数据 */ { final[v] = 0; /* 全部顶点初始化为未知最短路径状态 */ (*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */ (*P)[v] = -1; /* 初始化路径数组P为-1 */ } (*D)[v0] = 0; /* v0至v0路径为0 */ final[v0] = 1; /* v0至v0不需要求路径 */ /* 开始主循环，每次求得v0到某个v顶点的最短路径 */ for(v=1; v<G.numVertexes; v++) { min=INFINITY; /* 当前所知离v0顶点的最近距离 */ for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */ { if(!final[w] && (*D)[w]<min) { k=w; min = (*D)[w]; /* w顶点离v0顶点更近 */ } } final[k] = 1; /* 将目前找到的最近的顶点置为1 */ 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) { 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 : ",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]); return 0; }
结果：
Floyd算法：
该算法完成了所有顶点到所有顶点的最短路径计算。
首先的准备两个矩阵D-1和P-1，D-1是网图的邻接矩阵，P-1初设为P[i][j]=j这样的矩阵，它主要用来存储路径。
得到D-1和P-1后，由表达式：D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}得到D0和P0：
依次类推可以得到D1和P1，...D8和P8：
...
以v0到v8为例，P[0][8]=1，得到要经过顶点v1，然后将1取代0得到P[1][8]=2，说明要经过v2，然后将2取代1得到P[2][8]=4，说明要经过4，然后将4取代2得到P[4][8]=3，说明要经过v3，...，这样很容易推导出最终的最短路径值为v0->v1->v2->v4->v3->v6->v7->v8。
代码：
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 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]; /* 构件图 */ 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] = INFINITY; } } 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]; } } } /* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ void ShortestPath_Floyd(MGraph G,ShortPathTable *D) { int v,k; for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */ { for(w=0; w<G.numVertexes; ++w) { (*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */ (*P)[v][w]=w; /* 初始化P */ } } 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]) {/* 如果经过下标为k顶点路径比原两点间路径更短 */ (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */ (*P)[v][w]=(*P)[v][k];/* 路径设置为经过下标为k的顶点 */ } } } } } int main(void) { int v,k; MGraph G; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ CreateMGraph(&G); ShortestPath_Floyd(G,&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,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 ",P[v][w]); } printf("\n"); } return 0; }
结果：
比较：
1，算法时间复杂度都是O（n^3）；
2，如果需要求所有顶点到所有顶点的最短路径时，Floyd算法是不错的选择；
3，在这里求最短路径的两个算法举例都是无向图，但它们对有向图依然有效，因为二者的差异仅仅是邻接矩阵是否对称而已。
原文链接：https://www.f2er.com/datastructure/382721.html