本文為原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處
查看[數(shù)據(jù)結(jié)構(gòu)及算法]系列內(nèi)容請(qǐng)點(diǎn)擊：http://www.itdecent.cn/nb/45938463

本文通過(guò)一個(gè)例子及其變種，由淺入深解析常見(jiàn)的圖搜索算法。

例子如下：

假設(shè)有如下矩陣：

S表示開始節(jié)點(diǎn)，E表示結(jié)束節(jié)點(diǎn)

目標(biāo)：假如一個(gè)人站在圖中的S方格，他一次可以往上下左右方向移動(dòng)一格，但不能走到黑色的方格上，計(jì)算從S(Start)方格到E(End)方格最少需要走幾格？

這個(gè)問(wèn)題及其變種有很多種解決方案，下面我們說(shuō)【方格】或者說(shuō)【點(diǎn)】指的都是方格，下面就從這個(gè)問(wèn)題開始一一介紹這些算法。

DFS：深度優(yōu)先搜索算法

最簡(jiǎn)單（但不一定最適合）的方法就是深度優(yōu)先搜索算法，深度優(yōu)先一般使用遞歸策略，可以理解為窮舉從S到E的所有路徑，然后找到一個(gè)最短的路徑即可。需要注意的是，在一次搜索路徑中，已經(jīng)被走過(guò)的方格不能再次走上去。

假設(shè)我們搜索的方法是從S的12點(diǎn)方向順時(shí)針?biāo)阉鳎醋裱?code>先找最上面相鄰的點(diǎn)，其次找右上角，再次右邊的點(diǎn)...如此往復(fù)... 那么第一次從S搜索到E的路徑如下所示：

第一次搜索路徑

第二次搜索路徑

其中，灰色箭頭表示回退到上一個(gè)點(diǎn)，綠色箭頭表示繼續(xù)搜索的路徑。如此往復(fù)直到窮舉完所有的路徑為止，用代碼表示如下：

public class MainTest {
    // 定義移動(dòng)方向
    private static final int[][] directions = new int[][]{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

    private static int allPathCount = 0; // 記錄下所有走法的個(gè)數(shù)

    public static void main(String[] args) {
        int[][] g = new int[][]{
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0}
        };

        System.out.println(dfs(g, 2, 1, 2, 4)); // 輸出 4
        System.out.println("共有：" + allPathCount + "種走法"); // 共有：163506種走法
    }

    /**
     * g 表示初始化的圖，這里用0表示空白方格，1表示不可走方格，在程序里面，我們會(huì)用-1表示已經(jīng)走過(guò)的方格
     * 這里為了方便表示，使用行列來(lái)表示，而不是使用x、y來(lái)表示
     * (startLine, startColumn)和(endLine, endColumn) 分別表示起始和終止方格的行列
     */
    public static int dfs(int[][] g, int startLine, int startColumn, int endLine, int endColumn) {
        if (startLine == endLine && startColumn == endColumn) { // 到達(dá)E點(diǎn)
            allPathCount++;
            return 0;
        }

        g[startLine][startColumn] = -1; // 標(biāo)記為已經(jīng)走過(guò)

        int minStep = Integer.MAX_VALUE / 2;
        for (int[] direct : directions) {
            int newLine = startLine + direct[0];
            int newColumn = startColumn + direct[1];

            // 判斷不可走的格子
            if (newLine < 0 || newLine >= g.length || newColumn < 0 || newColumn >= g[0].length || g[newLine][newColumn] != 0)
                continue;

            int step = 1 + dfs(g, newLine, newColumn, endLine, endColumn); // 遞歸查找
            if (step < minStep) minStep = step;
        }
        g[startLine][startColumn] = 0; // 釋放標(biāo)記，讓其他路線可走

        return minStep;
    }
}

可以看到，上述結(jié)束輸出為4，實(shí)際上走的步數(shù)為4的路線為：

步數(shù)為4的走法之一

可以看到，走法一共有163506種，我們實(shí)際上需要將這么多種走法全部窮舉完，才可以計(jì)算出來(lái)走的步數(shù)的最小值，當(dāng)然，在實(shí)際運(yùn)用過(guò)程中，DFS可以在運(yùn)行過(guò)程中對(duì)其搜索樹進(jìn)行剪枝（比如對(duì)于當(dāng)前步數(shù)已經(jīng)大于全局到達(dá)目標(biāo)點(diǎn)步數(shù)的最小值了就沒(méi)必要繼續(xù)往下搜索了），可以很大程度上減少不必要的重復(fù)。

根據(jù)上面DFS的走法記錄，我們看到，基本思想是使用遞歸構(gòu)建一個(gè)隱式的搜索樹，然后窮舉樹的深度從而取出最小深度，其所要求的時(shí)間復(fù)雜度較高。時(shí)間復(fù)雜度分析如下：

