java弗洛伊德算法與迪杰斯特拉算法的實例介紹

本篇內(nèi)容主要講解“java弗洛伊德算法與迪杰斯特拉算法的實例介紹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“java弗洛伊德算法與迪杰斯特拉算法的實例介紹”吧!

最短路徑

公交和地鐵是最普遍的交通工具了，但是通常情況下去往某處有多種出行方案，有的少換乘，有的時間短，有的步行少，等等。這就涉及到如何尋找一條最合適的路徑的問題，比如從下圖的v₀處出發(fā)，怎樣才能最快到達(dá)v₈處？

尋找最短路徑，通常也有兩種經(jīng)典算法，接下來我們一一介紹。

迪杰斯特拉（Dijkstra）算法

迪杰斯特拉算法的思路是從起點開始，尋找它到每個中間點的最短距離，一步步向終點逼近。我們就以上圖為例，演示迪杰斯特拉算法的過程。

首先從v₀出發(fā)，可以到達(dá)的最近的點是v₁，距離是1，所以通過的第一條邊是(v₀, v₁)，如下所示：

接下來因為v₁可以去往v₂、v₃和v₄，所以從v₀->v₁->v₂距離為4，從v₀->v₁->v₃距離為8，從v₀->v₁->v₄距離為6，這三條路徑中最短為v₀->v₁->v₂，它甚至比直接從v₀->v₂還要短，所以接下來的路徑應(yīng)該為v₀->v₁->v₂，如下所示：

接下來我們又可以獲取更多的路徑信息，從v₀->v₂->v₄距離是5，從v₀->v₂->v₅距離是11，而前者比從從v₀->v₁->v₄還要短，所以接下來的路徑應(yīng)該為v₀->v₂->v₄，其中v₀->v₂實際上是v₀->v₁->v₂，如下所示：

接下來，我們按照同樣的邏輯，從v₄出發(fā)最近的頂點為v₃，路徑長度為7，而從v₀->v₁->v₃的直接距離為8，所以完整路徑為v₀->v₁->v₂->v₄->v₃，如下所示：

按照同樣方式，我們可以得到以下路徑，就是我們要找的最短路徑，如下所示：

可以看到，迪杰斯特拉算法就是通過不斷尋找到中間頂點的最短距離和對比頂點間的直接距離，一點點逼近終點的，這比較適合于提前規(guī)劃好路線，而不能走一步看一步。

弗洛伊德（Floyd）算法

弗洛伊德算法比較精妙，但是也相對較難理解，我們依然以上圖為例，演示它的運(yùn)算過程。

首先，構(gòu)建它的鄰接矩陣表，稱為D^-1，除此之外，再構(gòu)建一個矩陣P<sup>-1<sup>，賦值如下：

其中上標(biāo)-1表示初始化狀態(tài)，P^-1中的每個值表示從頂點 v_i 到頂點 v_j 需要經(jīng)過的中間點，默認(rèn)值表示直接連接，沒有中間點。

初始化完成后，就可以進(jìn)行弗洛伊德算法了。首先，讓所有頂點之間的路徑都經(jīng)過v₀，比如從v₁->v₂，變?yōu)関₁->v₀->v₂，此時發(fā)現(xiàn)v₁->v₂距離為3，而變?yōu)関₁->v₀->v₂后距離成為了6，所以不需要更新數(shù)據(jù)。由于v₃-v₈都不鄰接于v₀，也就無法讓 v₀ 成為中間點，所以也不需要更新，因此這次操作后，數(shù)據(jù)沒有任何改變，但是矩陣的狀態(tài)改變了，從D^-1變?yōu)镈⁰，P同理，如下所示：

現(xiàn)在，我們以每個頂點之間的路徑都經(jīng)過v₁，可以看到v₀->v₂的距離為5，而v₀->v₁->v₂的距離為4，比直接距離更短，同理v₀->v₃原本不能直接到達(dá)，經(jīng)過v₁后的路徑v₀->v₁->v₃距離變?yōu)?，v₀->v₁->v₄距離變?yōu)?。以v₂為起點，到達(dá)v₃的路徑v₂->v₁->v₃距離變?yōu)?0。以v₃為起點，到達(dá)v₀和v₂的距離，以及以v₄為起點，到達(dá)v₀的距離都發(fā)生了改變。此時因為將v₁作為中間點，使得部分路徑縮短，于是更新兩個表的值如下：

其中P的某些值更新為1，表示從v_i到v_j需要經(jīng)過頂點v₁。

