一裳凸、定義

在一幅加權(quán)有向圖中，最短路徑是指從頂點s到頂點t的最短路徑是所有從s到t的路徑中的權(quán)重最小者啥么。
求解最短路徑通常需要考慮以下情況：

1. 路徑是有向的登舞；
2. 并不是所有頂點都是可達(dá)的；
3. 可能出現(xiàn)負(fù)權(quán)邊悬荣；
4. 最短路徑可能并不唯一菠秒；
5. 可能出現(xiàn)環(huán)或平行邊；
6. 可能出現(xiàn)負(fù)權(quán)環(huán)氯迂，這種情況下践叠，最短路徑問題沒有意義。

二嚼蚀、單源最短路徑算法

2.1 理論基礎(chǔ)

單源最短路徑：即給定一幅加權(quán)有向圖和一個起點s禁灼，回答“從s到給定目的頂點v是否存在一條有向路徑？如果有轿曙，找出最短的那條路徑弄捕。”
單源最短路徑問題的求解結(jié)果是一棵最短路徑樹（SPT）僻孝。

2-1-1 最短路徑示例

API定義：

2-1-2 最短路徑API定義

數(shù)據(jù)結(jié)構(gòu)定義：
distTo[]：保存各個頂點已知的到源點s的最短路徑，初始時為正無窮大守谓；
edgeTo[]：保存各個頂點在最短路徑上的父路徑穿铆，如edgeTo[v]表示源點s->v的最短路徑上的最后一條路徑。

邊松弛：
定義：假定源點為s斋荞，松弛邊v->w荞雏，意味著檢查s->w的最短路徑是否是先從s->v，再從v->w平酿，即判斷 PATH(s,w) > PATH(s,v) + PATH(v,w)是否成立凤优？

2-1-3 邊松弛的兩種結(jié)果（左邊：松弛失敗蜈彼；右邊：松弛成功）

邊松弛-源碼：

private void relax(DirectedEdge e) {
    int v = e.from(), w = e.to();
    if (distTo[w] > distTo[v] + e.weight()) {
        distTo[w] = distTo[v] + e.weight();
        edgeTo[w] = e;
    }
}

頂點松弛：
定義：頂點松弛就是邊松弛的通用情況筑辨。在邊松弛中，假定源點為s柳刮，松弛邊為v->w挖垛；而在頂點松弛中，松弛邊為頂點v的所有出邊秉颗。

2-1-4 頂點松弛示意圖

頂點松弛-源碼：

private void relax(EdgeWeightedDigraph G, int v) {
    for (DirectedEdge e : G.adj(v)) {
        int w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
        }
    }
}

2.2 最短路徑的最優(yōu)性條件

令G是一幅加權(quán)有向圖痢毒，頂點s是G中的起點，distTo[]表示各個頂點到源點的已知最短路徑蚕甥。
對于從s不可達(dá)的頂點v哪替，distTo[v]的值為無窮大,則，當(dāng)且僅當(dāng)dist[w] ≤ distTo[v] + PATH(v,w)時菇怀，dist[w]為s->w的最短路徑凭舶。

因此，無論一種算法會如何計算distTo[]爱沟，都只需要遍歷圖中的所有邊一遍并檢查最優(yōu)性條件是否滿足帅霜，就能知道數(shù)組中的值是否就是該頂點到源點的最短路徑長度。

2.3 Dijkstra算法

Dijkstra算法是針對單源最短路徑的算法呼伸，僅適合求解不含負(fù)權(quán)邊的加權(quán)有向圖身冀。（用于從指定源點s開始，求解源點s到其余所有頂點的最短路徑）

算法步驟：
該算法每次添加離源點最近的頂點到路徑樹中：

1. 初始時括享，將源點s加入索引優(yōu)先隊列搂根，<key,value>=<頂點，路徑值>
   distTo[i]：保存頂點i到源點s的當(dāng)前已知最短路徑铃辖，初始時為正無窮大剩愧；
   edgeTo[v]：保存各個頂點在最短路徑上的父路徑，如edgeTo[v]表示源點s->v的最短路徑上的最后一條路徑娇斩。
