图算法之Floyd算法

  最近在翻看以前写的文章的时候，发现图这一块还漏了一两个经典的算法。接下来，小编将先把这些相关的算法做一个分享，再继续把背包系列有关的问题做一个经验总结。
一、绪论
  在获取单源正权值最短路径时，我们会用Dijkstra算法来求最短路径【小编前面文章有分享过，小伙伴们可以去翻翻看了解了解】，并且算法的思想很简单——贪心算法:每次确定最短路径的一个点然后维护（更新）这个点周围点的距离加入预选队列，等待下一次的抛出确定。虽然思想很简单，实现起来是非常复杂的，我们需要邻接矩阵(表)储存长度，需要优先队列(或者每次都比较)维护一个预选点的集合。还要用一个bool数组标记是否已经确定、还要其他相关的程序。总之，Dijkstra算法的思想上是很容易接受的，但是实现上其实是非常麻烦的。但是单源最短路径没有更好的办法，复杂度也为O（n²）;而在n节点多源最短路径中,如果从Dijkstra算法的角度上，只需要将Dijkstra封装，然后执行n次Dijkstra算法即可,复杂度为O(n³)。
  但是这样感觉很臃肿，代码量巨大，占用很多空间内存。有没有啥方法能够稍微变变口味呢？
  答案当然是有的，这就是小编今天要分享的多源最短路径算法，也就是Floyd算法。
二、算法简介
  Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。动态规划的思想小编在前面的文章中也有分享过，小伙伴们可以翻翻前面的内容看一看。
  简单的说就是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(n³)，空间复杂度为O(n²)。
三、算法核心思想
  对于一个图来说，从任意节点i到任意节点j的最短路径不外乎2种可能，第1种是直接从i到j，第2种是从i经过若干个节点k到j。所以，我们假设distance(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查distance(i,k) + distance(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置distance(i,j) = distance(i,k) + distance(k,j)，这样一来，当我们遍历完所有节点k，distance (i,j)中记录的便是i到j的最短路径的距离。
  算法步骤：
  （1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　
  （2）对于每一对顶点 i 和 j，看看是否存在一个顶点 k 使得从 i 到 k 再到 j 比己知的路径更短。如果是更新它。
  给出矩阵，其中矩阵distance是邻接矩阵，而矩阵path记录i，j两点之间最短路径所必须经过的点，可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径，也可以用于求两顶点之间最短路径。
  状态转移方程：

四、代码实现

template <class T, class E>
void  GraphMatrix<T, E>::Floyd()
{
    //可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题。
    int distance[numVertices][numVertices];//记录顶点间的最小路径值
    int path[numVertices][numVertices];//记录对应点的最小路径的前驱点，例如path[1][3] = 2 说明顶点1到顶点3的最小路径要经过2 
    //初始化floyd算法的两个矩阵
    for (int i = 0; i < numVertices; i++) {
        for(int j = 0; j < numVertices; j++){
            path[i][j] = -1;
            distance[i][j] = Edge[i][j];
        }
        
    }
     //这里是弗洛伊德算法的核心部分 
    //k为中间点 
    for(int k = 0; k < numVertices; k++){
        //i为起点 
        for(int i = 0 ; i < numVertices; i++){
            //j为终点 
            for(int j =0; j < numVertices; j++){
                if(distance[i][j] > (distance[i][k] + distance[k][j]) && distance[i][k]!= maxWeight && distance[k][j]!= maxWeight){
                    distance[i][j] = distance[i][k] + distance[k][j];//更新最小路径 
                    path[i][j] = k;//更新最小路径中间顶点 
                }
            }
        }
    }
    /*for(int i = 0 ; i < numVertices; i++){ 
        for(int j =0; j < numVertices; j++){
            cout<< distance[i][j]<<' ';
        }
        cout<<endl;
    }*/
    for(int i = 0 ; i < numVertices; i++){ 
        for(int j =0; j < numVertices; j++){
            if(distance[i][j]==maxWeight){
                cout<<"没有路可以从"<<getValue(i)<<"走到"<<getValue(j)<<endl;
            }
            if(distance[i][j]!=maxWeight && i!=j){
                cout<<getValue(i)<<"到"<<getValue(j)<<"的最短路径为：";
                int k=path[i][j];
                cout<<getValue(i); 
                while(k != j && k!=-1){
                    cout<<"->"<<getValue(k);//打印中间点
                    k= path[k][j]; 
                }
                cout<<"->"<<getValue(j)<<"-----最短距离为："<<distance[i][j]<<endl;
            }       
        }
    }
}

  算法的具体图解这里小编不做过多解释了，之前分享的图算法源码还少了一两个算法，今天补充了一个，接下来补充完整我会更新分享给大家。