圖的最短路徑問題！

Java高階數(shù)據(jù)結(jié)構(gòu) & 圖的最短路徑問題

圖的基礎(chǔ)知識(shí)博客：傳送門

最短路徑問題： 從在帶權(quán)圖的某一頂點(diǎn)出發(fā)，找出一條通往另一頂點(diǎn)的最短路徑，最短也就是沿路徑各邊的權(quán)值總 和達(dá)到最小。

一共會(huì)講解三種算法

1. Dijkstra算法【單源最短路徑】
2. Bellman-Ford算法【單源最短路徑】
   • 改進(jìn)：SPFA算法
3. Floyd-Warshall算法【多源最短路徑】

單源最短路徑問題： 給定一個(gè)圖G = ( V ， E ) G=(V，E)G=(V，E)，求源結(jié)點(diǎn)s ∈ V 到圖中每個(gè)結(jié)點(diǎn)v ∈ V 的最短路徑。

多源最短路徑問題： 就是找到每個(gè)頂點(diǎn)到除本身的頂點(diǎn)的最短路徑

兩頂點(diǎn)不連通，則不存在最短路徑–>∞

在后面的講解中，就不要聯(lián)想到鄰接矩陣了，這樣腦子CPU都要燒爛了，代碼實(shí)現(xiàn)需要鄰接矩陣，而不是圖就長成矩陣這么抽象的樣子。

• 看原圖去分析思考就行了，記住邊的代碼表達(dá)即可

  • 比如說，一個(gè)頂點(diǎn)連出去的邊，在原圖中很明顯，在鄰接矩陣中不明顯，但是后續(xù)我們要得到連出去的邊，我們也有方法呀，所以在算法思考的時(shí)候，先不要在意這點(diǎn)！
• 1. 算法思路：原圖
  2. 代碼實(shí)現(xiàn)：根據(jù)算法翻譯即可
     
     

  如果你本來就是這樣的，那真的太棒了

注意：帶負(fù)權(quán)的圖，可能可以找到最短路徑，也可能找不到

1. 帶負(fù)權(quán)回路的圖，不存在最短路徑

判斷方法：

• 一條路徑上通過兩次一樣的頂點(diǎn)，第二次反而更短了，則必然存在一個(gè) 負(fù)權(quán)回路
• 即，這個(gè)環(huán)的權(quán)值和為負(fù)數(shù)

則說明：一張圖的最短路徑，一定滿足邊數(shù)<= n-1

原因：

因?yàn)榭梢酝ㄟ^這個(gè)負(fù)權(quán)回路，導(dǎo)致一些最短路徑趨近于負(fù)無窮大

• 即，在這個(gè)環(huán)里，無限循環(huán)

（帶負(fù)權(quán)一定要是有向圖，無向圖的話，負(fù)權(quán)邊一定構(gòu)成兩個(gè)頂點(diǎn)的負(fù)權(quán)回路）

以下算法代碼實(shí)現(xiàn)簡單，重點(diǎn)看算法思想！

1. Dijkstra算法【單源最短路徑】

• 思路適用于解決帶權(quán)重的有向圖上的單源最短路徑問題
  • 無向圖當(dāng)然也可以~
• 但是，算法要求圖中的所有邊的權(quán)重都是非負(fù)的~
  • 再講解完算法后你就知道為什么了

定義：（不懂沒關(guān)系，最后我有詳細(xì)的證明）

1. 定義一個(gè)dist數(shù)組，這個(gè)數(shù)組記錄出發(fā)點(diǎn)到其他點(diǎn)的最短路徑

   • 一開始沒找出來的時(shí)候，默認(rèn)全為無窮大，到自身距離為0

2. 定義一個(gè)path數(shù)組，代表每個(gè)頂點(diǎn)的前一個(gè)節(jié)點(diǎn)

   • 通過這個(gè)數(shù)組可以還原路徑

3. 定義一個(gè)操作：“松弛”

   • 松弛一個(gè)頂點(diǎn)，就是將其連通的所有邊進(jìn)行以下操作：

   • 設(shè)此頂點(diǎn)為i，連通終點(diǎn)為j

   • 判斷：dist[i] + weight(i, j) < dist[j]

   1. 如果為真，則說明j此時(shí)的最短路徑不是最短路徑，path[j] = i，dist[j] = dist[i] + weight(i, j)
   2. 如果為假，什么也說明不了