2. 從隊列中取出并刪除一個最小頂點v（相當(dāng)于查找當(dāng)前離源點s最近的頂點）仁卷，對該頂點進(jìn)行松弛操作：
   如果松弛成功穴翩，即找到一個鄰點w滿足：PATH(s,w) > PATH(s,v) + PATH(v,w)，則更新PATH(s,w) = PATH(s,v) + PATH(v,w)锦积，并將w加入索引優(yōu)先隊列藏否。
3. 重復(fù)第2步，直到隊列為空充包，最終distTo[]數(shù)組中的值就是源點到所有頂點的最短路徑。

2-3-1 Dijkstra算法用例軌跡

源碼實現(xiàn)：

public class DijkstraSP {
    // distTo[v]保存頂點v到源點s的最短路徑遥椿，初始時基矮，distTo[s]=0，其它為無窮大
    private double[] distTo;
    // edgeTo[v]保存指向頂點v的最短路徑冠场，即s->v的路徑上的最后一條路徑
    private DirectedEdge[] edgeTo;
    // 索引優(yōu)先隊列家浇，以頂點v為索引，distTo[v]為值碴裙，每次取出最小的進(jìn)行頂點松弛
    private IndexMinPQ<Double> pq;

    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // relax vertices in order of distance from s
        pq = new IndexMinPQ<Double>(G.V());
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty()) {
            int v = pq.delMin();
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }
    }

    //邊松弛
    private void relax(DirectedEdge e) {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w))
                pq.decreaseKey(w, distTo[w]);
            else
                pq.insert(w, distTo[w]);
        }
    }

    /**
     * 源點到頂點v的最短路徑值
     */
    public double distTo(int v) {
        return distTo[v];
    }
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }
    /**
     * 源點到頂點v的最短路徑
     */
    public Iterable<DirectedEdge> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v))
            return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
        int s = Integer.parseInt(args[1]);

        // 計算從源點s開始的最短路徑樹
        DijkstraSP sp = new DijkstraSP(G, s);

        for (int t = 0; t < G.V(); t++) {
            if (sp.hasPathTo(t)) {
                StdOut.printf("%d to %d (%.2f)  ", s, t, sp.distTo(t));
                for (DirectedEdge e : sp.pathTo(t)) {
                    StdOut.print(e + "   ");
                }
                StdOut.println();
            } else {
                StdOut.printf("%d to %d         no path\n", s, t);
            }
        }
    }
}

性能分析：
時間復(fù)雜度：O(ElgV)

2.4 基于拓?fù)渑判虻淖疃搪窂剿惴?/h4>

基于拓?fù)渑判虻淖疃搪窂剿惴ǖ幕静襟E如下：

1. 對于一幅加權(quán)有向無環(huán)圖（DAG）钢悲，進(jìn)行拓?fù)渑判颍玫揭粋€拓?fù)湫蛄校?/li>
2. 按照拓?fù)湫蛄刑蛑辏来螌旤c進(jìn)行松弛莺琳。

算法特點：

1. 能夠在線性時間內(nèi)解決單源最短路徑問題；
2. 能夠處理負(fù)權(quán)邊载慈；
3. 由于是基于拓?fù)渑判虿训龋?strong>必須是無環(huán)圖

2-4-1 基于拓?fù)渑判虻淖疃搪窂剿惴ㄊ纠?/div>

源碼實現(xiàn)：

public class AcyclicSP {
    // distTo[v]保存頂點v到源點s的最短路徑，初始時办铡，distTo[s]=0辞做，其它為無窮大
    private double[] distTo;
    // edgeTo[v]保存指向頂點v的最短路徑，即s->v的路徑上的最后一條路徑
    private DirectedEdge[] edgeTo;

