前言

image

本篇文章我將向大家介紹求解最短路徑的三種經(jīng)典算法——Dijkstra 算法蓝厌，Bellman-Ford 算法以及 Floyd-Warshall 算法。

Dijkstra 算法

最短路徑

最短路徑問題是圖論研究領(lǐng)域中的一個經(jīng)典算法問題违施，旨在尋找圖中兩節(jié)點之間的最短路徑严里。

image

譬如上圖為一個無向有權(quán)圖燕偶，節(jié)點 0 到節(jié)點 3 的最短路徑為 ：

0 -> 2 -> 1 -> 3

其路徑長度為：5缝龄。

研究最短路徑算法具有哪些意義呢？或者說最短路徑算法可以解決哪些問題胶坠？

我們知道君账，在生活中，地鐵是我們重要的出行工具之一沈善。當(dāng)我們在地鐵售票處或是軟件上輸入了出發(fā)地與目的地后乡数，手機軟件就會給我們一個耗費最小或時間最短的最佳出行方案椭蹄，導(dǎo)航軟件這個功能的實現(xiàn)實際上就是一個最短路徑算法的具體應(yīng)用。

image

研究最短路徑算法旨在解決出行問題净赴，旅游問題塑娇，工程耗費等問題，在計算機科學(xué)劫侧，運籌學(xué)，地理信息科學(xué)中都具有重大意義哨啃。

Dijkstra 算法

Dijkstra 算法是求解單源最短路的經(jīng)典算法之一烧栋，是由荷蘭計算機科學(xué)家 Dijkstra 在 1956 年發(fā)明的算法。

使用 Dijkstra 算法的前提條件是圖中不能有負(fù)權(quán)邊拳球。在我介紹完 Dijkstra 算法的思路以后审姓，相信大家也就能夠明白，為什么圖中不能包含負(fù)權(quán)邊是 Dijkstra 算法的前置條件了祝峻。不過這一個前置條件并不會影響我們求解的絕大部分問題魔吐，譬如拿上面的求解耗費最小的地鐵線路來舉例，如果圖中的每一條邊的權(quán)值代表從一個節(jié)點到另一個節(jié)點耗費的金額莱找，那么這個金額的大小一定是大于 0 的酬姆。所以說， Dijkstra 算法即便不能處理帶有負(fù)權(quán)邊的圖奥溺，但其仍然能夠解決最短路徑這個研究領(lǐng)域中的絕大部分問題辞色。

接下來，我們來看一下 Dijkstra 算法的具體思路：

image

上圖中浮定，源點為 0相满，表格 dis 表示的是從源點到各點的最短路徑。因為最開始我們并不知道源點到各點的最短路徑是多少桦卒，所以初始值我們使用 來表示立美，而源點到源點的最短路徑則已經(jīng)確定，其值為 0方灾。

我們從源點開始建蹄，找到了源點相鄰的節(jié)點（1，2）迎吵，邊 0-1 的權(quán)為 4躲撰，邊 0-2 的權(quán)為 2，因為他們的值要比當(dāng)前的 dis 數(shù)組中的值還要小击费，所以我們更新 dis 數(shù)組拢蛋，將 dis[1] 更新為 4,dis[2] 更新為 2，而剩余的節(jié)點的權(quán)仍然保持為 蔫巩。此時谆棱，我們可以確定快压，當(dāng)前這些未確定最短路的節(jié)點中，值最小的就是從源到該點的最短路垃瞧。

這么說可能比較繞蔫劣，我們通過圖來直觀地看一下這個過程：

首先找到已經(jīng)確定最短路的節(jié)點，在圖中就是我使用黃色標(biāo)注出來的節(jié)點 0个从。然后更新未確定最短路的所有節(jié)點脉幢，藍(lán)色節(jié)點表示我更新的節(jié)點。

image

最后嗦锐，這些未確定最短路的節(jié)點中嫌松，路徑最短的就是從源點到該點的最短路。

image

如上圖中奕污，dis[2] 的值最小萎羔，所以我們可以確定從源點 0 到節(jié)點 2 的最短路徑為 dis[2]。