• 第一個(gè)點(diǎn)具有8個(gè)方向，第二個(gè)點(diǎn)具有7個(gè)方向，那么整體需要搜索的次數(shù)約為：8×7×7×...×7 ，具有多少個(gè)7呢？我們分析，搜索樹的深度最多為n × m，n和m分別為矩陣行列數(shù)。總搜索節(jié)點(diǎn)數(shù)大約為8 ×7^(n×m)，所以總體上時(shí)間復(fù)雜度為 O(8^(n×m))，如果只能向上下左右4個(gè)方向移動(dòng)，那么時(shí)間復(fù)雜度為 O(4^(n×m))。總之，在最壞情況下，時(shí)間復(fù)雜度是指數(shù)級(jí)的。
• 如果我們不關(guān)注最短的步數(shù)，而是隨機(jī)找出一條路徑能夠到達(dá)終點(diǎn)，那么，時(shí)間復(fù)雜度為O(V+E)，其中，V是圖中邊的個(gè)數(shù)，E是圖中點(diǎn)的個(gè)數(shù)。
• 使用遞歸的話，空間復(fù)雜度與時(shí)間復(fù)雜度相等，使用棧來(lái)解決的話，空間復(fù)雜度為 O(n×m)

BFS：廣度優(yōu)先搜索算法

對(duì)于簡(jiǎn)單的尋路問(wèn)題，我們也可以使用廣度優(yōu)先搜素算法解決，從而大大縮小其時(shí)間復(fù)雜度。BFS的基本思想是每次從當(dāng)前節(jié)點(diǎn)擴(kuò)展一層，每次遍歷子節(jié)點(diǎn)的時(shí)候，依次將子節(jié)點(diǎn)往外擴(kuò)展一層，由于這樣的話步數(shù)最小的步驟總是在前面，所以當(dāng)某一次擴(kuò)展擴(kuò)展到了E點(diǎn)就可以結(jié)束了。同時(shí)，由于后擴(kuò)展的節(jié)點(diǎn)步長(zhǎng)肯定比前面擴(kuò)展的步長(zhǎng)更長(zhǎng)，所以可以設(shè)置全局訪問(wèn)過(guò)的節(jié)點(diǎn)不再繼續(xù)訪問(wèn)?；緮U(kuò)展步驟如下：

擴(kuò)展步驟：不同的顏色代表不同的擴(kuò)展步驟

public class MainTest {
    // 定義移動(dòng)方向
    private static final int[][] directions = new int[][]{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

    public static void main(String[] args) {
        int[][] g = new int[][]{
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0}
        };

        System.out.println(bfs(g, 2, 1, 2, 4)); // 輸出 4
    }

    /**
     * g 表示初始化的圖，這里用0表示空白方格，1表示不可走方格，在程序里面，我們會(huì)用-1表示已經(jīng)走過(guò)的方格
     * 這里為了方便表示，使用行列來(lái)表示，而不是使用x、y來(lái)表示
     * (startLine, startColumn)和(endLine, endColumn) 分別表示起始和終止方格的行列
     */
    public static int bfs(int[][] g, int startLine, int startColumn, int endLine, int endColumn) {
        Triple[] path = new Triple[g.length * g[0].length]; // 這里實(shí)際用Queue隊(duì)列更方便

        int head = 1, tail = 0;
        path[0] = new Triple(startLine, startColumn, 0); // 初始點(diǎn)入隊(duì)列
        g[startLine][startColumn] = -1; // 標(biāo)記初始點(diǎn)不可走

        while (head > tail) {
            Triple t = path[tail];
            for (int i = 0; i < directions.length; i++) {
                int newLine = t.line + directions[i][0];
                int newColumn = t.column + directions[i][1];

                // 找到直接返回
                if (newLine == endLine && newColumn == endColumn) return t.step + 1;
                if (newLine < 0 || newLine >= g.length || newColumn < 0 || newColumn >= g[0].length || g[newLine][newColumn] != 0)
                    continue;

                g[newLine][newColumn] = -1; // 標(biāo)記為已走過(guò)
                path[head++] = new Triple(newLine, newColumn, t.step + 1); //  繼續(xù)將子節(jié)點(diǎn)入隊(duì)列
            }

            tail++;
        }
        return -1;
    }

    private static class Triple {
        int line;
        int column;
        int step;

        public Triple(int line, int column, int step) {
            this.line = line;
            this.column = column;
            this.step = step;
        }
    }
}

后面很多的算法都借鑒了BFS算法，并進(jìn)行了一定的變化。