    public AcyclicSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // 對原圖進(jìn)行拓?fù)渑判?        Topological topological = new Topological(G);
        if (!topological.hasCycle())
            throw new IllegalArgumentException("Digraph is not acyclic.");
        // 按照拓?fù)湫蛄泄丫撸来嗡沙陧旤c的每條出邊
        for (int v : topological.order()) {
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }
    }

    // relax edge e
    private void relax(DirectedEdge e) {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
        }
    }
    public double distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        validateVertex(v);
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v))
            return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int s = Integer.parseInt(args[1]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

        // find shortest path from s to each other vertex in DAG
        AcyclicSP sp = new AcyclicSP(G, s);
        for (int v = 0; v < G.V(); v++) {
            if (sp.hasPathTo(v)) {
                StdOut.printf("%d to %d (%.2f)  ", s, v, sp.distTo(v));
                for (DirectedEdge e : sp.pathTo(v)) {
                    StdOut.print(e + "   ");
                }
                StdOut.println();
            } else {
                StdOut.printf("%d to %d         no path\n", s, v);
            }
        }
    }
}

性能分析：
時間復(fù)雜度：O(E+V)

2.5 Bellman-Ford 算法

Bellman-Ford算法的前提條件是：從源點s出發(fā)秤茅，s到任意負(fù)權(quán)環(huán)的頂點都是不可達(dá)的（否則，最短路徑問題沒有意義）童叠。

算法思想：
Bellman-Ford 算法的基本思想是框喳，對于V個頂點的圖，每次對所有邊進(jìn)行松弛拯钻，每松弛1次帖努，就得到從源點出發(fā)路徑長度為k的頂點的最短路徑，最多松弛V-1次就可以得到所有頂點的最短路徑粪般。

為什么最多是需要V-1次松弛拼余？
因為V個頂點形成一棵最短路徑樹，根據(jù)樹定理亩歹，V個頂點的樹只有V-1條邊匙监，所以任意兩個頂點之間的最短路徑長度最多是V-1凡橱。

算法步驟：
在任意含有V個頂點的加權(quán)有向圖中，給定源點s（從s無法到達(dá)任何負(fù)權(quán)重環(huán)）：

1. 初始時亭姥，除了dist[s]=0以外稼钩，其余皆為無窮大；
2. 從源點s出發(fā)达罗，每次都對圖中的所有邊進(jìn)行“松弛”：
   第1輪“松弛”后坝撑，得到從源點出發(fā)，只經(jīng)過1條邊到達(dá)其余各頂點的最短路徑粮揉；
   第2輪“松弛”后巡李，得到從源點出發(fā)，只經(jīng)過2條邊到達(dá)其余各頂點的最短路徑扶认；
   …
   第k輪“松弛”后侨拦，得到從源點出發(fā)，只經(jīng)過k條邊到達(dá)其余各頂點的最短路徑辐宾；
3. 對于一個有V個頂點的圖來說狱从，任意兩個頂點之間的最短路徑最多只有V-1條邊。
   故最多經(jīng)過V-1輪叠纹，即可得到源點到各個頂點的最短路徑季研。

源碼描述如下：

for (int n = 1; n <= G.V()-1; n++)
       for (int v = 0; v < G.V(); v++)
          for (DirectedEdge e : G.adj(v))
              relax(e);

注：負(fù)權(quán)回路的檢測
Bellman-Ford 算法適用的有向圖中，不能出現(xiàn)負(fù)權(quán)回路誉察。
在不含負(fù)權(quán)回路是情況下训貌，經(jīng)過V-1次松弛后，各個頂點的最短路徑不會發(fā)生變化冒窍。

所以為了檢測負(fù)權(quán)回路递沪，可以在V-1次松弛后，再補(bǔ)充1次松弛综液，如果松弛后款慨，某個頂點的最短路徑發(fā)生變化，說明存在負(fù)權(quán)回路谬莹。

2.6 基于隊列的Bellman-Ford算法（SPFA算法）

優(yōu)化思路：
SPFA算法是對Bellman-Ford算法的優(yōu)化檩奠，在Bellman-Ford算法中，每次松弛后附帽，有些頂點已經(jīng)求得了最短路徑埠戳，此后這些頂點的最短路徑會一直保持不變，不再受后續(xù)松弛的影響蕉扮。
所以整胃，可以每次松弛時，僅對上一次松弛時最短路徑發(fā)生了變化的頂點進(jìn)行松弛喳钟，具體步驟如下：