這一論點該如何證明呢碳默？

Dijkstra 算法的本質(zhì)是貪心（greedy algorithm）贾陷，需要嚴(yán)格的數(shù)學(xué)歸納法證明，在這里我就不使用數(shù)學(xué)推導(dǎo)這種方式來證明了嘱根，感興趣的朋友們可以自行搜索一下 【 Dijkstra's algorithm: proof of correctness】髓废。

image

我們使用一種較為容易理解的方式來證明該想法。上圖中该抒，源點 到節(jié)點 這條邊的權(quán)記作 瓦哎，相同地，源點 到節(jié)點 和 這兩條邊的權(quán)記作 和 柔逼。

已知蒋譬，，愉适，如果該圖不存在負(fù)權(quán)邊犯助，那么我就一定可以確定， 為源點 到節(jié)點 的最短路徑维咸。

所以剂买，我們可以確定 Dijkstra 算法的這種思想是正確的，并且我們也間接地證明了癌蓖，為什么 Dijkstra 算法的前置條件為圖中不能含有負(fù)權(quán)邊瞬哼。

接下來，我們就繼續(xù)沿用這種思想租副，繼續(xù)模擬這個過程：

首先坐慰，我們通過已經(jīng)確定最短路的節(jié)點更新 dis 數(shù)組。在這里用僧，我們可以看到 dis[1] 更新為 3结胀，這一步的操作也叫松弛操作或放松操作（Relaxation）赞咙，松弛這個名詞可以理解為，我們選擇使用了較長的“距離”來作為兩節(jié)點之間的最短路徑糟港，可以看到攀操，節(jié)點 0 和 節(jié)點 1 之間的最短路并不是兩節(jié)點之間的邊，而是 0-2-1 這一條路徑秸抚。

image

我們從當(dāng)前這些未確定最短路的節(jié)點中速和，確定值最小的節(jié)點：

image

重復(fù)上述的過程，我們就可以得到源點 0 到圖中所有的節(jié)點的最短路徑了：

image

Dijkstra 算法的代碼實現(xiàn)

Dijkstra 算法的 Java 代碼如下剥汤，因為代碼當(dāng)中我已經(jīng)標(biāo)明了詳細(xì)的注釋健芭，所以就不對該程序一一解釋了。另外因為本文的篇幅有限秀姐，所以測試代碼的鏈接我會在文章最后給出，而測試用例與代碼這部分的內(nèi)容也就不在這里贅述了若贮。

Dijkstra

import java.util.Arrays;

public class Dijkstra {

    private WeightedGraph G;
    private int s;
    private int[] dis;
    private boolean[] visited;

    public Dijkstra(WeightedGraph G, int s) {
        this.G = G;
        // 判斷源點 s 的合法性
        if (s < 0 || s >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");
        this.s = s;
        // 對 dis 數(shù)組進(jìn)行初始化
        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;

        visited = new boolean[G.V()];

        // Dijkstra 算法的流程
        // 1. 找到當(dāng)前沒有訪問的最短路節(jié)點
        // 2. 確認(rèn)這個節(jié)點的最短路就是當(dāng)前大小
        // 3. 根據(jù)這個節(jié)點的最短路大小省有，尋找這個節(jié)點相鄰的節(jié)點并更新其他節(jié)點的路徑長度
        while (true) {
            int curdis = Integer.MAX_VALUE;
            int cur = -1;
            
            // 1. 找到未訪問的最小的節(jié)點
            for (int v = 0; v < G.V(); v++)
                if (!visited[v] && dis[v] < curdis) {
                    curdis = dis[v];
                    cur = v;
                }
            
            // 如果 cur == -1 表示所有流程結(jié)束，跳出循環(huán)
            if (cur == -1) break;
            // 2. 確認(rèn)這個節(jié)點的最短路就是當(dāng)前大小谴麦，并更新 visited
            visited[cur] = true;
            // 3. 根據(jù)這個節(jié)點的最短路大小蠢沿，尋找這個節(jié)點相鄰的節(jié)點并更新其他節(jié)點的路徑長度
            for (int w : G.adj(cur))
                if (!visited[w] && dis[cur] + G.getWeight(cur, w) < dis[w])
                    dis[w] = dis[cur] + G.getWeight(cur, w);
        }
    }


    public boolean isConnected(int v) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");

        return visited[v];
    }