至于為什么叫松弛，這也是英譯過來的。
一開始小范圍的這個(gè)操作，只能涉及一些邊和一些頂點(diǎn)，就像彈簧被壓得很緊，這個(gè)操作會(huì)帶向更多的邊，彈簧也沒那么緊了~

不理解也沒所謂，不要糾結(jié)這個(gè)動(dòng)詞，不要糾結(jié)這個(gè)叫法！

步驟：

1. 選取此時(shí)dist中的最小元素下標(biāo)，標(biāo)記它，斷言此頂點(diǎn)為最短路徑
   • （值為0的出發(fā)點(diǎn)此時(shí)必然第一個(gè)被標(biāo)記和松弛）
2. 松弛剛才被標(biāo)記的頂點(diǎn)
3. 選取松弛完dist中最小元素下標(biāo)，標(biāo)記它，斷言此頂點(diǎn)為最短路徑
4. 松弛剛才被標(biāo)記的頂點(diǎn)
5. 選取松弛完dist中最小元素下標(biāo)，標(biāo)記它，斷言此頂點(diǎn)為最短路徑
6. 松弛剛才被標(biāo)記的頂點(diǎn)
7. …
8. 直到所有頂點(diǎn)都被標(biāo)記

可以有兩種理解方式：

1. 標(biāo)記 松弛 標(biāo)記 松弛 標(biāo)記 松弛 … 標(biāo)記（最后一次沒必要松弛）
   • 標(biāo)記最短路徑頂點(diǎn)，松弛這個(gè)頂點(diǎn)
2. （標(biāo)記出發(fā)點(diǎn)后） 松弛 標(biāo)記 松弛 標(biāo)記 松弛 標(biāo)記 … 松弛 標(biāo)記
   • 松弛后誕生一個(gè)最短路徑，標(biāo)記

獲得最短路徑：

• 通過path數(shù)組，不斷向出發(fā)點(diǎn)方向“跳”，直到到達(dá)出發(fā)點(diǎn)

例子：

• 如以上連通無向圖，求0為出發(fā)點(diǎn)，求0到其余點(diǎn)的最短路徑

動(dòng)圖演示：

來源：【算法】最短路徑查找—Dijkstra算法_嗶哩嗶哩_bilibili

• 講的很好！
• 但是沒有證明為什么，接下來就來看看為什么吧

1.1 Dijkstra算法證明

1. 松弛操作的作用

• 所以，松弛操作，保證了目前看來（在下一次松弛之前），頂點(diǎn)們?cè)赿ist數(shù)組內(nèi)的中是當(dāng)前能達(dá)到的最小值
• 并且改變j的路徑為，【0 , i】延伸一條邊【i , j】

一樣短會(huì)怎么樣呢？

• 不會(huì)怎么樣，只是說明最短路徑不唯一

至少對(duì)這個(gè)頂點(diǎn)后續(xù)的延伸是沒區(qū)別的，因?yàn)?到j(luò)的距離都一樣，后續(xù)該怎么延伸出去還是怎么延伸出去

2. 為什么可以斷言這個(gè)頂點(diǎn)一定是最短路徑？

重要原因：圖沒有負(fù)權(quán)

我們按照算法思路先走一走

1. 選擇0，這是顯然的，松弛0后，誕生了“第一代最短路徑”（路徑上只有1條邊）
2. 標(biāo)記松弛后的dist數(shù)組（未標(biāo)記頂點(diǎn)）中最小的頂點(diǎn)

那么我們就斷言第一代最短路徑中最短的那條路徑，就是“正確的”

• 這也是攜帶了為什么Dijkstra只能解決帶非負(fù)權(quán)圖的原因
• 就是因?yàn)椋乃惴ǖ那疤?，就?strong>沒有負(fù)權(quán)！

第一代最短路徑最短那那條L，就不可能通過任何方式讓其更短

• 因?yàn)檫@個(gè)點(diǎn)的其他路徑就只能是第二代，或者更多
• 而這條路徑，是通過第一代最短路徑的另一些邊的，而這些邊本身就比L大，并且此后路徑的邊都是正的，必然比L大