• 使用邊和點(diǎn)來(lái)表示的話，時(shí)間復(fù)雜度為O(V+E)，其中V是點(diǎn)的個(gè)數(shù)，E是邊的個(gè)數(shù)，上面的例子里面，邊的個(gè)數(shù)約有n×m×8個(gè)（忽略邊緣和不可走的點(diǎn)周邊的邊不到8個(gè)的情況），所以時(shí)間復(fù)雜度為：O(n×m×9)

A*算法：?jiǎn)l(fā)式尋路

下面我們把上面的題目變換一下：

假設(shè)還是上面的圖，從任意方格橫向或者豎向走，所需要走的步數(shù)為2，斜向走需要走的步數(shù)為3，請(qǐng)問(wèn)最少需要多少步數(shù)能從S點(diǎn)走到E點(diǎn)？（后續(xù)將步數(shù)也稱為代價(jià)）

很明顯，這里就是一個(gè)帶權(quán)的圖搜索問(wèn)題了。當(dāng)我們可以大概評(píng)估從任意一格走到終點(diǎn)E的代價(jià)的時(shí)候，就可以使用A算法，A算法實(shí)際上是一種貪心算法，由Dijkstra算法改進(jìn)而來(lái)，下面詳細(xì)介紹。

A*算法基本元素

• 在A*算法中，需要維護(hù)兩個(gè)列表，一個(gè)是open list列表，用來(lái)存儲(chǔ)在下一次搜索中可能會(huì)被搜索到的點(diǎn)，open list是一個(gè)按照后面說(shuō)的F值從小到大排好序的list，open list一開始只有一個(gè)起點(diǎn)。
• 第二個(gè)列表是close list列表，已經(jīng)檢測(cè)過(guò)的節(jié)點(diǎn)放入close list，在close list中的點(diǎn)不會(huì)再次被檢測(cè)。
• 父節(jié)點(diǎn)，記錄回溯的節(jié)點(diǎn)，如果只是找出最短路徑的長(zhǎng)度，不進(jìn)行回溯的話，則不需要父節(jié)點(diǎn)。
• 路徑排序，F值，F = G + H，其中，G為從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)，H為從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估算代價(jià)，即：?jiǎn)l(fā)函數(shù)。
• 啟發(fā)函數(shù)，即H，用來(lái)估算從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的代價(jià)，啟發(fā)函數(shù)的選擇好壞會(huì)直接影響算法的性能與結(jié)果。這里就使用曼哈頓距離，即橫縱向走的代價(jià)之和：H=|(i_S-i_K)|×2 + |(j_S-j_K)|×2，2是走一格的代價(jià)。

算法流程

• 1、把起點(diǎn)S加入到open list中，并估算S點(diǎn)的F值；
• 2、從open list中取出一個(gè)F值最小的點(diǎn)P，向周圍一格（橫豎向或斜向）擴(kuò)展點(diǎn)，并遵循3、4、5規(guī)則；
• 3、若周圍的某個(gè)格子不可走或在close list中，則忽略；
• 4、若周圍的某個(gè)格子不在open list或close list中，且可走，則估算其F值，并按照F值從小到大將該格子加入open list；
• 5、若周圍某個(gè)格子在open list中，且該節(jié)點(diǎn)的F值大于：P點(diǎn)的F值+該節(jié)點(diǎn)的H值+P到該節(jié)點(diǎn)的代價(jià)，則更新該節(jié)點(diǎn)的F值，并將該節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為P點(diǎn)。
• 6、重復(fù)步驟2，直到找到S點(diǎn)為止。

按照以上步驟，我們可以看到第一次的搜索路徑如下（對(duì)于具有相同的F值的點(diǎn)，隨便選取一個(gè)擴(kuò)展即可）：

第一次搜索擴(kuò)展，灰色S代表加入到close list中的點(diǎn)

第二次搜索擴(kuò)展如下：

第二次搜索擴(kuò)展，灰色字體格子代表加入close list的點(diǎn)

經(jīng)過(guò)多輪擴(kuò)展后的最終結(jié)果：

最終結(jié)果，F(xiàn)=11

最終計(jì)算，最先到達(dá)E點(diǎn)的路徑F=11，這里F值就代表其最終代價(jià)。
可以看到，H函數(shù)的選擇對(duì)于評(píng)估具有非常重要的作用更高，H函數(shù)會(huì)直接影響最終結(jié)果。
A*算法實(shí)現(xiàn)的代碼如下：

import java.util.*;

public class MainTest {
    // 定義移動(dòng)方向
    private static final int[][] directions = new int[][]{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
    private static final int[] walkStep = new int[]{2, 3, 2, 3, 2, 3, 2, 3}; // 八個(gè)方向走一步的代價(jià)

    public static void main(String[] args) {
        int[][] g = new int[][]{
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0}
        };

        System.out.println(aStar(g, 2, 1, 2, 4)); // 輸出 11
    }

