弗洛伊德 Floyd 图顶点最短路径算法

1. 算法思想

1. 任意两个顶点的最短路径都是由若干个中间顶点间的最短路径组合而成的
   1. 即中间任意两顶点都必定是最短路径
   2. 任意两点的最短路径可以抽象成起点 ->中转 ->...-> 终点
2. 遍历每个顶点
   1. 再遍历每条边, 看看这个顶点替换掉该边原来的中转顶点, 是不是路径更短
      1. 如果是就让起点指向这个中转

2. 适用范围:

1. 相较Dijkstra算法, 效率较慢
2. 图中具有负数权值的边
3. 同时得到图中任意两个顶点的最短路径

3. 在C语言中的实现

梗概:

1. 该算法需要用到两个二维数组
   1. 一个用来保存目前的行下标到列下标的最短距离
   2. 另一个用来保存行下标到列下标的最短路径的下一步顶点
      1. 如下一步顶点就等于列下标, 则下一步就是终点了
      2. 如果下一步顶点不等于列下标, 则作为下一步的起点(列下标)
2. 标志性的三个for
   1. 最外层的for遍历所有顶点
   2. 内两层用来同时遍历距离二维数组和路径二维数组
3. 比较记录中的路径长度和经过新中转顶点的路径长度
   1. 如果新中转路径更短
   2. 则更新记录中的最短距离
   3. 再把这个中转顶点作为最短路径的下一步顶点 代码:

void ShortestPath_Floyd(int vernum, Graph *G,int Path[][vernum]){
    //Path为用来存放结果的二维数组,-1表示不存在路径
    int i,j,v;//v为中转顶点
    int Dist[vernum][vernum];//保存目前任意两结点最短距离
    //初始化
    for(i=0;i<vernum;++i){
        for(j=0;j<vernum;++j){
            Dist[i][j]=G->arcs[i][j].adj;
            Path[i][j]=-1;
        }
    }
    for(v=0;v<vernum;++v)
        for(i=0;i<vernum;++i)
            for(j=0;j<vernum;++j)
                if(Dist[i][v]+Dist[v][j]<Dist[i][j]){
                   Dist[i][j]=Dist[i][v]+Dist[v][j];
                   Path[i][j]=v; 
                }
}