在此基礎(chǔ)上，我們以每個頂點之間的路徑都經(jīng)過v₂，再次進(jìn)行同樣的計算，我們找到的第一個需要更新的數(shù)據(jù)是v₀->v₄，它的距離是6，而v₀->v₂->v₄的距離為5，所以D[0][4]值更新為5，P[0][4]的值則應(yīng)該更新為P[0][2]的值，這是因為從v₀->v₂還有可能經(jīng)過其它中間點，例如這里就是經(jīng)過v₁，這樣我們就把v₀->v₄的路徑從原本的v₀->...->v₄，變?yōu)榱藦膙₀->...->v₂->v₄，只要不斷迭代，就可以找到完整的路徑。更新結(jié)果如下所示：

按照同樣的規(guī)則，我們對其余數(shù)據(jù)進(jìn)行同樣的操作，最終可以得到下圖的結(jié)果：

最后得到的D⁸表的每個數(shù)據(jù)表示從頂點 v_i 到頂點 v_j 的最短距離，而P⁸表的每個數(shù)據(jù)表示從頂點 v_i 到頂點 v_j 需要經(jīng)過的第一個中間頂點。例如從 v₀->v₈，首先要經(jīng)過頂點 v₁，完整路徑為v₀->v₁加上v₁->v₈，而v₁->v₈需要經(jīng)過v₂，于是完整路徑為v₀->v₁->v₂加上v₂->v₈，迭代下去，可以得到最終的最短路徑為v₀->v₁->v₂->v₄->v₃->v₆->v₇->v₈，如下所示：

可以看到，結(jié)果和使用迪杰斯特拉算法的結(jié)果是一致的。

代碼實現(xiàn)

迪杰斯特拉算法

public void dijkstra(AMGraph<String> amGraph, int fromIndex) {
    int len = amGraph.getVertexNum();
    // 存儲從fromIndex到其他各頂點的最短路徑下標(biāo)
    int[] p = new int[len];
    // 存儲從fromIndex到其他各頂點的最短路徑的權(quán)值和
    int[] d = new int[len];
    // 標(biāo)記求得了頂點fromIndex到其他各定點的最短路徑
    boolean[] finded = new boolean[len];
    // 初始化數(shù)據(jù)
    for (int toIndex = 0; toIndex < len; toIndex++) {
        finded[toIndex] = false;
        d[toIndex] = amGraph.getWeight(fromIndex, toIndex);
        p[toIndex] = 0;
    }

    // fromIndex到自己的路徑長度為0，并且不需要再求它的最短路徑了
    d[fromIndex] = 0;
    finded[fromIndex] = true;

    int min = 0;
    int k = -1;
    // 求fromIndex到toIndex的最短路徑
    for (int toIndex = 1; toIndex < len; toIndex++) {
        min = Integer.MAX_VALUE;
        // 尋找距離fromIndex最近的頂點
        for (int i = 0; i < len; i++) {
            if (!finded[i] && d[i] < min) {
                // i 離 fromIndex最近
                k = i;
                min = d[i];
            }
        }

        // 找到了最近的點
        finded[k] = true;

        // 更新剩余頂點的距離值
        for (int i = 0; i < len; i++) {
            // 如果經(jīng)過 k 之后的距離比直接到 i 的距離近，就更新距離
            if (!finded[i] && amGraph.getWeight(k, i) != Integer.MAX_VALUE && (min + amGraph.getWeight(k, i) < d[i])) {
                d[i] = min + amGraph.getWeight(k, i);
                p[i] = k;
            }
        }

        System.out.println();
        for (int i = 0; i < len; i++) {
            System.out.print(p[i] + "\t");
        }
    }
}

迪杰斯特拉算法的時間復(fù)雜度為O(n²)，但是它每次只能計算出從某一個頂點開始到其它頂點的最短路徑。

弗洛伊德算法

public void floyd(AMGraph<String> amGraph) {
    int len = amGraph.getVertexNum();
    int[][] d = new int[len][len];
    int[][] p = new int[len][len];

    // 初始化d和p數(shù)組
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            d[i][j] = amGraph.getWeight(i, j);
            p[i][j] = j;
        }
    }

    for (int k = 0; k < len; k++) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (d[i][k] != Integer.MAX_VALUE && d[k][j] != Integer.MAX_VALUE && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    p[i][j] = p[i][k];
                }
            }
        }
    }

    printD(len, d);
    printP(len, p);
}

弗洛伊德算法十分優(yōu)雅和簡潔，并且可以得到任意頂點間的最短路徑，不過因為三層循環(huán)的原因，它的時間復(fù)雜度為O(n³)。

以上涉及代碼請參考ShortestPath.java。

到此，相信大家對“java弗洛伊德算法與迪杰斯特拉算法的實例介紹”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！