    public static int aStar(int[][] g, int startLine, int startColumn, int endLine, int endColumn) {
        List<Point> openList = new ArrayList<>(); // close list中的節(jié)點(diǎn)我們直接將其值置為-1，不再單獨(dú)開list保存，在open list中的點(diǎn)標(biāo)記為2
        Point[][] pointIndex = new Point[g.length][g[0].length]; // 用于加快從(line, column)查找Point的效率

        openList.add(new Point(startLine, startColumn, 0, endLine, endColumn));
        g[startLine][startColumn] = 2; // 這一行不是必須的，只是為了讓邏輯更清晰
        pointIndex[startLine][startColumn] = openList.get(0);

        while (openList.size() > 0) {
            Point p = openList.remove(0);
            g[p.line][p.column] = -1;

            for (int i = 0; i < directions.length; i++) {
                int newLine = p.line + directions[i][0];
                int newColumn = p.column + directions[i][1];

                // 找到直接返回
                if (newLine == endLine && newColumn == endColumn) return p.G + walkStep[i];

                // 不可走或已經(jīng)在close list中，則忽略
                if (newLine < 0 || newLine >= g.length || newColumn < 0 || newColumn >= g[0].length || (g[newLine][newColumn] != 0 && g[newLine][newColumn] != 2))
                    continue;

                // 若沒(méi)有在open list中則加入
                if (g[newLine][newColumn] != 2) {
                    g[newLine][newColumn] = 2;
                    Point p1 = new Point(newLine, newColumn, p.G + walkStep[i], endLine, endColumn);
                    insertOpenList(openList, p1);
                    pointIndex[newLine][newColumn] = p1;
                } else { // 若在open list中，則根據(jù)情況更新
                    int newF = p.G + walkStep[i] + Math.abs((endLine - newLine) * 2) + Math.abs((endColumn - newColumn) * 2);
                    if (newF < pointIndex[newLine][newColumn].F) {
                        Point p1 = new Point(newLine, newColumn, p.G + walkStep[i], endLine, endColumn);
                        openList.remove(pointIndex[newLine][newColumn]);
                        insertOpenList(openList, p1);
                        pointIndex[newLine][newColumn] = p1;
                    }
                }
            }
        }

        return -1;
    }

    // 插入列表
    public static void insertOpenList(List<Point> openList, Point p) {
        int insertIndex = Collections.binarySearch(openList, p, (a, b) -> a.F - b.F); // 二分查找需要插入的地方
        if (insertIndex < 0) insertIndex = -(insertIndex + 1);

        openList.add(insertIndex, p);
    }

    private static class Point {
        int line;
        int column;
        int F;
        int G;
        int H;

        // 自動(dòng)計(jì)算F值
        public Point(int line, int column, int G, int endLine, int endColumn) {
            this.line = line;
            this.column = column;
            this.G = G;
            this.H = Math.abs((endLine - line) * 2) + Math.abs((endColumn - column) * 2);
            this.F = this.G + this.H;
        }
    }
}

A*算法的時(shí)間復(fù)雜度不是很好估計(jì)，但是可以初步估計(jì)其 空間復(fù)雜度為O(V)量級(jí)，時(shí)間復(fù)雜度取決于H函數(shù)的計(jì)算策略、排序方法等，我們這里的H函數(shù)復(fù)雜度為O(1)，排序算法為O(log(V))，對(duì)于每一個(gè)需要插入的點(diǎn)都需要一次或多次排序，在極限情況下可以認(rèn)為對(duì)檢查每條邊都需要進(jìn)行一次排序，那么排序次數(shù)為E次，點(diǎn)的個(gè)數(shù)為V，邊的個(gè)數(shù)為E，那么按照排序來(lái)算，時(shí)間復(fù)雜度為O(E×log(V))

Dijkstra算法

剛剛在A*算法中，我們認(rèn)為上下左右走的時(shí)候，其步數(shù)為2，斜向走的時(shí)候步數(shù)為3，實(shí)際上就是我們?yōu)檫呥M(jìn)行了加權(quán)，為了更加方便的討論，我們從這里開始，將上面的矩陣進(jìn)行簡(jiǎn)化，簡(jiǎn)化為圖的形式，并進(jìn)行一部分點(diǎn)的簡(jiǎn)化和邊的加權(quán)簡(jiǎn)化。

簡(jiǎn)化后的圖 如下所示：

圖，邊上的數(shù)字表示從一個(gè)點(diǎn)到另外一個(gè)點(diǎn)所需的代價(jià)