2. 松弛剛才標(biāo)記的頂點(diǎn)1，誕生“第二代最短路徑”（路徑上為2條邊）
3. 標(biāo)記松弛后的dist數(shù)組（未標(biāo)記頂點(diǎn)）中最小的頂點(diǎn)

那么我們就斷言第一代最短路徑中最短的那條路徑L2，就是“正確的”

同樣的道理，這條路徑要么是一條邊的，要么是兩條邊的

剛才為什么不一起選擇7這個(gè)頂點(diǎn)呢？

• 【0到1】 比 【0到7】 短，所以可能【0到1】在到其他頂點(diǎn)，再回到7這個(gè)頂點(diǎn)

在第二代最短路徑中，剛才的0松弛操作保證了目前看來最短路徑為一條邊的和最短路徑為兩條邊的頂點(diǎn)在dist值最小

你會(huì)發(fā)現(xiàn)，如果你不對(duì)剛才的更新的頂點(diǎn)進(jìn)行松弛，而是重復(fù)松弛之前的頂點(diǎn)，沒有任何頂點(diǎn)更新，沒有任何作用，則剛才的松弛操作，已經(jīng)保證了這一點(diǎn)
而你可以這樣理解，松弛就相當(dāng)于在對(duì)賬核對(duì)，核對(duì)完后，保證這一點(diǎn)
（這是本文章的核心思想）

• 即，局部范圍內(nèi)，他們是最短路徑（在現(xiàn)在能觸及的范圍內(nèi)，他們的dist值是正確的）
• 即，以出發(fā)點(diǎn)為標(biāo)準(zhǔn)，最多延伸兩條邊的子圖范圍內(nèi)，他們都是最短路徑
  • 這個(gè)子圖不包含所有的“兩條邊的路徑”，不包含的部分也不需要出現(xiàn)，因?yàn)闆]有負(fù)權(quán)，包含在內(nèi)的“兩條邊的路徑”，是由上一次的最短路徑頂點(diǎn)延伸出來的，那么這個(gè)條包含在子圖內(nèi)的“兩條邊的路徑”，一定是比不包含的要短~

這一次，最短的是【0到7】，同樣的原因，可以斷言7此時(shí)是正確的最短路徑

• 剛才的證明了此時(shí)7是這個(gè)范圍內(nèi)的最短路徑，這就夠了
• 后續(xù)不會(huì)再有到7路徑更短的頂點(diǎn)了（別的路徑只能增加）

4. 松弛頂點(diǎn)7，誕生第三代最短路徑
5. 標(biāo)記松弛后dist值（未標(biāo)記頂點(diǎn)中）最小的頂點(diǎn)

同樣的，以出發(fā)點(diǎn)為標(biāo)準(zhǔn)，最多延伸三條邊的子圖（<=3，一樣的，不一定包含所有的“三邊路徑”和“兩邊路徑”，一定包含“更有權(quán)威的”路徑）范圍內(nèi)，他們都是最短路徑

• 選擇頂點(diǎn)6（此時(shí)頂點(diǎn)6）~
  • 因?yàn)楹罄m(xù)到這頂點(diǎn)就只能增了~

依照這個(gè)思路下去，所有頂點(diǎn)被標(biāo)記，結(jié)束！

• 這個(gè)例子中，邊數(shù)最多的路徑，為“四邊路徑”，【0到4】
  

3. 為什么可以通過path確認(rèn)最短路徑？

以【0到4】為例子

【0到4】=【0到5】+【5到4】

1. 其實(shí)一條長路徑一定是由短路徑拼接起來的（由剛才的算法得出結(jié)論，最短路徑的更新，是在前一個(gè)頂點(diǎn)的最短路徑基礎(chǔ)上延伸一條邊）
2. 

所以，一個(gè)最短路徑的子路徑為別的頂點(diǎn)的最短路徑，所以可以通過下標(biāo)的往回“跳”，得到真實(shí)路徑

證明完畢~

1.2 Dijkstra算法代碼實(shí)現(xiàn)