    public int dis(int v) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");
        return dis[v];
    }
}

我們分析一下該算法的時間復(fù)雜度。該算法的外層為一個 while 循環(huán)匾效，內(nèi)層則是遍歷了圖中的每一個頂點舷蟀，while 循環(huán)的終止條件為每一個節(jié)點的最短路徑都被確定，所以該算法的時間復(fù)雜度為 面哼，其中 為該圖的頂點的個數(shù)野宜。

大家思考一下，這樣一個 Dijkstra 算法是否有優(yōu)化的空間呢魔策？其實不難發(fā)現(xiàn)匈子，我們的算法類中，找到圖中未訪問的最小的節(jié)點這個操作每次都要遍歷圖的所有節(jié)點闯袒，這一步驟是可以進(jìn)行優(yōu)化的虎敦，通常在貪心的問題中，優(yōu)化的策略就是使用優(yōu)先隊列政敢。

優(yōu)先隊列與 Pair 類

優(yōu)先隊列（Priority Queue）是一種特殊的隊列其徙，在優(yōu)先隊列中每個元素都有各自的優(yōu)先級，優(yōu)先級最高的元素最先得到服務(wù)喷户；優(yōu)先級相同的元素按照其在優(yōu)先隊列中的順序得到服務(wù)唾那。而優(yōu)先隊列往往使用堆這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。

在 Java 語言中褪尝，優(yōu)先隊列的默認(rèn)實現(xiàn)是最小堆通贞，我們可以使用自定義比較器來規(guī)定優(yōu)先隊列每個元素的優(yōu)先級朗若。

在我們的 Dijkstra 這個算法類中，優(yōu)先隊列中的元素應(yīng)該維護(hù) cur 以及 curdis 這兩個信息昌罩，并且優(yōu)先隊列應(yīng)該按照 curdis 從小到大的順序進(jìn)行排序哭懈。

我們很自然地想到自定義一個類，該類維護(hù)兩個變量 cur 以及 curdis茎用；然后我們讓該類實現(xiàn) Comparable 接口遣总，并在 compareTo 方法中定義我們的比較邏輯。

在這里轨功，我向大家推薦使用 JDK 中自帶的 com.sun.tools.javac.util 包下的 Pair 類旭斥。

Pair

public class Pair<A, B> {
    public final A fst;
    public final B snd;

    public Pair(A var1, B var2) {
        this.fst = var1;
        this.snd = var2;
    }

    public String toString() {
        return "Pair[" + this.fst + "," + this.snd + "]";
    }

    public boolean equals(Object var1) {
        return var1 instanceof Pair && Objects.equals(this.fst, ((Pair)var1).fst) && Objects.equals(this.snd, ((Pair)var1).snd);
    }

    public int hashCode() {
        if (this.fst == null) {
            return this.snd == null ? 0 : this.snd.hashCode() + 1;
        } else {
            return this.snd == null ? this.fst.hashCode() + 2 : this.fst.hashCode() * 17 + this.snd.hashCode();
        }
    }

    public static <A, B> Pair<A, B> of(A var0, B var1) {
        return new Pair(var0, var1);
    }
}

我們將 Pair.fst 用來存儲 cur 的信息，將 Pair.snd 用來存儲 curdis 的信息古涧。使用優(yōu)先隊列簡化后的 Dijkstra 算法類如下：