如上圖所示，一共有6個(gè)點(diǎn)，點(diǎn)之間可以互相連接，也可以不互相連接，箭頭上的數(shù)字代表了從一個(gè)點(diǎn)到另外一個(gè)點(diǎn)所需要走的步數(shù)（代價(jià)），試求從S點(diǎn)到E點(diǎn)所需要的最小代價(jià)。

Dijkstra算法屬于典型的貪心算法，算法思想是記錄從S點(diǎn)到達(dá)每一個(gè)點(diǎn)的當(dāng)前最短路徑，然后不斷通過(guò)“松弛”操作來(lái)進(jìn)行調(diào)整最短路徑長(zhǎng)度。算法的基本步驟如下：

• 1、初始化一個(gè)列表L，記錄其余的各個(gè)點(diǎn)和S到達(dá)他們的距離，不能直達(dá)的則標(biāo)記距離為無(wú)窮大，對(duì)于L中能直達(dá)的點(diǎn)集合，我們標(biāo)記為L1，不能直達(dá)的點(diǎn)集合標(biāo)記為L2，所以：L = L1 ∪ L2，然后進(jìn)行第2步的松弛操作；
• 2、從L2中取出一個(gè)點(diǎn)P，點(diǎn)P需要滿足條件：P是L2中距離L1中所有的點(diǎn)距離最近的點(diǎn)。然后將P加入L1并計(jì)算最短的距離，如果L2中的某點(diǎn)Q距離S的距離滿足：distance(S -> Q) 大于 distance(s -> P ->Q)，那么更新其距離為distance(s -> P ->Q)。
• 3、重復(fù)操作2，直到所有L2為空，或者L2中的點(diǎn)不能加入到L1（非連通圖）為止。

按照上述步驟模擬，最終會(huì)找出從S到E的最短路徑為：

綠色代表最短路線

Java實(shí)現(xiàn)的代碼如下：

import java.util.*;

public class MainTest {

    public static void main(String[] args) {
        // 初始化圖
        Point S = new Point('S');
        Point p1 = new Point('p');
        Point p2 = new Point('p');
        Point p3 = new Point('p');
        Point p4 = new Point('p');
        Point E = new Point('E');

        S.addChild(p1, 3);
        S.addChild(p2, 12);
        p2.addChild(p1, 5);
        p1.addChild(p3, 8);
        p3.addChild(p4, 1);
        p2.addChild(p4, 30);
        p3.addChild(E, 10);
        p4.addChild(E, 2);

        System.out.println(dijkstra(S, E)); // 輸出 14
    }

    public static int dijkstra(Point S, Point E) {
        Map<Point, Integer> L1 = new HashMap<>(); // L1列表，為了加快效率這里使用HashMap, key=Point value=length
        L1.put(S, 0);

        while (true) {
            Point P = null;
            int minLen = Integer.MAX_VALUE / 2;

            // 尋找L1中的點(diǎn)的所有子節(jié)點(diǎn)
            for (Point Q : L1.keySet()) {
                int existWeight = L1.get(Q);

                for (int i = 0; i < Q.children.size(); i++) {
                    if (L1.containsKey(Q.children.get(i))) continue; // 在L1列表中的忽略

                    if (existWeight + Q.weight.get(i) < minLen) {
                        minLen = existWeight + Q.weight.get(i);
                        P = Q.children.get(i);
                        break; // 這里是一個(gè)小優(yōu)化，插入的時(shí)候把權(quán)重最小的放在前面，這里可以直接break
                    }
                }
            }

            if (P == null) break;
            if (P == E) return minLen;
            L1.put(P, minLen);
// TODO 這里由于上面是兩層循環(huán)所以沒(méi)有做松弛操作
        }

        return -1;
    }

    // 定義節(jié)點(diǎn)類型
    private static class Point {
        char name;
        List<Point> children = new ArrayList<>(); // 子節(jié)點(diǎn)
        List<Integer> weight = new ArrayList<>(); // 邊的權(quán)重

        Point(char n) {
            this.name = n;
        }

        // 插入的時(shí)候注意，權(quán)重最小的放在最前面
        void addChild(Point p, int w) {
            int insertIndex = Collections.binarySearch(weight, w, (a, b) -> a - b); // 二分法查找插入index
            if (insertIndex < 0) insertIndex = -(insertIndex + 1);

            children.add(insertIndex, p);
            weight.add(insertIndex, w);
        }
    }
}

可以看到，實(shí)際上Dijkstra算法在計(jì)算的過(guò)程中，在找到目標(biāo)節(jié)點(diǎn)的時(shí)候不返回，那么就求出了從S點(diǎn)到其他任意一點(diǎn)的最短距離。所以該算法比較適合用來(lái)求從某個(gè)特定的點(diǎn)到另外其他的所有點(diǎn)的最短距離。