• 代碼實(shí)現(xiàn)看起來很簡單，但是原理是剛才那樣的復(fù)雜

	/**
     *
     * @param src 出發(fā)點(diǎn)
     * @param dist 要求把最短路徑長存放在這個(gè)數(shù)組里
     * @param path 要求將前面點(diǎn)存放在這個(gè)數(shù)組里
     */
public void dijkstra(char src, int[] dist, int[] path) {
    //獲取頂點(diǎn)下標(biāo)
    int srcIndex = getIndexOfV(src);

    //初始化dist
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[srcIndex] = 0;//起始點(diǎn)

    //初始化path
    Arrays.fill(path, -1);
    path[srcIndex] = srcIndex;//如果是前一個(gè)頂點(diǎn)是本身的話，則說明到達(dá)起始點(diǎn)

    //定義visited數(shù)組
    int n = arrayV.length;
    boolean[] visited = new boolean[n];

    //開始標(biāo)記與松弛操作了
    //由于我們知道每次循環(huán)都會(huì)標(biāo)記一個(gè)，那么循環(huán)次數(shù)就知道了，所以我們就用特定的for循環(huán)去寫
    for (int i = 0; i < n; i++) {

        //找dist最小值
        int index = srcIndex;//這個(gè)無所謂
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if(!visited[j] && dist[j] < min) {
                index = j;
                min = dist[j];
            }
        }
        //標(biāo)記
        visited[index] = true;

        //松弛
        for (int j = 0; j < n; j++) {
            //被必要松弛到標(biāo)記的頂點(diǎn)的，因?yàn)闆]用（再之前的證明中），你要也可以
            if(!visited[j] && matrix[index][j] != Integer.MAX_VALUE
               && dist[index] + matrix[index][j] < dist[j]) {
                //松弛導(dǎo)致的更新操作，更新其路徑為【0，index】延伸一條邊【index，j】
                dist[j] = dist[index] + matrix[index][j];
                path[j] = index;
            }
        }
    }
}

測(cè)試：

打印路徑和路徑長的方法：

public void printShortPath(char vSrc,int[] dist,int[] pPath) {
    //1. 獲取頂點(diǎn)下標(biāo)
    int srcIndex = getIndexOfV(vSrc);
    int n = arrayV.length;
    //2、遍歷pPath數(shù)組 的n個(gè) 值，
    // 每個(gè)值到起點(diǎn)S的 路徑都打印一遍
    for (int i = 0; i < n; i++) {
        //自己到自己的路徑不打印
        if(i != srcIndex) {
            ArrayList<Integer> path = new ArrayList<>();
            int parentI = i;
            while (parentI != srcIndex) {
                path.add(parentI);
                parentI = pPath[parentI];
            }
            path.add(srcIndex);
            //翻轉(zhuǎn)path當(dāng)中的路徑
            Collections.reverse(path);
            for (int pos : path) {
                System.out.print(arrayV[pos] +" -> ");
            }
            System.out.println(dist[i]);
        }
    }
}

測(cè)試案例：

public static void testGraphDijkstra() {
    String str = "syztx";
    char[] array = str.toCharArray();
    GraphByMatrix g = new GraphByMatrix(str.length(),true);
    g.initArrayV(array);
    g.addEdge('s', 't', 10);
    g.addEdge('s', 'y', 5);
    g.addEdge('y', 't', 3);
    g.addEdge('y', 'x', 9);
    g.addEdge('y', 'z', 2);
    g.addEdge('z', 's', 7);
    g.addEdge('z', 'x', 6);
    g.addEdge('t', 'y', 2);
    g.addEdge('t', 'x', 1);
    g.addEdge('x', 'z', 4);
/*    
	搞不定負(fù)權(quán)值
    String str = "sytx";
    char[] array = str.toCharArray();
    GraphByMatrix g = new GraphByMatrix(str.length(),true);
    g.initArrayV(array);
    g.addEdge('s', 't', 10);
    g.addEdge('s', 'y', 5);
    g.addEdge('t', 'y', -7);
    g.addEdge('y', 'x', 3);
*/

    int[] dist = new int[array.length];
    int[] parentPath = new int[array.length];
    g.dijkstra('s', dist, parentPath);
    g.printShortPath('s', dist, parentPath);
}
public static void main(String[] args) {
    testGraphDijkstra();
}