Dijkstra_2

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Dijkstra_2 {
    private WeightedGraph G;
    private int s;
    private int[] dis;
    private boolean[] visited;

    public Dijkstra_2(WeightedGraph G, int s) {
        this.G = G;
        // 判斷源點 s 的合法性
        if (s < 0 || s >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");
        this.s = s;
        // 對 dis 數(shù)組進(jìn)行初始化
        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;

        visited = new boolean[G.V()];

        // Dijkstra 算法的流程
        // 1. 找到當(dāng)前沒有訪問的最短路節(jié)點
        // 2. 確認(rèn)這個節(jié)點的最短路就是當(dāng)前大小
        // 3. 根據(jù)這個節(jié)點的最短路大小垂券，尋找這個節(jié)點相鄰的節(jié)點并更新其他節(jié)點的路徑長度

        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.snd));
        pq.offer(new Pair<>(s, 0));

        while (!pq.isEmpty()) {
            int cur = pq.poll().fst;
            if (visited[cur]) continue;
            visited[cur] = true;
            for (int w : G.adj(cur))
                if (!visited[w] && dis[cur] + G.getWeight(cur, w) < dis[w]) {
                    dis[w] = dis[cur] + G.getWeight(cur, w);
                    pq.offer(new Pair<>(w, dis[w]));
                }
        }
    }


    public boolean isConnected(int v) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");

        return visited[v];
    }

    public int dis(int v) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");
        return dis[v];
    }
}

優(yōu)化后的 Dijkstra 算法的復(fù)雜度是多少呢？

優(yōu)先隊列中塞進(jìn)去的元素個數(shù)的上界為圖中的邊的個數(shù) 羡滑，而向優(yōu)先隊列出隊與入隊操作的復(fù)雜度為 菇爪，所以我們優(yōu)化后的 Dijkstra 算法的時間復(fù)雜度為 。

好啦柒昏，關(guān)于 Dijkstra 算法的介紹就到這里為止了凳宙。我們可以看到，Dijkstra 算法的流程理解起來其實不難职祷，它的思想是一種貪心策略氏涩，但是，我們的代碼寫起來則是有一些復(fù)雜有梆。如果認(rèn)為代碼比較難懂的童鞋們是尖，可以先按照思路嘗試自己寫一下代碼，然后就可以更好地理解示例代碼每一句話的具體含義了～

Bellman-Ford 算法

上一章節(jié)中泥耀，我們介紹了 Dijkstra 算法析砸，Dijkstra 算法主要處理的是沒有負(fù)權(quán)邊的單源最短路徑問題。

那么對于含有負(fù)權(quán)邊的圖來說爆袍，該如何求解最短路徑問題呢首繁？

負(fù)權(quán)環(huán)

我們來看一下這個圖：

image

該圖為一個無向帶權(quán)圖，請求出從節(jié)點 a 到節(jié)點 c 的最短路徑陨囊。

你可能會說弦疮，a -> b -> c 就是節(jié)點 a 到節(jié)點 c 的最短路，其值為 -2蜘醋。...... 等等胁塞，好像不是這么回事。

對于上面這個無向圖來說，如果存在負(fù)權(quán)邊啸罢，那么似乎是沒有最短路的编检！因為我可以從節(jié)點 a 開始出發(fā)，無限地圍繞著這個環(huán)走下去扰才，這樣就永遠(yuǎn)得不到最短路——實際上允懂，完全不需要轉(zhuǎn)圈浪費時間，我們到達(dá)節(jié)點 b 以后衩匣，反復(fù)地在 b-c 這條邊“刷步數(shù)”就可以了:-)蕾总。

所以，對于一個無向圖來說琅捏，存在負(fù)權(quán)邊時聪建，就一定不存在最短路徑静秆。其原因就在于負(fù)權(quán)邊會構(gòu)成負(fù)權(quán)環(huán)，而無向圖的負(fù)權(quán)邊自己就是一個負(fù)權(quán)環(huán)早芭。而對于有向圖來說现斋，如果存在負(fù)權(quán)環(huán)也不存在最短路徑容诬，譬如下圖：

image

該圖是一個有向圖盲赊，但是存在負(fù)權(quán)環(huán)浑测，我們也無法求得最短路徑。

說一個題外話赎败，筆者寫到這里想起了一個小故事～

