Floyd算法--多源最短路径

╰+攻爆jí腚メ 2022-07-12 01:24 226阅读 0赞

在一个给定的图中求两个顶点的最短路径的算法一直是比较常用和比较重要的算法。主要的求最短路径的算法有Floyd算法、Dijkstra算法和Bellman-Ford算法等等，本篇我们先来看一下Floyd算法：

首先我们知道，要求一个图中两个顶点中的最短路径，除了计算出这两个顶点的直接路径，还可以借助其他的顶点作为“跳板”，
    来看看能不能使得这两点的路径变短，来看一个例子：

![这里写图片描述][SouthEast]

假设这是一个给定的无向图图，图中共有4个顶点（A、B、C、D），
    图中的边共有：A-->B(10)、A-->C(2)、C-->B(6)、C-->D(1)、D-->B(2)五条边（严格来说有10条边，因为是无向图），
    顶点C和顶点B相连：A-->C-->B的距离一共是8，明显比顶点A直接到顶点B更短。
    再观察一下，我们还可以发现顶点C和顶点D直接相连，D顶点和顶点B直接相连：A-->C-->D-->B的距离一共是5，又是一条更短的路径！
    之后我们找不到顶点A到顶点B还有比距离5更短的路径了，那么，在这个图中顶点A到顶点B的最短路径就是5

在上面的那个简单的例子中，求顶点A到顶点B的最短路径，我们正是利用了其他的顶点作为“跳板”，来寻找是否有更短的路径，Floyd算法的核心思想也正是这个：**借助图的其它顶点来求目标顶点之间的最短路径**  
对于上面的例子，假设顶点A为1号顶点，顶点B为2号顶点，顶点的总数为n，e\[n\]\[n\]为图的邻接矩阵。那么我们可以用代码来描述刚刚的过程：

for(int i = 1; i <= n; i++)
    {
        if(e[1][2] > e[1][i] + e[i][2])
        {
        
            /* 这段代码的意思是：循环遍历图中的所有顶点
            * 如果利用图中的其它顶点可以使得顶点A到顶点B的路径变短，
            * 那么更新顶点A到顶点B的最短路径
            */
            e[1][2] = e[1][i] + e[i][2]; 
        }
    }

对于上面的代码，其实当i等于1的时候是没有意义的：顶点A借助顶点A来尝试是否能使得顶点A到顶点B的最短路径变短（自己借助自己有什么意义呢），不过我们这里的重点并不在这，那么现在我们要求图中的所有顶点到其他顶点的最短路径该怎么办呢，按照刚刚的思路，我们可以大概的写出代码：

for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                if(e[j][k] > e[j][i] + e[i][k])
                {
        
                    e[j][k] = e[j][i] + e[i][k];
                }
            }
        }
    }

其实很好理解，就是在原来的基础上嵌套了一个双重循环，这个双重循环是为了遍历图中的任意两个顶点，然后再利用最外面的一重循环来寻找最短路径，整个代码理解起来就是：**借助前 i 个顶点来寻找图中的任意两个定点的最短路径。**  
Ok， 其实这就是Floyd算法的核心代码，如果你把不需要的大括号去掉（这里只是为了代码美观），你会发现这个算法只有5行！

下面给出完整的Floyd代码：

#include <iostream>
    using namespace std;
    const int inf = 999999999;  // 模拟无穷大（表示图的两个顶点没有直接相连）
    const int N = 1000; // 图的顶点个数最多为1000个
    
    int e[N][N];    // 图的邻接矩阵
    
    int main()
    {
        int n, m;  // 图的顶点个数和边的条数(其实叫度的数目会更好)
        cin >> n >> m;
        for(int i = 1; i <= n; i++) // 初始化图
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == j)
                {
                    e[i][j] = 0;
                }
                else
                {
                    e[i][j] = inf;
                }
            }
        }
        int x, y, w;    // 记录图的每一条边的信息
        for(int i = 1; i <= m; i++)
        {
            cin >> x >> y >> w;
            e[x][y] = e[y][x] = w;
        }
    
        for(int i = 1; i <= n; i++) // Floyd算法核心代码
        {
            for(int j = 1; j <= n; j++)
            {
                for(int k = 1; k <= n; k++)
                {
                    if(e[j][k] > e[j][i] + e[i][k])
                    {
                        e[j][k] = e[j][i] + e[i][k];
                    }
                }
            }
        }
    
        for(int i = 1; i <= n; i++) // 输出算法结束后的图的邻接矩阵信息
        {
            for(int j = 1; j <= n; j++)
            {
                cout.width(4);
                cout << e[i][j] << " ";
            }
            cout << endl;
        }
    
        return 0;
    }

输入我们上面的例子数据，运行结果：  
![这里写图片描述][SouthEast 1]  
Yes，完成，我们可以检验一下图中的数据是否符合，确实是图中所有两个顶点之间的最短路径。各位小伙伴可以自行检验一下。  
那么Floyd算法的时间复杂度呢，在这个代码中算法的时间复杂度是O(N^3)，相比其他最短路算法，还是比较高的，但是这个算法可以求多源最短路径，而且代码相对简单，所以这个算法还是较优的。  
如果博客中有什么不正确的地方，还请多多指点。  
谢谢观看。。。

[SouthEast]: /images/20220711/d703bdebb2d04c9bb5db50a4c2b451d6.png
[SouthEast 1]: /images/20220711/c61a4f56b0e1485b937e458e62179bbb.png