1. 用一個隊列保存所有待松弛的頂點屁使，初始時只有源點s在岂；
2. 每次出隊一個頂點v，對其所有出邊進(jìn)行松弛蛮寂；如果存在某條v->w的邊松弛成功（滿足PATH(s,w) > PATH(s,v) + PATH(v,w)）蔽午，則將w加入隊列（假設(shè)w原來在不隊列中）。
   注意：w必須是不在隊列中酬蹋，否則可能重復(fù)添加相同頂點及老，所以需要用一個boolean數(shù)組標(biāo)識某個頂點是否已經(jīng)在隊列中。
3. 重復(fù)步驟2范抓，直到隊列為空或發(fā)現(xiàn)負(fù)權(quán)環(huán)写半。

如何判斷圖中是否存在負(fù)權(quán)回路？
如果不存在從起點s可達(dá)的負(fù)權(quán)回路尉咕，那么算法終止的條件將是隊列為空；
如果存在呢璃岳？隊列永遠(yuǎn)不會空（又在兜圈子了）年缎！
這意味著程序永不會結(jié)束，為此铃慷，我們必須判斷從s可達(dá)的路徑中是否存在負(fù)權(quán)回路单芜。

兩種判斷方法：
①根據(jù)前面的算法思想我們只知道，Bellman-Ford算法最多需要進(jìn)行V-1次松弛犁柜。所以對于任意一個頂點洲鸠，每進(jìn)入一次隊列，意味著需要進(jìn)行一次松弛馋缅，所以如果某個頂點進(jìn)入隊列的次數(shù)超過V扒腕，說明存在負(fù)權(quán)環(huán)。
②周期性檢測萤悴，每當(dāng)邊的松弛次數(shù)達(dá)到一個指定值瘾腰，就進(jìn)行一次檢測（如下源碼）。

基于隊列的Bellman-Ford算法（SPFA算法）源碼：

public class BellmanFordSP {
    // distTo[v]保存頂點v到源點s的最短路徑覆履，初始時蹋盆，distTo[s]=0，其它為無窮大
    private double[] distTo;
    // edgeTo[v]保存指向頂點v的最短路徑硝全，即s->v的路徑上的最后一條路徑
    private DirectedEdge[] edgeTo;
    // 標(biāo)識頂點v是否已經(jīng)在待松弛隊列中
    private boolean[] onQueue;
    // 待松弛隊列栖雾，保存所有待松弛的頂點
    private Queue<Integer> queue;
    // 記錄邊的松弛總次數(shù)
    private int cost;
    // 保存負(fù)權(quán)環(huán)
    private Iterable<DirectedEdge> cycle;
 
    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        onQueue = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
 
        queue = new Queue<Integer>();
        queue.enqueue(s);
        onQueue[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) {
            int v = queue.dequeue();
            onQueue[v] = false;
            relax(G, v);
        }
    }
 
    // relax vertex v and put other endpoints on queue if changed
    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (!onQueue[w]) {
                    queue.enqueue(w);
                    onQueue[w] = true;
                }
            }
            // 每間隔一段時間，就檢查一次屬否出現(xiàn)負(fù)環(huán)伟众。
            // 這里的間隔定為頂點總數(shù)的倍數(shù)
            if (cost++ % G.V() == 0) {
                findNegativeCycle();
                if (hasNegativeCycle())// found a negative cycle
                    return;
            }
        }
    }
 
    public boolean hasNegativeCycle() {
        return cycle != null;
    }
 
    public Iterable<DirectedEdge> negativeCycle() {
        return cycle;
    }
 
    /**
     * 查找負(fù)權(quán)環(huán) 
                  * 先根據(jù)當(dāng)前已知的最短路徑析藕，生成一幅圖 然后通過DFS判斷是否有總權(quán)值為負(fù)的環(huán)
     */
    private void findNegativeCycle() {
        int V = edgeTo.length;
        EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
        for (int v = 0; v < V; v++)
            if (edgeTo[v] != null)
                spt.addEdge(edgeTo[v]);
 
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
        cycle = finder.cycle();
    }
 
    public double distTo(int v) {
        if (hasNegativeCycle())
            throw new UnsupportedOperationException("Negative cost cycle exists");
        return distTo[v];
    }
 
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }
 
    public Iterable<DirectedEdge> pathTo(int v) {
        if (hasNegativeCycle())
            throw new UnsupportedOperationException("Negative cost cycle exists");
        if (!hasPathTo(v))
            return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }
 
    public static void main(String[] args) {
        In in = new In(args[0]);
        int s = Integer.parseInt(args[1]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
 
        BellmanFordSP sp = new BellmanFordSP(G, s);
 
        // print negative cycle
        if (sp.hasNegativeCycle()) {
            for (DirectedEdge e : sp.negativeCycle())
                StdOut.println(e);
        }
        // print shortest paths
        else {
            for (int v = 0; v < G.V(); v++) {
                if (sp.hasPathTo(v)) {
                    StdOut.printf("%d to %d (%5.2f)  ", s, v, sp.distTo(v));
                    for (DirectedEdge e : sp.pathTo(v)) {
                        StdOut.print(e + "   ");
                    }
                    StdOut.println();
                } else {
                    StdOut.printf("%d to %d           no path\n", s, v);
                }
            }
        }
    }
}