1.3 堆優(yōu)化的Dijkstra算法

• 時(shí)間復(fù)雜度為O(N²)
  • 標(biāo)記N次，每次都要遍歷數(shù)組
  • 但是這個(gè)原始的算法，適合解決稠密圖的最短路徑~

• 但如果是稀疏圖的話，每次都遍歷一次數(shù)組，這個(gè)復(fù)雜度太大了
• 所以有了以下堆優(yōu)化的算法

本質(zhì)原理一樣：

定義存放在堆里面的類：

class Point {
    int index;
    int minPath;
}

1. 每次松弛都向堆里面放這個(gè)對(duì)象（而不是改變堆里面對(duì)應(yīng)index的值）

   • 堆是如何實(shí)現(xiàn)與dist數(shù)組一樣“更新”的呢？
   • 因?yàn)槲倚录尤氲倪@個(gè)對(duì)象，會(huì)比堆原本的那個(gè)index值的那個(gè)值要小，肯定會(huì)在其之前被取出

2. 取堆頂元素

   • 如果這個(gè)元素被標(biāo)記過，達(dá)咩，不要（continue）

   • 如果這個(gè)元素沒有被標(biāo)記過，喲西，標(biāo)記它，并且對(duì)其進(jìn)行松弛操作

     • 標(biāo)記后，其后面出現(xiàn)遺留的點(diǎn)也無所謂咯

而優(yōu)化后是適合稀疏圖的，因?yàn)樗沙谌攵巡僮鞯拇螖?shù)可以認(rèn)為是C常數(shù)，那么復(fù)雜度為O(N*log₂N)

• 但是如果是稠密圖，這個(gè)松弛入堆操作的次數(shù)則會(huì)接近于N，算法復(fù)雜度到達(dá)O(N²*log₂N)
• 比不優(yōu)化的還差

1.4 堆優(yōu)化Dijkstra算法代碼實(shí)現(xiàn)

定義Point類：

static class Point {
    int indexV;
    int distValue;

    public Point(int indexV, int distValue) {
        this.indexV = indexV;
        this.distValue = distValue;
    }
}

核心方法：

• 根據(jù)的就是剛才的算法!

/**
 *
 * @param src 出發(fā)點(diǎn)
 * @param dist 要求把最短路徑長存放在這個(gè)數(shù)組里
 * @param path 要求將前面點(diǎn)存放在這個(gè)數(shù)組里
 */
public void pQDijkstra(char src,int[] dist,int[] path) {
    //獲得頂點(diǎn)下標(biāo)
    int srcIndex = getIndexOfV(src);
    //初始化dist
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[srcIndex] = 0;//起始點(diǎn)

    //初始化path
    Arrays.fill(path, -1);
    path[srcIndex] = srcIndex;//如果是前一個(gè)頂點(diǎn)是本身的話，則說明到達(dá)起始點(diǎn)

    //定義visited數(shù)組
    int n = arrayV.length;
    boolean[] visited = new boolean[n];

    //定義小根堆
    PriorityQueue<Point> queue = new PriorityQueue<Point>(
            (o1, o2) -> {
                return o1.distValue - o2.distValue;
            }
    );

    queue.offer(new Point(srcIndex, 0));
    while(!queue.isEmpty()) {
        Point point = queue.poll();
        int index = point.indexV;
        //被標(biāo)記過，達(dá)咩！
        if(visited[index]) {
            continue;
        }
        //標(biāo)記
        visited[index] = true;
        //松弛
        for (int j = 0; j < n; j++) {
            //被必要松弛到標(biāo)記的頂點(diǎn)的，因?yàn)闆]用（再之前的證明中），你要也可以
            if(!visited[j] && matrix[index][j] != Integer.MAX_VALUE
                    && dist[index] + matrix[index][j] < dist[j]) {
                //松弛導(dǎo)致的更新操作，更新其路徑為【0，index】延伸一條邊【index，j】
                dist[j] = dist[index] + matrix[index][j];
                path[j] = index;
                queue.offer(new Point(j, dist[j]));
            }
        }
    }
}