A 和 B 兩個國家的國王吵架，A 國王生氣了蠢甲，規(guī)定 B 國的 100 元只能兌換 A 國的 90 元僵刮；B 國王聽聞后也做出規(guī)定：A 國的 100 元也只能換 B 國的 90 元。在 A 國鹦牛，有一個聰敏的家伙搞糕，利用這個規(guī)則賺到了一筆橫財，你知道他是怎么做的嘛曼追？（為啥寫完了會覺得自己這么弱智）

image

閑話說回來窍仰。

對于帶有負(fù)權(quán)邊的圖來說，我們需要對該圖進(jìn)行檢測礼殊，檢測圖中是否存在負(fù)權(quán)環(huán)驹吮，如果存在負(fù)權(quán)環(huán)，那么該圖就一定不存在最短路徑晶伦。而檢測負(fù)權(quán)環(huán)在算法的實現(xiàn)中是非常簡單的碟狞，我們先來看一下存在負(fù)權(quán)邊時求解最短路徑的一個經(jīng)典算法——Bellman-Ford 算法。

Bellman-Ford 算法

Bellman-Ford 算法的原理就在于松弛操作婚陪。

image

假設(shè)族沃， 是從源點 到節(jié)點 經(jīng)過邊數(shù)不超過 的最短距離。

如果 ，我們就進(jìn)行一次松弛操作脆淹，更新 常空；

所以，我們找到了從源點 到節(jié)點 經(jīng)過邊數(shù)不超過 的最短距離盖溺。

同理漓糙，如果 ，我們就進(jìn)行一次松弛操作咐柜，更新 兼蜈；

這樣，我們就找到了從源點 到節(jié)點 經(jīng)過邊數(shù)不超過 的最短距離拙友。

根據(jù)上述理論为狸，我們的 Bellman-Ford 算法流程如下：

1. 初始化 dis 數(shù)組，dis[s] = 0遗契，其余的值設(shè)置為
2. 對所有邊進(jìn)行一次松弛操作辐棒，則求出了到所有點，經(jīng)過邊數(shù)最多為 1 的最短路
3. 對所有邊再進(jìn)行一次松弛操作牍蜂，則求出了到所有點漾根，經(jīng)過邊數(shù)最多為 2 的最短路
4. ... ...
5. 對所有邊進(jìn)行 V-1 次松弛操作，則求出了到所有點鲫竞，經(jīng)過邊數(shù)最多為 V-1 的最短路

我們的圖只有 V 個頂點辐怕，如果不存在負(fù)權(quán)環(huán)，從一個頂點到另外一個頂點最多經(jīng)過 V-1 條邊从绘，所以在我們對所有邊進(jìn)行了 V-1 次松弛操作后寄疏，我們就找到了源點到所有點的最短路，并且 Bellman-Ford算法支持存在負(fù)權(quán)邊僵井。

接下來陕截，我們通過一個示例來模擬一下 Bellman-Ford 算法的執(zhí)行流程，相信通過這個模擬過程批什，你一定會對 Bellman-Ford 算法有更加深刻的理解:-)

image

上圖為一個有向帶權(quán)圖农曲，我們規(guī)定節(jié)點 0 為源點，源點到源點的最短路初始值為 0驻债，其余節(jié)點則使用 來表示乳规。

首先，我們對所有邊進(jìn)行一次松弛操作合呐，假設(shè)我們先松弛 0-1 這條邊驯妄，然后松弛 0-2 這條邊，最后松弛 2-1 這條邊合砂，經(jīng)過第一次松弛操作后青扔，我們的 dis 數(shù)組更新如下：

image

經(jīng)過第一次松弛操作以后源织，我們實際上就已經(jīng)求出了源點到各個頂點的最短路徑了。

看上去微猖，我們并不需要 V-1 次松弛操作谈息？是這樣么？實際上凛剥，V-1 次松弛操作是一個上界侠仇，我們完全有可能在小于 V-1 次松弛操作之后就得到結(jié)果，但是最壞的情況犁珠，我們也只需要 V-1 次松弛操作逻炊。

上面的示例中，我們從 0-1 這條邊開始松弛犁享，如果換一種思路余素，從 2-1 這條邊開始松弛會是什么結(jié)果呢？

