数据结构-最短路径（Dijkstra算法与Floyd算法）

介绍

对于网图来说，最短路径是指两顶点之间经过的边上权值之和最少的路径，其路径上第一个点记为源点，最后一个为终点。

计算最短路径有两个经典算法，即迪杰斯特拉（Dijkstra）算法与弗洛伊德（Floyd）算法。

Dijkstra算法

这个算法是从一个给定的顶点出发，不断计算更新此顶点到目标顶点的最短路径

假如有这样一张网图

如果我们要求顶点0到顶点1的最短距离，那无疑是1。由于1还与2，3相连，所以我们也可以求出0->1->2的距离为1+2=3，0->1->3距离为1+4=5；

但如果求从顶点0到顶点2的最短距离，由于边上都有权值，5是大于3的，所以0到2的最短距离是3；

同时，因为2与3,4相连，我们可以求得由此路径的0->1->2->3=3+1=4,0->1->2->4的距离为4+4=7；而这条路径上0到3的距离要小于上述0->1->3那条，则目前0到3的最短距离更新为4

... ...以此类推，不断基于已经求出的中途的最短距离，来更新到目标顶点的最短路径，这就是这个算法的核心思想

具体代码实现

	typedef struct{int vex[max];//顶点数组int arc[max][max];//带权边长int numN,numE;//顶点数及边数
}Mgraph;//用邻接矩阵存储整张图
int p[max];//储存最短路径下标数组
int d[max];//储存到各点的最短路径权值和
void SPDijkstra(Mgraph g,int v0){//传入图与起始顶点int m;int final[max];//记录从v0到i顶点的最短路径for (int i=0;i<g.numN;i++){final[i]=0;//初始化未未知最短路径的状态d[i]=g.arc[v0][i];//将所有与v0有连线的加上权值p[i]=-1;//初始化路径数组为-1}d[v0]=0;//v0至v0距离为0final[v0]=1;//标记v0至v0不需要求路径int k;for (int i=1;i<g.numN;i++){//从v1开始找起m=INT_MAX;for (int j=0;j<g.numN;j++){if (!final[j]&&d[j]<m){m=d[j];k=j;//记录距v0最短的带权路径顶点}}final[k]=1;//标记此顶点//开始更新最短距离for (int j=0;j<g.numN;j++){if (!final[j]&&m+g.arc[k][j]<d[j]){d[j]=m+g.arc[k][j];//更新v0到j的最短路径p[j]=k;//v0到j顶点的最短路径前驱是k}}}
}

Floyd算法

还是以此图为例

弗洛伊德算法常用于求取所有顶点至所有顶点的最短路径，它利用动态规划的方法，将顶点至顶点间的最短路径记录在一个二维数组中

在带权的邻接矩阵中，arc[i][j]记录的为i j之间的距离，如例图中arc[0][2]=5

但如果找一个与两个顶点都相连的中间节点，如1，计算得出arc[0][1]+arc[1][2]=1+2=3，这个值是小于5的，这条路径的距离就可以更新到矩阵中代替5的位置

利用这种算法进行重复迭代，对于每一对顶点i,j，遍历所有的中间节点k，检查是否存在一条路径比当前更短，如果是则更新矩阵中的最短距离。这样就可以的出两个个顶点之间的最短路径与最短距离。

代码实现如下

int p[max][max];//p数组记录路径，方便后续输出最短路径
int d[max][max];//记录最短距离
void SPFloyd(Mgraph g){for (int i=0;i<g.numN;i++){for (int j=0;j<g.numN;j++){d[i][j]=g.arc[i][j];//初始化为邻接矩阵p[i][j]=j;//初始化路径数组}}for(int k=0;k<g.numN;k++){for (int i=0;i<g.numN;i++){for (int j=0;j<g.numN;j++){if(d[i][j]>d[i][k]+d[k][j]){d[i][j]=d[i][k]+d[k][j];//更新最短距离p[i][j]=p[i][k];//更新路径，即要到j的最短路径中，j之前一个顶点为k}}}}
}