Dijkstra算法的時(shí)間復(fù)雜度，內(nèi)層的for循環(huán)需要循環(huán)K次，K = 1 + 2 + 3 + ... + (V-1) = (V^2) / 2，總體時(shí)間復(fù)雜度為O(V^2)。這里為了加快搜索速度，使用了一個(gè)HashMap來(lái)存儲(chǔ)Point，所以空間復(fù)雜度為O(V)

Floyd算法：尋找圖中任意兩點(diǎn)的最短距離

我們將上面題目變一下：

請(qǐng)輸出圖中任意兩點(diǎn)之間的距離。

最簡(jiǎn)單的辦法是對(duì)每個(gè)節(jié)點(diǎn)都跑一次Dijkstra算法，時(shí)間復(fù)雜度為O(V^3)，這里我們不介紹這種方法。我們主要介紹Floyd算法。

Floyd算法是一種使用動(dòng)態(tài)規(guī)劃思想來(lái)進(jìn)行計(jì)算路徑的算法。對(duì)于圖中的任意三個(gè)點(diǎn)i, j, k，我們用distance(i,j)表示從i到j的距離，用distance(i, k, j)表示i經(jīng)過(guò)k再到j的距離，主要思路是：

if distance(A, B) > distance(A, C, B) then: distance(A, B) = distance(A, C, B)

Floyd算法一般為了好計(jì)算，使用鄰接矩陣來(lái)進(jìn)行表示圖。
如下圖，用鄰接矩陣對(duì)每個(gè)點(diǎn)都進(jìn)行編號(hào)，表示如下：

圖中為每個(gè)節(jié)點(diǎn)進(jìn)行了編號(hào)

圖的鄰接矩陣表示，不可直達(dá)的點(diǎn)距離為無(wú)窮大

算法基本思路：

每次選取一個(gè)中間點(diǎn)k，窮舉i和j點(diǎn)，如果distance(i,j) > distance(i,k,j)則更新distance(i,j)=distance(i,k,j)

代碼實(shí)現(xiàn)：

public class MainTest {
    private static int X = Integer.MAX_VALUE / 2; // 表示無(wú)窮大

    public static void main(String[] args) {
        int[][] g = new int[][]{
                {0, 3, X, 12, X, X},
                {X, 0, 8, X, X, X},
                {X, X, 0, X, 1, 10},
                {X, 5, X, 0, 30, X},
                {X, X, X, X, 0, 2},
                {X, X, X, X, X, 0}
        };

        int[][] distance = floyd(g);
        for (int i = 0; i < distance.length; i++) {
            for (int j = 0; j < distance[i].length; j++)
                System.out.println("" + i + " -> " + j + " : " + distance[i][j]);
        }
    }

    public static int[][] floyd(int[][] g) {
        int[][] distance = g;  // 這里偷個(gè)懶，直接用圖的原始權(quán)重表示距離

        for (int k = 0; k < g.length; k++) {
            for (int i = 0; i < g.length; i++) {
                for (int j = 0; j < g.length; j++) {
                    if (i == j) continue;
                    if (distance[i][j] > distance[i][k] + distance[k][j])
                        distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }

        return distance;
    }
}

輸出結(jié)果：

0 -> 0 : 0
0 -> 1 : 3
0 -> 2 : 11
0 -> 3 : 12
0 -> 4 : 12
0 -> 5 : 14
1 -> 0 : 1073741823
1 -> 1 : 0
1 -> 2 : 8
1 -> 3 : 1073741823
1 -> 4 : 9
1 -> 5 : 11
2 -> 0 : 1073741823
2 -> 1 : 1073741823
2 -> 2 : 0
2 -> 3 : 1073741823
2 -> 4 : 1
2 -> 5 : 3
3 -> 0 : 1073741823
3 -> 1 : 5
3 -> 2 : 13
3 -> 3 : 0
3 -> 4 : 14
3 -> 5 : 16
4 -> 0 : 1073741823
4 -> 1 : 1073741823
4 -> 2 : 1073741823
4 -> 3 : 1073741823
4 -> 4 : 0
4 -> 5 : 2
5 -> 0 : 1073741823
5 -> 1 : 1073741823
5 -> 2 : 1073741823
5 -> 3 : 1073741823
5 -> 4 : 1073741823
5 -> 5 : 0

可以看到，輸出數(shù)字特別大的就是從i到j不可到達(dá)的，我們看0 -> 5 : 14與上面Dijkstra計(jì)算的結(jié)果一致。

Floyd算法時(shí)間復(fù)雜度為O(V^3)，由于一般需要（我們的代碼里面并沒(méi)有）有一個(gè)數(shù)組來(lái)存儲(chǔ)計(jì)算結(jié)果，所以空間復(fù)雜度為O(V)

Bellman-Form算法：解決帶負(fù)權(quán)回路的最短路徑算法

我們將上面Dijkstra算法用到的圖添加一條邊：

從4到3多了一條權(quán)重為-15的邊

在進(jìn)行松弛操作的時(shí)候，假如當(dāng)前L1列表中包含了S, 1, 2, 4點(diǎn)，當(dāng)想納入3點(diǎn)的時(shí)候，會(huì)發(fā)現(xiàn)，經(jīng)過(guò)3到達(dá)1點(diǎn)更近，從S到達(dá)1點(diǎn)直接距離為3，經(jīng)過(guò)3點(diǎn)后從S到達(dá)1點(diǎn)的距離變?yōu)榱?，同時(shí)也會(huì)涉及到2點(diǎn)的距離更新。而我們?cè)贒ijkstra中并沒(méi)有這種更新機(jī)制。