假設(shè)我們先松弛 2-1 這條邊炊昆，然后松弛 0-1 這條邊桨吊，最后松弛 0-2 這條邊，經(jīng)過第一次松弛操作后凤巨，我們的 dis 數(shù)組更新如下：

image

需要注意的是视乐，在松弛 2-1 這條邊時，我們會用 敢茁，其值仍為 佑淀。

第二次松弛操作后，我們的 dis 數(shù)組更新如下：

image

我們看到彰檬，經(jīng)過了兩次對所有邊的松弛后伸刃，我們也得到了正確解。

那么如何檢測負(fù)權(quán)環(huán)呢僧叉？

其實很簡單奕枝，根據(jù) Bellman-Ford 算法棺榔，如果我們的圖不存在負(fù)權(quán)環(huán)瓶堕，經(jīng)過 V-1 次松弛操作后，我們就可以得到源點到各個節(jié)點的最短路徑了症歇，如果 V-1 次松弛操作后郎笆，我們再對所有邊進(jìn)行松弛，各個點的 dis 值是不會發(fā)生變化的忘晤；而如果圖中存在負(fù)權(quán)環(huán)宛蚓，經(jīng)過 V-1 輪松弛操作后，再進(jìn)行松弛操作设塔，dis 數(shù)組的每個值仍然會發(fā)生變化凄吏。

所以在算法的設(shè)計上，我們只需要在 V-1 次松弛操作后，再進(jìn)行一次松弛操作痕钢，判斷 dis 數(shù)組是否發(fā)生改變图柏，如果發(fā)生了改變，則說明圖中存在負(fù)權(quán)環(huán)任连，即無法求得最短路徑蚤吹。

接下來，讓我們看一下 Bellman-Ford 算法的具體實現(xiàn)随抠。

Bellman-Ford 算法的代碼實現(xiàn)

Bellman-Ford 算法的 Java 代碼如下裁着，代碼中標(biāo)明了詳細(xì)的注釋，我就不再解釋了:-)

同樣拱她，測試代碼的鏈接會在文章最后給出二驰，測試部分就不在本文中贅述了。

Bellman-Ford

import java.util.Arrays;

public class BellmanFord {
    private WeightedGraph G;
    private int s;
    private int[] dis;
    public boolean hasNegativeCycle = false;

    public BellmanFord(WeightedGraph G, int s) {
        this.G = G;
        if (s < 0 || s >= G.V())
            throw new IllegalArgumentException("vertex" + s + "is invalid");
        this.s = s;
        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;
        // V-1 輪松弛操作
        for (int pass = 1; pass < G.V(); pass++) {

            for (int v = 0; v < G.V(); v++)
                for (int w : G.adj(v))
                    if (dis[v] != Integer.MAX_VALUE && dis[v] + G.getWeight(v, w) < dis[w])
                        dis[w] = dis[v] + G.getWeight(v, w);
        }

        // 再進(jìn)行一次放松(松弛)操作椭懊，判斷負(fù)權(quán)環(huán)
        for (int v = 0; v < G.V(); v++)
            for (int w : G.adj(v))
                if (dis[v] != Integer.MAX_VALUE && dis[v] + G.getWeight(v, w) < dis[w])
                    hasNegativeCycle = true;

    }

    public boolean isConnected(int v) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + v + "is invalid");
        return dis[v] != Integer.MAX_VALUE;
    }

    public int dis(int v) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + v + "is invalid");
        if (hasNegativeCycle) throw new RuntimeException("Exist negative cycle");
        return dis[v];
    }

}

Bellman-Ford 算法的時間復(fù)雜度是多少呢诸蚕？我們需要進(jìn)行 V-1 輪松弛操作，每一次松弛操作都會遍歷圖中所有的邊氧猬，所以背犯，Bellman-Ford 算法的時間復(fù)雜度為 ≈迅В可以看到漠魏，Bellman-Ford 算法雖然可以解決負(fù)權(quán)邊，但是其整體的復(fù)雜度是要差于 Dijkstra 算法的妄均。