性能分析：

• 時間復(fù)雜度
  平均情況：O(E+V)
  最壞情況：O(EV)

三、多源最短路徑算法

3.1 Floyd-Warshall算法

算法思想：
基于“動態(tài)規(guī)劃”思想凳厢，對于一幅加權(quán)有向圖中的任意兩個頂點I噪径，J：

• 如果兩個頂點之間沒有其它頂點柱恤，則最短路徑就是兩個頂點之間的距離；
• 如果兩個頂點之間只有1個頂點找爱，則當(dāng)PATH(I,J) > PATH(I,k) + PATH(k,J)時梗顺，說明頂點k使得i，j之間距離變短了车摄，則更新PATH(I,J) = PATH(I,k) + PATH(I,J)寺谤；
• 如果兩個頂點之間只有2個頂點，則對這兩個頂點分別判斷PATH(I,J) > PATH(I,k) + PATH(k,J)吮播；
  …
• 如果兩個頂點之間只有k個頂點变屁，則對這k個頂點分別判斷PATH(I,J) > PATH(I,k) + PATH(k,J)；

源碼實現(xiàn)：

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (e[i][j] > e[i][k] + e[k][j])
                e[i][j] = e[i][k] + e[k][j];
        }
    }
}

性能分析：

• 時間復(fù)雜度
  O(V³)

四意狠、各類最短路徑算法比較

\	Dijkstra算法	Bellman-Ford算法	SPFA算法（基于優(yōu)先隊列的Bellman-Ford）	Floyd-Warshall算法	基于拓?fù)渑判虻淖疃搪窂剿惴?/th>
時間復(fù)雜度	O(ElgV)	O(EV)	平均：O(E+V) 最壞：O(EV)	O(V3)	O(E+V)
算法特點	1.稠密圖（鄰接矩陣）; 2.和頂點關(guān)系密切; 3.解決單源最短路徑問題	1.稀疏圖（鄰接表）; 2.和邊關(guān)系密切; 3.解決單源最短路徑問題; 4.查找負(fù)權(quán)環(huán)	1.稀疏圖（鄰接表）; 2.和邊關(guān)系密切; 3.解決單源最短路徑問題; 4.查找負(fù)權(quán)環(huán)	1.稠密圖（鄰接矩陣）; 2.和頂點關(guān)系密切; 3.解決多源最短路徑問題	1.解決單源最短路徑問題
負(fù)權(quán)邊/環(huán)	1.不能解決負(fù)權(quán)邊; 2.可有環(huán)	1.可以解決負(fù)權(quán)邊; 2.可有環(huán)	1.可以解決負(fù)權(quán)邊; 2.可有環(huán)	1.可以解決負(fù)權(quán)邊; 2.可有環(huán)	1.可以解決負(fù)權(quán)邊; 2.不能有環(huán)