【算法】Floyd-Warshall算法（任意两点间的最短路问题）（判断负圈）

骑猪看日落 2023-06-01 14:57 16阅读 0赞

## 问题 ##

求解任意两点间最短路问题也叫多源最短路径问题。

## 可解决途径 ##

一种方法是把图中每个点当做源点重复算n次***Dijkstra 算法***（Dijkstra是求单源最短路径的算法），时间复杂度O（n^3），据说可以优化成O（n^2logn）。  
另一种方法时最经典的算法***Floyd算法***，时间复杂度也是O（n^3），但是关键代码只有5行，适合时间要求不苛刻的时候编写。

## Floyd算法基本思想 ##

Floyd算法本质上是一个动态规划算法。对于每个顶点k，枚举其他两个顶点i和j，若i和j之间的距离大于i到k加上k到j的距离，那么更新i到j之间的距离。

【注】Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。（这句话摘自书上，本人并未深刻理解，若有大佬理解，望指教一二）

## 基本操作 ##

d\[k\]\[i\]\[j\] 表示 顶点i 经过顶点k 到顶点j 的最短路径长度。

分两种情况讨论：

1.  经过顶点k, d\[k\]\[i\]\[j\] = d\[k-1\]\[i\]\[j\]。 即等于只用前k-1个顶点时的最短路径
2.  不经过顶点k, d\[k\]\[i\]\[j\] = d\[k-1\]\[i\]\[k\] + d\[k-1\]\[k\]\[j\]。 即等于i离k的最路路径+k离j的最短路径。

可以得到递推式 d\[k\]\[i\]\[j\] = min( d\[k-1\]\[i\]\[j\] , d\[k-1\]\[i\]\[k\] + d\[k-1\]\[s\]\[k\] );

## 还可优化 ##

由于第k层只与k-1层相关，也可以用二维表示：  
![1218254-20190830131309830-1815284301.png][]  
（本图来自知乎，放在此处便于大家理解，侵删）  
d\[i\]\[j\] = min( d\[i\]\[j\] , d\[i\]\[k\] + d\[k\]\[j\] );

精简版算法模板：

#include <bits\stdc++.h>
    using namespace std;
    #define INF 2147483647
    #define MAX_V 1000
    #define MAX_E 2000 
    
    int d[MAX_V][MAX_V]; // d[u][v]表示边u->v的距离（不存在时设为INF，d[i][i] = 0） 
    int V;             //  顶点数 
    void warshall_floyd(){
        
        for(int k = 0;k < V; k++){
            for(int i = 0;i < V; i++){
                for(int j = 0;j < V; j++){
                    if(i != j && i != k && j != k)
                        if(d[i][k] != INF && d[k][j] != INF) //INF与正数相加会溢出
                            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
    int main(){
    }

转载于:https://www.cnblogs.com/zhangjiuding/p/11434467.html

[1218254-20190830131309830-1815284301.png]: /images/20230601/205785d11cbf4082a63172fcb5dc8e14.png