最短路径(Floyd算法）

声明：图片及内容基于https://www.bilibili.com/video/BV1oa4y1e7Qt?from=articleDetail

多源最短路径的引入

 

Floyd算法 原理

加入a：

加入b：

加入c：

数据结构

核心代码

Floyd()

void MGraph::Floyd(){ for(int i=0;i<vertexNum;i++){ for(int j=0;j<vertexNum;j++){ dist[i][j]=arc[i][j]; //dist数组初始化 if(dist[i][j]!=INFINIT&&dist[i][j]!=0) //dist为INFINIT则无路径，dist为0则指向自己 path[i][j]=vertex[i]+vertex[j]; //path数组初始化 else path[i][j]=""; //不符合则path为空串 } } for(int k=0;k<vertexNum;k++){ //k个顶点循环k次 for(int i=0;i<vertexNum;i++){ //k每循环一次，要更新dist和path数组 for(int j=0;j<vertexNum;j++){ if(dist[i][k]+dist[k][j]<dist[i][j]){ dist[i][j]=dist[i][k]+dist[k][j]; //这里两个path拼接的时候，第一个字符串的最后一个字符和第二个字符串的第一个字符重复 //用substr去除第一个字符串的最后一个字符 string tmp=path[i][k].substr(0,path[i][k].length()-1); path[i][j]=tmp+path[k][j]; } } } } displayDist(); displayPath(); }