Bellman-Ford 算法我就介紹到這里了柱锹，接下來我們來看一下本篇文章介紹的最后一個算法——Floyd-Warshall 算法。

Floyd-Warshall 算法

我們在前面介紹了 Dijkstra 與 Bellman-Ford 這兩種求解單源最短路徑的算法丰包，而本章節(jié)介紹的 Floyd-Warshall 算法則是一種用來求解所有點對（任意兩點）最短路徑的算法禁熏。

求解所有點對最短路徑有什么意義呢？

如果我們知道圖中任意兩點的最短路徑邑彪，我們就可以得到該圖中任意兩點最短路徑的最大值瞧毙，這個名詞術(shù)語叫做圖的直徑。

舉一個例子寄症，如果我們的圖表示一個互聯(lián)網(wǎng)的網(wǎng)絡(luò)系統(tǒng)宙彪，節(jié)點與節(jié)點之間的邊表示兩個中間站的傳輸延遲，如何去評價這個網(wǎng)絡(luò)系統(tǒng)的性能有巧？這個時候释漆，求解圖的直徑就有著重大的意義。而求解圖的直徑就需要求解所有點對兒最短路徑篮迎。

對于 Dijkstra 算法來說男图，求解單源最短路徑的復(fù)雜度為 示姿，如果求解所有點對最短路徑，則需要對圖中的每個頂點求解一次單源路徑問題逊笆，所以峻凫，其復(fù)雜度為 ；而 Bellman-Ford 算法用來分析求解所有點對最短路徑的思路也是一樣的览露，其時間復(fù)雜度為 荧琼。

對于 Floyd-Warshall 算法來說，求解所有點對最短路徑的時間復(fù)雜度為 差牛，且可以求解負(fù)權(quán)邊命锄，接下來我們來看一下 Floyd-Warshall 算法的具體思路。

因為 Floyd-Warshall 算法中并沒有源節(jié)點這個概念偏化，或者可以認(rèn)為對于每個節(jié)點來說脐恩，都是一個源節(jié)點，所以我們使用一個 數(shù)組侦讨， 表示頂點 到頂點 的最短路徑驶冒。

數(shù)組的初始化也非常簡單， 的初始值設(shè)為 0韵卤，如果 存在一條邊骗污，那么就令 的初始值為節(jié)點 和節(jié)點 這條邊的權(quán)值 ，其余的則以 來表示沈条。

Floyd-Warshall 算法的偽碼如下：

for(int t = 0; t < V; t++)
  for(int v = 0; v < V; v++)
    for(int w = 0; w < V; w++)
      if(dis[v][t] + dis[t][w] < dis[v][w])
        dis[v][w] = dis[v][t] + dis[t][w]

這段偽碼描述的是一個什么過程呢需忿？

image

如果節(jié)點 和節(jié)點 之間存在著某個節(jié)點 ，并且 蜡歹，那么就更新 屋厘，這一步驟的本質(zhì)實際上就是松弛操作。那么我們該如何理解 的含義呢月而？

這個循環(huán)表達(dá)的含義是汗洒，每一輪循環(huán)求解出中間經(jīng)過 這些點的最短路徑。

• 賦初始值時父款，我們只考慮頂點 和頂點 不經(jīng)過任何頂點時的距離溢谤；
• 當(dāng) 時，我們考慮的就是铛漓，如果頂點 和頂點 中間經(jīng)過了 0 這個頂點后溯香，是否更新了當(dāng)前的最短路鲫构；
• 當(dāng) 時浓恶，我們考慮的就是，如果頂點 和頂點 中間經(jīng)過了 中的頂點后结笨，是否更新了當(dāng)前的最短路包晰；
• 當(dāng) 時湿镀，我們考慮的就是，如果頂點 和頂點 中間經(jīng)過了 中的頂點后伐憾，是否更新了當(dāng)前的最短路勉痴。