實(shí)際上，對(duì)于上面的情況，我們無(wú)法求出S點(diǎn)到達(dá)1, 2, 3, 4, 5點(diǎn)的最短路徑，或者最短路徑為負(fù)無(wú)窮大。Bellman-Form算法就是在Dijkstra的基礎(chǔ)上進(jìn)行了負(fù)權(quán)環(huán)狀回路的檢測(cè)，檢測(cè)到這種情況就返回并告知無(wú)法求出。

負(fù)權(quán)回路實(shí)際上指的是回路上所有權(quán)重的最小值相加后的值是負(fù)的，比如上面的圖，如果點(diǎn)4到點(diǎn)3的權(quán)重為-5，那么就不會(huì)存在問(wèn)題。

那么如何檢測(cè)負(fù)權(quán)回路呢？這里給一個(gè)公式：

如果松弛完成以后還存在 distance(v) > distance(u) + w(u,v)，那么就存在負(fù)權(quán)回路。帶入上圖，v就是點(diǎn)2，u就是點(diǎn)1

首先，我們拿Dijkstra算法來(lái)改一下：

import java.util.*;

public class MainTest {

    public static void main(String[] args) {
        // 初始化圖
        Point S = new Point('S');
        Point p1 = new Point('p');
        Point p2 = new Point('p');
        Point p3 = new Point('p');
        Point p4 = new Point('p');
        Point E = new Point('E');

        S.addChild(p1, 3);
        S.addChild(p2, 12);
        p2.addChild(p1, 5);
        p1.addChild(p3, 8);
        p3.addChild(p4, 1);
        p2.addChild(p4, 30);
        p3.addChild(E, 10);
        p4.addChild(E, 2);
        p4.addChild(p2, -15); // 添加一個(gè)權(quán)重為-15的邊

        System.out.println(dijkstra(S, 6)); //輸出 null
    }

    // 這里改成了返回從`S`點(diǎn)到到其他所有點(diǎn)的最短路徑
    public static Map<Point, Integer> dijkstra(Point S, int pointCount) {
        Map<Point, Integer> L1 = new HashMap<>(); // L1列表，為了加快效率這里使用HashMap, key=Point value=length
        L1.put(S, 0);

        while (true) {
            Point P = null;
            int minLen = Integer.MAX_VALUE / 2;

            // 尋找L1中的點(diǎn)的所有子節(jié)點(diǎn)
            for (Point Q : L1.keySet()) {
                int existWeight = L1.get(Q);

                for (int i = 0; i < Q.children.size(); i++) {
                    if (L1.containsKey(Q.children.get(i))) continue; // 在L1列表中的忽略

                    if (existWeight + Q.weight.get(i) < minLen) {
                        minLen = existWeight + Q.weight.get(i);
                        P = Q.children.get(i);
                        break; // 這里是一個(gè)小優(yōu)化，插入的時(shí)候把權(quán)重最小的放在前面，這里可以直接break
                    }
                }
            }

            if (P == null) break;
            L1.put(P, minLen);
        }

        // 如果有的點(diǎn)不可達(dá)，返回null
        if (pointCount != L1.size()) return null;

        // 檢測(cè)負(fù)權(quán)回路
        for (Point v : L1.keySet()) {
            int distanceV = L1.get(v);
            for (Point u : L1.keySet()) {
                int distanceU = L1.get(u);
                int w = Integer.MAX_VALUE / 2;
                if (u.children.contains(v)) w = u.weight.get(u.children.indexOf(v));
                if (distanceV > distanceU + w) return null;
            }
        }

        return L1;
    }