測(cè)試：

g.pQDijkstra('s', dist, parentPath);
g.printShortPath('s', dist, parentPath);

public static void main(String[] args) {
    testGraphDijkstra();
}

• 跟剛才一樣的案例

結(jié)果一致：

2. Bellman-Ford算法【單源最短路徑】

如果把Dijkstra算法稱為深度優(yōu)先，那么Bellman-Ford算法就是廣度優(yōu)先，也更加直接與粗暴

• 簡稱BF（更暴力算法BF還真對(duì)上了O(∩_∩)O哈哈~）

與Dijkstra算法不同，其可以解決帶負(fù)權(quán)的圖的最短路徑問題！

用到Dijkstra用過的操作：

不同的是它的算法步驟：

1. 對(duì)全局所有的頂點(diǎn)，都進(jìn)行一次松弛操作
2. 這里不做任何標(biāo)記，因?yàn)楝F(xiàn)在直接相連的點(diǎn)，最終如果有負(fù)權(quán)，還是有可能通過“邊數(shù)更長的最短路徑”到達(dá)該點(diǎn)
3. 這樣的操作進(jìn)行N - 1輪，N為頂點(diǎn)的個(gè)數(shù)
   • 如果這一次沒有做任何更新，則以后的松弛也不會(huì)有任何的更新，退出循環(huán)，結(jié)束！

獲得最短路徑：

• 通過path數(shù)組，不斷向出發(fā)點(diǎn)方向“跳”，直到到達(dá)出發(fā)點(diǎn)

例子：

動(dòng)圖演示：

來源：【熊羊一鍋鮮】Ep.13 單源最短路徑Bellman-Ford算法及SPFA算法_嗶哩嗶哩_bilibili

2.1 BF算法證明

一些點(diǎn)在Dijkstra的證明那已經(jīng)講過了

• 不同的一點(diǎn)在于，BF算法松弛操作的頂點(diǎn)，每一次都是所有頂點(diǎn)~

你也會(huì)發(fā)現(xiàn)，一開始如果先松弛的不是出發(fā)點(diǎn)，或者是“已經(jīng)有路徑的頂點(diǎn)”，這個(gè)松弛操作是沒有意義的，因?yàn)檫@個(gè)頂點(diǎn)的dist值為∞

• 這也衍生出了一個(gè)問題：頂點(diǎn)松弛的先后會(huì)不會(huì)有影響

2. 第N代最短路徑中“邊最長為N”的子圖范圍內(nèi)，各個(gè)頂點(diǎn)的dist值在這個(gè)局部范圍內(nèi)【限制路徑最多有N條邊】是正確的，是最短的

這一點(diǎn)，是 通過松弛操作來保證 的，原本Dijkstra算法沒有保證這個(gè)子圖的完整性，而BF算法由于每次都是松弛所有頂點(diǎn)，所以這個(gè)子圖是完整的~

如第一代子圖（第一次循環(huán)的結(jié)果）：

如第二代子圖（第二次循環(huán)的結(jié)果）：

如第三代子圖（第三次循環(huán)的結(jié)果）：

你可能有一個(gè)錯(cuò)覺：這不是已經(jīng)涉及所有頂點(diǎn)了嗎，那么這就是在全局范圍內(nèi)的正確？

否，因?yàn)檫@里限制路徑長最大是“三條邊”，在這個(gè)限制下是正確的

• 例如【0到6】最短為三步，再走一步到7確實(shí)是11<12但是，這就是四步了呀

如第四代子圖（第四次循環(huán)的結(jié)果）：

到了第五代子圖的時(shí)候（第五次循環(huán)的結(jié)果）：

• 所有頂點(diǎn)都沒被更新~
• 跳出循環(huán)，算法結(jié)束
• 說明了里面“最長的最短路徑”是四條邊的

3. 頂點(diǎn)松弛的先后會(huì)不會(huì)有影響

其實(shí) 被松弛涉及到的頂點(diǎn)i有更新的條件 是：頂點(diǎn)j（頂點(diǎn)j松弛后涉及到了頂點(diǎn)i）更新過

而你也發(fā)現(xiàn)了這個(gè)算法產(chǎn)生了大量的沒用操作