Floyd-Warshall 算法檢測負(fù)權(quán)環(huán)的原理和 Bellman-Ford 算法檢測負(fù)權(quán)環(huán)的原理是實際上相同的，在算法結(jié)束之后树肃，我們只需要遍歷一遍圖的所有頂點蒸矛，看 是否有出現(xiàn)小于 0 的情況即可，如果出現(xiàn)了負(fù)值則表示該圖中含有負(fù)權(quán)環(huán)胸嘴。

好啦雏掠，F(xiàn)loyd-Warshall 算法的流程便是這樣了，我們來看一下具體的代碼實現(xiàn)劣像。

Floyd-Warshall 算法的代碼實現(xiàn)

Floyd-Warshall

import java.util.Arrays;

public class FloydWarshall {
    private WeightedGraph G;
    private int[][] dis;
    public boolean hasNegativeCycle = false;

    public FloydWarshall(WeightedGraph G) {
        this.G = G;
        dis = new int[G.V()][G.V()];
        for (int i = 0; i < G.V(); i++)
            Arrays.fill(dis[i], Integer.MAX_VALUE);

        for (int v = 0; v < G.V(); v++) {
            dis[v][v] = 0;
            for (int w : G.adj(v))
                dis[v][w] = G.getWeight(v, w);
        }

        for (int t = 0; t < G.V(); t++)
            for (int v = 0; v < G.V(); v++)
                for (int w = 0; w < G.V(); w++)
                    if (dis[v][t] != Integer.MAX_VALUE
                            && dis[t][w] != Integer.MAX_VALUE
                            && dis[v][t] + dis[t][w] < dis[v][w])
                        dis[v][w] = dis[v][t] + dis[t][w];

        for (int v = 0; v < G.V(); v++)
            if (dis[v][v] < 0) hasNegativeCycle = true;
    }

    public boolean isConnected(int v, int w) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + v + "is invalid");
        if (w < 0 || w >= G.V())
            throw new IllegalArgumentException("vertex" + w + "is invalid");
        return dis[v][w] != Integer.MAX_VALUE;
    }

    public int dis(int v, int w) {
        if (v < 0 || v >= G.V())
            throw new IllegalArgumentException("vertex" + v + "is invalid");
        if (w < 0 || w >= G.V())
            throw new IllegalArgumentException("vertex" + w + "is invalid");
        return dis[v][w];
    }
}

可以看到乡话，F(xiàn)loyd-Warshall 算法是一個易讀的算法，我們可以很快看出耳奕，F(xiàn)loyd-Warshall 算法的復(fù)雜度為 绑青，雖然這個復(fù)雜度并沒有優(yōu)于 Dijkstra 算法，但是屋群，F(xiàn)loyd-Warshall 算法卻可以檢測負(fù)權(quán)環(huán)闸婴，用于帶有負(fù)權(quán)邊的圖，并且其復(fù)雜度優(yōu)于 Bellman-Ford 算法求解所有點對最短路徑芍躏。

不過掠拳，F(xiàn)loyd-Warshall 算法它最大的優(yōu)點是簡潔優(yōu)美，這里面融匯的是 DP 算法的藝術(shù)纸肉。

總結(jié)

在這一篇文章中溺欧，我向你介紹了三種最短路徑算法，這三種算法分別是 Dijkstra 算法柏肪，Bellman-Ford 算法以及 Floyd-Warshall 算法姐刁。

Dijkstra 算法是求解單源最短路徑的經(jīng)典算法，雖然無法求解帶有負(fù)權(quán)邊的圖烦味，但是 Dijkstra 算法仍然是一個非常有意義的算法聂使，畢竟我們求解的最短路徑問題，有很大一部分都是沒有負(fù)權(quán)邊的情況谬俄。

如果遇到有負(fù)權(quán)邊的最短路徑問題時柏靶，我們可以選擇 Bellman-Ford 算法或 Floyd-Warshall 算法，前者用于解決單源最短路問題溃论，后者則可以解決所有點對最短路問題屎蜓。

好啦，至此為止钥勋，這篇文章就到這里了～歡迎大家關(guān)注我的公眾號炬转，在這里希望你可以收獲更多的知識辆苔，我們下一期再見！