    // 定義節(jié)點(diǎn)類型
    private static class Point {
        char name;
        List<Point> children = new ArrayList<>(); // 子節(jié)點(diǎn)
        List<Integer> weight = new ArrayList<>(); // 邊的權(quán)重

        Point(char n) {
            this.name = n;
        }

        // 插入的時(shí)候注意，權(quán)重最小的放在最前面
        void addChild(Point p, int w) {
            int insertIndex = Collections.binarySearch(weight, w, (a, b) -> a - b); // 二分法查找插入index
            if (insertIndex < 0) insertIndex = -(insertIndex + 1);

            children.add(insertIndex, p);
            weight.add(insertIndex, w);
        }
    }
}

如果可以不用Dijkstra算法，而定義另外一種松弛操作：

// w[j -> i]表示從j直接到i的權(quán)重
if distance[i] > distance[j] + w[j -> i] then distance[i] = distance[j] + w[j -> i]

代碼如下：

import java.util.*;

public class MainTest {

    public static void main(String[] args) {
        // 初始化圖
        Point S = new Point('S');
        Point p1 = new Point('p');
        Point p2 = new Point('p');
        Point p3 = new Point('p');
        Point p4 = new Point('p');
        Point E = new Point('E');

        S.addChild(p1, 3);
        S.addChild(p2, 12);
        p2.addChild(p1, 5);
        p1.addChild(p3, 8);
        p3.addChild(p4, 1);
        p2.addChild(p4, 30);
        p3.addChild(E, 10);
        p4.addChild(E, 2);
        p4.addChild(p2, -15); // 添加一個(gè)權(quán)重為-15的邊

        List<Point> points = Arrays.asList(S, p1, p2, p3, p4, E);
        System.out.println(bellmanForm(S, points)); //輸出 null
    }

    // 這里改成了返回從`S`點(diǎn)到到其他所有點(diǎn)的最短路徑
    public static Map<Point, Integer> bellmanForm(Point S, List<Point> points) {
        Map<Point, Integer> L1 = new HashMap<>(); // L1列表，為了加快效率這里使用HashMap, key=Point value=length
        for (Point p : points) L1.put(p, p == S ? 0 : Integer.MAX_VALUE / 2);

        // 松弛操作
        for (int t = 1; t < points.size(); t++) {
            for (int i = 0; i < points.size(); i++) {
                List<Point> children = points.get(i).children;
                List<Integer> weight = points.get(i).weight;
                for (int j = 0; j < children.size(); j++) {
                    if (L1.get(points.get(i)) > L1.get(children.get(j)) + weight.get(j)) {
                        L1.put(points.get(i), L1.get(children.get(j)) + weight.get(j));
                    }
                }
            }
        }

        // 檢測(cè)負(fù)權(quán)回路
        for (Point v : L1.keySet()) {
            int distanceV = L1.get(v);
            for (Point u : L1.keySet()) {
                int distanceU = L1.get(u);
                int w = Integer.MAX_VALUE / 2;
                if (u.children.contains(v)) w = u.weight.get(u.children.indexOf(v));
                if (distanceV > distanceU + w) return null;
            }
        }

        return L1;
    }

    // 定義節(jié)點(diǎn)類型
    private static class Point {
        char name;
        List<Point> children = new ArrayList<>(); // 子節(jié)點(diǎn)
        List<Integer> weight = new ArrayList<>(); // 邊的權(quán)重

        Point(char n) {
            this.name = n;
        }

        // 插入的時(shí)候注意，權(quán)重最小的放在最前面
        void addChild(Point p, int w) {
            int insertIndex = Collections.binarySearch(weight, w, (a, b) -> a - b); // 二分法查找插入index
            if (insertIndex < 0) insertIndex = -(insertIndex + 1);

            children.add(insertIndex, p);
            weight.add(insertIndex, w);
        }
    }
}

如果我們不定義Point而是定義Edge數(shù)據(jù)結(jié)構(gòu)，則松弛操作的寫法會(huì)更簡(jiǎn)單，請(qǐng)讀者自行實(shí)現(xiàn)。

關(guān)于為什么松弛操作要循環(huán)V-1次，這里簡(jiǎn)單說(shuō)明下：每次松弛都只松弛一層，如果結(jié)果是可求的話，那么路徑長(zhǎng)度最多為V-1，在最壞的情況下，對(duì)于最前面的邊的松弛操作需要V-1次才能傳遞到路徑上的最后一條邊（入下圖所示），所以這里循環(huán)V-1次。

最開始的綠色箭頭表示的松弛操作需要3次才能傳遞到最后一條邊

Bellman-Form算法的時(shí)間復(fù)雜度為O(V*E)，主要是在松弛的時(shí)候需要對(duì)V和E做雙層的循環(huán)。

以上。