1. 如果先對(duì)“后面”的頂點(diǎn)松弛，可能沒有作用
2. 假設(shè)此次是第n次循環(huán)，那么一個(gè)頂點(diǎn)目前最短路徑邊數(shù)小于等于n-2的頂點(diǎn)
   • 例如第二次循環(huán)的時(shí)候，出發(fā)點(diǎn)沒必要松弛
   • 第三次循環(huán)的時(shí)候，最短路徑邊數(shù)為1的頂點(diǎn)沒有必要松弛
     • 因?yàn)樗沙谕旰笞疃酁閮蓷l邊，而兩條邊的時(shí)候在第二代子圖（第二次循環(huán)結(jié)果）中，已經(jīng)是得到最短的了
     • 所以沒有必要！

你可能會(huì)覺得，先松弛出發(fā)點(diǎn)，那么可能“后面的頂點(diǎn)”也會(huì)鏈?zhǔn)降谋桓碌?/strong>

//這也是判斷是否有負(fù)權(quán)回路的算法
public boolean bellmanFord(char src,int[] dist,int[] path) {
    //獲得頂點(diǎn)下標(biāo)
    int srcIndex = getIndexOfV(src);
    //初始化dist
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[srcIndex] = 0;//起始點(diǎn)

    //初始化path
    Arrays.fill(path, -1);
    path[srcIndex] = srcIndex;//如果是前一個(gè)頂點(diǎn)是本身的話，則說明到達(dá)起始點(diǎn)

    int n = arrayV.length;

    //循環(huán)n-1次，每次松弛一個(gè)頂點(diǎn)
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
  				if(matrix[j][k] != Integer.MAX_VALUE && 
                            matrix[j][k] + dist[j] < dist[k]) {
                        dist[k] = matrix[j][k] + dist[j];
                        path[k] = j;
                }
            }
        }
    }
    //檢測(cè)負(fù)權(quán)回路
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //至于一樣短的情況下，無所謂，這就是最短路徑不唯一唄~
            //
            if (matrix[i][j] != Integer.MAX_VALUE 
                && matrix[i][j] + dist[i] < dist[j]) {
                return false; //false代表了有負(fù)權(quán)回路

            }
        }
    }
    return true;
}

public static void testGraphBellmanFord() {
    String str = "syztx";
    char[] array = str.toCharArray();
    GraphByMatrix g = new GraphByMatrix(str.length(),true);
    g.initArrayV(array);
    g.addEdge('s', 't', 6);
    g.addEdge('s', 'y', 7);
    g.addEdge('y', 'z', 9);
    g.addEdge('y', 'x', -3);
    g.addEdge('z', 's', 2);
    g.addEdge('z', 'x', 7);
    g.addEdge('t', 'x', 5);
    g.addEdge('t', 'y', 8);
    g.addEdge('t', 'z', -4);
    g.addEdge('x', 't', -2);
    //負(fù)權(quán)回路實(shí)例
    //        g.addEdge('s', 't', 6);
    //        g.addEdge('s', 'y', 7);
    //        g.addEdge('y', 'z', 9);
    //        g.addEdge('y', 'x', -3);
    //        g.addEdge('y', 's', 1);
    //        g.addEdge('z', 's', 2);
    //        g.addEdge('z', 'x', 7);
    //        g.addEdge('t', 'x', 5);
    //        g.addEdge('t', 'y', -8);
    //        g.addEdge('t', 'z', -4);
    //        g.addEdge('x', 't', -2);
    int[] dist = new int[array.length];
    int[] parentPath = new int[array.length];
    boolean flg = g.bellmanFord('s', dist, parentPath);
    if(flg) {
        g.printShortPath('s', dist, parentPath);
    }else {
        System.out.println("存在負(fù)權(quán)回路");
    }
}
public static void main(String[] args) {
    testGraphDijkstra();
}

public void queueBellmanFord(char src,int[] dist,int[] path) {
    //獲得頂點(diǎn)下標(biāo)
    int srcIndex = getIndexOfV(src);
    //初始化dist
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[srcIndex] = 0;//起始點(diǎn)

    //初始化path
    Arrays.fill(path, -1);
    path[srcIndex] = srcIndex;//如果是前一個(gè)頂點(diǎn)是本身的話，則說明到達(dá)起始點(diǎn)

    int n = arrayV.length;

    //定義一個(gè)隊(duì)列
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(srcIndex);

    //開始循環(huán)松弛
    while(!queue.isEmpty()) {
        int top = queue.poll();
        for (int i = 0; i < n; i++) {
            if (matrix[top][i] != Integer.MAX_VALUE
                    && matrix[top][i] + dist[top] < dist[i]) {
                dist[i] = matrix[top][i] + dist[top];
                path[i] = top;
                queue.offer(i);
            }
        }
    }
}

public static void testGraphBellmanFord() {
    String str = "syztx";
    char[] array = str.toCharArray();
    GraphByMatrix g = new GraphByMatrix(str.length(),true);
    g.initArrayV(array);
    g.addEdge('s', 't', 6);
    g.addEdge('s', 'y', 7);
    g.addEdge('y', 'z', 9);
    g.addEdge('y', 'x', -3);
    g.addEdge('z', 's', 2);
    g.addEdge('z', 'x', 7);
    g.addEdge('t', 'x', 5);
    g.addEdge('t', 'y', 8);
    g.addEdge('t', 'z', -4);
    g.addEdge('x', 't', -2);
    int[] dist = new int[array.length];
    int[] parentPath = new int[array.length];
    g.queueBellmanFord('s', dist, parentPath);
    g.printShortPath('s', dist, parentPath);
}
public static void main(String[] args) {
    testGraphDijkstra();
}

public void floydWarShall(int[][] dist, int[][] path) {
    //初始化dist和path
    int n = arrayV.length;
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], Integer.MAX_VALUE);
        Arrays.fill(path[i], -1);
    }

    //每一個(gè)頂點(diǎn)的第一代子圖，記錄在dist和path中，現(xiàn)在局部的最短路徑
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(matrix[i][j] != Integer.MAX_VALUE) {
                dist[i][j] = matrix[i][j];
                path[i][j] = i;//這一行的上一個(gè)就是i
            }else {
                path[i][j] = -1;//不存在路徑
            }
            if(i == j) {
                dist[i][j] = 0;
                path[i][j] = j;//跳回本身
            }
        }
    }
    //進(jìn)行算法，每個(gè)頂點(diǎn)都當(dāng)一回中介點(diǎn)
    //每個(gè)頂點(diǎn)都被當(dāng)做一次起始點(diǎn),終點(diǎn)
    //一個(gè)點(diǎn)即使起始點(diǎn)有時(shí)中介點(diǎn)又是終點(diǎn)，好像也無所謂
    //只要滿足那個(gè)方程！
    //順序完全沒關(guān)系~
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //規(guī)定k代表的是中介點(diǎn)，i為起始點(diǎn)，j為終點(diǎn)
                boolean flag = dist[i][k] != Integer.MAX_VALUE
                        && dist[k][j] != Integer.MAX_VALUE
                        && dist[i][k] + dist[k][j] < dist[i][j];
                //取不取等無所謂，只是不同最短路徑的區(qū)別罷了
                if (flag) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];//【i，j】以【k，j】為子路徑
                }

            }
        }
    }
}

public static void testGraphFloydWarShall() {
    String str = "12345";
    char[] array = str.toCharArray();
    GraphByMatrix g = new GraphByMatrix(str.length(),true);
    g.initArrayV(array);
    g.addEdge('1', '2', 3);
    g.addEdge('1', '3', 8);
    g.addEdge('1', '5', -4);
    g.addEdge('2', '4', 1);
    g.addEdge('2', '5', 7);
    g.addEdge('3', '2', 4);
    g.addEdge('4', '1', 2);
    g.addEdge('4', '3', -5);
    g.addEdge('5', '4', 6);
    int[][] dist = new int[array.length][array.length];
    int[][] path = new int[array.length][array.length];
    g.floydWarShall(dist,path);
    for (int i = 0; i < array.length; i++) {
        g.printShortPath(array[i],dist[i],path[i]);
        //把一行一行傳過去~
        //一行代表一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑
    }
}

public static void main(String[] args) {
    testGraphFloydWarShall();
}