從一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)的成本最小的路徑。

我們采用一個(gè)一般性的模型，即加權(quán)有向圖。在加權(quán)有向圖中，每條有向路徑都有一個(gè)與之關(guān)聯(lián)的路徑權(quán)重，它是路徑中的所有邊的權(quán)重之和。這種重要的度量方式使得我們能夠?qū)⑦@個(gè)問(wèn)題歸納為 “找到有個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)的權(quán)重最小的有向路徑”。

單點(diǎn)最短路徑。給定一幅加權(quán)有向圖和一個(gè)起點(diǎn) s ，“從 s 到給定的目的頂點(diǎn) v 是否存在一條有向路徑？如果有，找出最短（總權(quán)重最?。┑哪菞l路徑”。

相關(guān)問(wèn)題：

• 1.加權(quán)有向圖的 API 和實(shí)現(xiàn)以及單點(diǎn)最短路徑的 API；
• 2.解決邊的權(quán)重非負(fù)的最短路徑問(wèn)題的經(jīng)典 Dijkstra 算法；
• 3.在無(wú)環(huán)加權(quán)有向圖中解決該問(wèn)題的一種快速方法，邊的權(quán)重可以是負(fù)數(shù)；
• 4.適用于一般情況的經(jīng)典 Bellman-Ford 算法，其中圖可以含有環(huán)，邊的權(quán)重也可以是負(fù)數(shù)；

還需要算法來(lái)找出負(fù)權(quán)重的環(huán)，以及不含有這種環(huán)的加權(quán)有向圖中的最短路徑。

1.最短路徑的性質(zhì)

• 1.路徑是有向的。最短路徑需要考慮各條邊的方向。
• 2.權(quán)重不一定等價(jià)于距離。
• 3.并不是所有頂點(diǎn)都是可達(dá)的。為了簡(jiǎn)化問(wèn)題，這里的樣圖都是強(qiáng)連通的。
• 4.負(fù)權(quán)重會(huì)使問(wèn)題更復(fù)雜。
• 5.最短路徑一般都是簡(jiǎn)單的。這里的算法會(huì)忽略構(gòu)成環(huán)的零權(quán)重邊，因此找到的最短路徑都不會(huì)含有環(huán)。
• 6.最短路徑不一定是惟一的。從一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)的最短路徑可能有多條，我們只要找到其中一條即可。
• 7.可能存在平行邊和自環(huán)。平行邊中權(quán)重最小的邊才會(huì)被選中，最短路徑也不可能包含自環(huán)，除非自環(huán)的權(quán)重為零，但會(huì)忽略它。

最短路徑

我們的重點(diǎn)是單點(diǎn)最短路徑問(wèn)題，其中給出起點(diǎn) s ，計(jì)算的結(jié)果是一棵最短路徑樹(shù)（SPT），它包含了頂點(diǎn) s 到所有可達(dá)的頂點(diǎn)的最短路徑。

這樣一棵樹(shù)一定存在的：一般來(lái)說(shuō)，從 s 到一個(gè)頂點(diǎn)有可能存在兩條長(zhǎng)度相等的路徑，可以刪除其中一條路徑的最后一條邊。如此這般，直到從起點(diǎn)到每個(gè)頂點(diǎn)都只有一條路徑相連（即一棵樹(shù)）。通過(guò)構(gòu)造這棵最短路徑樹(shù)，可以為用例提供從 s 到圖中任何頂點(diǎn)的最短路徑，表示方法為一組指向父結(jié)點(diǎn)的鏈接。

2.加權(quán)有向圖的數(shù)據(jù)結(jié)構(gòu)

加權(quán)有向圖邊的API

    public class DirectedEdge
    {
        private int v;//邊的起點(diǎn)
        private int w;//邊的終點(diǎn)
        private double weight;//邊的權(quán)重

        public DirectedEdge(int v,int w,double weight)
        {
            this.v = v;
            this.w = w;
            this.weight = weight;
        }

        public double Weight()
        {
            return weight;
        }

        public int From()
        {
            return v;
        }

        public int To()
        {
            return w;
        }
    }

加權(quán)有向圖的API

    public class EdgeWeightedDigraph
    {
        private int v;//頂點(diǎn)總數(shù)
        private int e;//邊的總數(shù)
        private List<DirectedEdge>[] adj;//鄰接表

        public EdgeWeightedDigraph(int v)
        {
            this.v = v;
            this.e = 0;
            adj = new List<DirectedEdge>[v];

            for (int i = 0; i < v; i++)
            {
                adj[i] = new List<DirectedEdge>();
            }
        }

        public int V()
        {
            return v;
        }

        public int E()
        {
            return e;
        }

        public void AddEdge(DirectedEdge _e)
        {
            adj[_e.From()].Add(_e);
            e++;
        }

        public IEnumerable<DirectedEdge> Adj(int v)
        {
            return adj[v];
        }

        public IEnumerable<DirectedEdge> Edges()
        {
            List<DirectedEdge> edges = new List<DirectedEdge>();
            foreach (var _adj in adj)
            {
                edges.AddRange(_adj);
            }

            return edges;
        }
    }

最短路徑的API

最短路徑的數(shù)據(jù)結(jié)構(gòu)

最短路徑樹(shù)中的邊。和深度優(yōu)先搜索，廣度優(yōu)先搜索一樣，使用一個(gè)頂點(diǎn)索引的 DirectedEdge 對(duì)象的父鏈接數(shù)組 edgeTo[ ] ，其中 edgeTo[v] 的值為樹(shù)中連接 v 和它的父結(jié)點(diǎn)的的邊（也是從 s 到 v 的最短路徑上的最后一條邊）。

到達(dá)起點(diǎn)的距離。我們需要一個(gè)由頂點(diǎn)索引的數(shù)組 distTo[ ] ，其中 distTo[v] 為從 s 到 v 的已知最短路徑的長(zhǎng)度。

我們約定，edgeTo[s] 的值為 null，distTo[s] 的值為 0，從起點(diǎn)到不可達(dá)的頂點(diǎn)的距離為Double.MaxValue。

邊的松弛

我們的最短路徑 API 的實(shí)現(xiàn)都基于一個(gè)被稱(chēng)為松弛（relaxation）的簡(jiǎn)單操作。一開(kāi)始我們只知道圖的邊和它們的權(quán)重，distTo[ ] 中只有起點(diǎn)所對(duì)應(yīng)的元素的值為 0 ，其余元素的值均被初始化為Double.MaxValue 。 隨著算法的執(zhí)行，它將起點(diǎn)到其他頂點(diǎn)的最短路徑信息存入 edgeTo[ ] 和 distTo[ ] 數(shù)組。在遇到新的邊時(shí)，通過(guò)更新這些信息就可以得到最短路徑。特別是，我們?cè)谄渲袝?huì)用到邊的松弛技術(shù)，定義為：放松邊 v -> w 意味著檢查從 s 到 w 的最短路徑是否是先從 s 到 v，然后再由 v 到 w 。如果是，則根據(jù)這個(gè)情況更新數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。由 v 到 w 的最短路徑是 distTo[v] 與 e.Weight() 之和 —— 如果這個(gè)值不小于 distTo[w] ，則這條邊失效并忽略。

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;
    }
}

下圖是邊的放松操作之后可能出現(xiàn)兩種情況。一種情況是邊失效（左邊），不更新任何數(shù)據(jù)；另一種情況是 v -> w 就是到達(dá) w 的最短路徑（右邊），這將會(huì)更新 edgeTo[w] 和 distTo[w] （這可能會(huì)使另一些邊失效，但也可能產(chǎn)生一些新的有效邊）。

頂點(diǎn)的松弛

實(shí)際上，實(shí)現(xiàn)會(huì)放松從一個(gè)給定頂點(diǎn)指出的所有邊。從任意 distTo[v] 為有限值的頂點(diǎn) v 指向任意 distTo[ ] 為無(wú)窮的頂點(diǎn)的邊都是有效的。如果 v 被放松，那么這些有效邊都會(huì)被添加到 edgeTo[ ] 中。某條從起點(diǎn)指出的邊將會(huì)是第一條被加入 edgeTo[ ] 中的邊。算法會(huì)謹(jǐn)慎選擇頂點(diǎn)，使得每次頂點(diǎn)松弛操作都能得出到達(dá)某個(gè)頂點(diǎn)的更短路徑，最后逐漸找出到達(dá)每個(gè)頂點(diǎn)的最短路徑。

private void Relax(EdgeWeightDigraph G,int v)
{
     foreach(DirectedEdge e in G.Adj(v))
     {
          int w = e.To();
          if(distTo[w] > distTo[v] + e.Weight())
          {
               distTo[w] = distTo[v] + e.Weight();
               edgeTo[w] = e;
          }
     }  
}

3.最短路徑算法的理論基礎(chǔ)

邊的放松一項(xiàng)非常容易實(shí)現(xiàn)的重要操作，它是實(shí)現(xiàn)最短路徑算法的基礎(chǔ)。同時(shí)，它也是理解這個(gè)算法的理論基礎(chǔ)并使我們能夠完整地證明算法的正確性。

最優(yōu)性條件

最短路徑的最優(yōu)性條件：令 G 為一幅加權(quán)有向圖，頂點(diǎn) s 是 G 中的起點(diǎn)，distTo[ ] 是一個(gè)由頂點(diǎn)索引的數(shù)組，保存的是 G 中路徑的長(zhǎng)度。對(duì)于從 s 可達(dá)的所有頂點(diǎn) v ，distTo[v] 的值是從 s 到 v 的某條路徑的長(zhǎng)度，對(duì)于從 s 不可達(dá)的所有頂點(diǎn) v ,該值為無(wú)窮大。當(dāng)且僅當(dāng)對(duì)于從 v 到 w 的任意一條邊 e ，這些值都滿(mǎn)足 distTo[w] <= distTo[v] + e.Weight() 時(shí)（換句話(huà)說(shuō)，不存在有效邊時(shí)），它們是最短路徑的長(zhǎng)度。

驗(yàn)證

上面最優(yōu)性條件的一個(gè)重要的實(shí)際應(yīng)用是最短路徑的驗(yàn)證。無(wú)論一種算法會(huì)如何計(jì)算 distTo[ ] ，都只需要遍歷圖中的所有邊一邊并檢查最優(yōu)性條件是否滿(mǎn)足就能夠知道該數(shù)組中的值是否是最短路徑的長(zhǎng)度。最短路徑的算法可能會(huì)很復(fù)雜，因此能夠快速驗(yàn)證計(jì)算的結(jié)果就很重要。后面會(huì)有 Check（） 方法。

通用算法

通用最短路徑算法：將 distTo[s] 初始化為 0 ，其他 distTo[ ] 元素初始化為無(wú)窮達(dá)，繼續(xù)如下操作：

放松 G 中的任意邊，直到不存在有效邊為止。

對(duì)于任意從 s 可達(dá)的頂點(diǎn) w ，在進(jìn)行這些操作之后，distTo[w] 的值即為從 s 到 w 的最短路徑的長(zhǎng)度且 edgeTo[w] 的值即為該路徑上的最后一條邊。

證明：放松邊 v -> w 必然會(huì)將 distTo[w] 的值設(shè)為從 s 到 w 的某條路徑的長(zhǎng)度且將 edgeTo[w] 設(shè)為該路徑上的最后一條邊。對(duì)于從 s 可達(dá)的任意頂點(diǎn) w，只要 distTo[w] 仍然是無(wú)窮達(dá)，到達(dá) w 的最短路徑上的某條邊肯定仍然是有效的，因此算法的操作會(huì)不斷繼續(xù)，直到由 s 可達(dá)的每個(gè)頂點(diǎn)的 distTo[ ] 值均變?yōu)榈竭_(dá)頂點(diǎn)的某條路徑的長(zhǎng)度。對(duì)于已經(jīng)找到最短路徑的任意頂點(diǎn) v ，在算法的計(jì)算過(guò)程中 distTo[v] 的值都是從 s 到 v 的某條路徑的長(zhǎng)度且必然是單調(diào)遞減的。因此，它遞減的次數(shù)必然是有限的（每切換一條 s 到 v 簡(jiǎn)單路徑就遞減一次）。當(dāng)不存在有效邊的時(shí)候，最優(yōu)性條件就成立了。

將最優(yōu)性條件和通用算法放在一起討論的關(guān)鍵原因是，通用算法并沒(méi)有指定邊的放松順序。因此，要證明這些算法都能通過(guò)計(jì)算得到最短路徑，只需要證明它們都會(huì)放松所有的邊直到所有邊都失效即可。

4.Dijkstra 算法

在最小生成樹(shù)中，分享了尋找加權(quán)無(wú)向圖中的最小生成樹(shù)的 Prim 算法：構(gòu)造最小生成樹(shù)的每一步都向這棵樹(shù)中添加一條新的邊。Dijkstra 算法采用了類(lèi)似的方法來(lái)計(jì)算最短路徑樹(shù)。首先將 distTo[s] 初始化為 0，distTo[ ] 中的其他元素初始化為正無(wú)窮大。然后將distTo[ ]最小的非樹(shù)頂點(diǎn)放松并加入樹(shù)中，如此這般，直到所有的頂點(diǎn)都在樹(shù)中或者所有的非樹(shù)頂點(diǎn)的distTo[ ] 值均為無(wú)窮大。

Dijkstra 算法能夠解決邊權(quán)重非負(fù)的加權(quán)有向圖的單起點(diǎn)最短路徑問(wèn)題。證明：如果 v 是從起點(diǎn)可達(dá)的，那么所有 v -> w 的邊都只會(huì)被放松一次。當(dāng) v 被放松時(shí)，必有distTo[w] <=distTo[v] + e.Weight() 。該不等式在算法結(jié)束前都會(huì)成立，因此 distTo[v] 則不會(huì)改變（因?yàn)檫叺臋?quán)重非負(fù)且在每一步中算法都會(huì)選擇 distTo[ ] 最小的頂點(diǎn)，之后的放松操作不可能使任何 distTo[ ] 的值小于 distTo[v]）。因此，在所有從 s 可達(dá)的頂點(diǎn)均被添加到樹(shù)中之后，最短路徑的最優(yōu)性條件成立。

數(shù)據(jù)結(jié)構(gòu)

要實(shí)現(xiàn)Dijkstra 算法，除了 distTo[ ] 和 edgeTo[ ] 數(shù)組之外還需要一條索引優(yōu)先隊(duì)列 pq ，以保存需要被放松的頂點(diǎn)。 IndexMinPQ 可以將索引和鍵（優(yōu)先級(jí)）關(guān)聯(lián)起來(lái)并且可以刪除并返回優(yōu)先級(jí)最低的索引。在這里，只要將頂點(diǎn) v 和 distTo[v] 關(guān)聯(lián)起來(lái)就立即可以得到Dijkstra 算法的實(shí)現(xiàn)。edgeTo[ ] 中的元素所對(duì)應(yīng)的可達(dá)頂點(diǎn)構(gòu)成了一棵最短路徑樹(shù)。

如下圖，根據(jù)算法的證明，已知樹(shù)節(jié)點(diǎn)所對(duì)應(yīng)的 distTo[ ] 值均為最短路徑的長(zhǎng)度。對(duì)于優(yōu)先隊(duì)列中的任意頂點(diǎn) w ，distTo[w] 是從 s 到 w 的最短路徑的長(zhǎng)度，該路徑上的中間頂點(diǎn)在樹(shù)中且路徑結(jié)束于橫切邊 edgeTo[w] 。優(yōu)先級(jí)最小的頂點(diǎn)的 distTo[ ] 值就是最短路徑的權(quán)重，它不會(huì)小于已經(jīng)放松過(guò)的任意頂點(diǎn)的最短路徑的權(quán)重，也不會(huì)大于還未被放松過(guò)的任意頂點(diǎn)的最短路徑的權(quán)重。這個(gè)頂點(diǎn)就是下一個(gè)要被放松的頂點(diǎn)。所有從 s 可達(dá)的頂點(diǎn)都會(huì)按照最短路徑的權(quán)重順序被放松。

實(shí)現(xiàn)

    public class DijkstraSP
    {
        private DirectedEdge[] edgeTo;
        private double[] distTo;
        private IndexMinPQ<Double> pq;

        public DijkstraSP(EdgeWeightedDigraph G,int s)
        {
            edgeTo = new DirectedEdge[G.V()];
            distTo = new double[G.V()];
            pq = new IndexMinPQ<double>(G.V());

            for (int v = 0; v < G.V(); v++)
            {
                distTo[v] = Double.MaxValue;
            }

            distTo[0] = 0.0;
            pq.Insert(s,0.0);
            while (!pq.IsEmpty())
            {
                Relax(G,pq.DelMIn());
            }
        }

        private void Relax(EdgeWeightedDigraph G, int v)
        {
            foreach (var e in G.Adj(v))
            {
                int w = e.To();
                if (distTo[w] > distTo[v] + e.Weight())
                {
                    distTo[w] = distTo[v] + e.Weight();
                    edgeTo[w] = e;

                    if (pq.Contains(w))
                    {
                        pq.Change(w, distTo[w]);
                    }
                    else
                    {
                        pq.Insert(w,distTo[w]);
                    }

                }
            }
        }
    }

軌跡

• 1.將頂點(diǎn) 0 添加到樹(shù)中，將頂點(diǎn) 2 和 4 加入優(yōu)先隊(duì)列；
• 2.從優(yōu)先隊(duì)列中刪除頂點(diǎn) 2，將 0 -> 2 添加到樹(shù)中，將頂點(diǎn) 7 加入優(yōu)先隊(duì)列；
• 3.從優(yōu)先隊(duì)列中刪除頂點(diǎn) 4，將 0 -> 4 添加到樹(shù)中，將頂點(diǎn) 5 加入優(yōu)先隊(duì)列，邊 4 -> 7 失效；
• 4.從優(yōu)先隊(duì)列中刪除頂點(diǎn) 7，將2 -> 7添加到樹(shù)中，將頂點(diǎn) 3 加入到優(yōu)先隊(duì)列，邊 7 -> 5 失效；
• 5.從優(yōu)先隊(duì)列中刪除頂點(diǎn) 5，將 4 -> 5添加到樹(shù)中，將頂點(diǎn) 1 加入優(yōu)先隊(duì)列，邊 5 -> 7 失效；
• 6.從優(yōu)先隊(duì)列中刪除頂點(diǎn) 1，將 5 -> 1添加到樹(shù)中，邊 1 -> 3 失效；
• 7.從優(yōu)先隊(duì)列中刪除頂點(diǎn) 6，將 3 -> 6 添加到樹(shù)中。

算法按照頂點(diǎn)到起點(diǎn)的最短路徑的長(zhǎng)度的增序?qū)⑺鼈兲砑拥阶疃搪窂綐?shù)中。

在一幅含有 V 個(gè)頂點(diǎn)和 E 條邊的加權(quán)有向圖中，使用 Dijkstra 算法計(jì)算結(jié)點(diǎn)為給定起點(diǎn)的最短路徑樹(shù)所需的空間與 V 成正比，時(shí)間與 ElogV 成正比（最壞情況下）。

變種

只需對(duì)Dijkstra 算法的實(shí)現(xiàn)稍作修改就能解決這個(gè)問(wèn)題的其他版本。例如，加權(quán)無(wú)向圖中的單點(diǎn)最短路徑。

如果將無(wú)向圖看做有向圖，創(chuàng)建一幅由相同頂點(diǎn)構(gòu)成的加權(quán)有向圖，且對(duì)于無(wú)向圖中的每條邊，相應(yīng)地創(chuàng)建兩條方向不同的有向邊。有向圖中的路徑和無(wú)向圖中的路徑存在一一對(duì)應(yīng)的關(guān)系，路徑的權(quán)重也是相同的——最短路徑的問(wèn)題是等價(jià)的。

給定兩點(diǎn)的最短路徑。

給定一幅加權(quán)有向圖以及一個(gè)起點(diǎn) s 和一個(gè)終點(diǎn) t，找到從 s 到 t 的最短路徑。

要解決這個(gè)問(wèn)題，可以使用Dijkstra 算法并在從優(yōu)先隊(duì)列中取到 t 之后終止搜索。

任意頂點(diǎn)對(duì)之間的最短路徑

下面的代碼解決了任意頂點(diǎn)對(duì)之間的最短路徑問(wèn)題，所需的時(shí)間和空間都與 EVlogV 成正比。它構(gòu)造了DijkstraSP 對(duì)象的數(shù)組，每個(gè)元素都將相應(yīng)的頂點(diǎn)作為起點(diǎn)。在用例進(jìn)行查詢(xún)時(shí)，代碼會(huì)訪(fǎng)問(wèn)起點(diǎn)所對(duì)應(yīng)的單點(diǎn)最短路徑對(duì)象并將目的頂點(diǎn)作為參數(shù)進(jìn)行查詢(xún)。

    public class DijkstraAllPairsSP
    {
        private DijkstraSP[] all;

        public DijkstraAllPairsSP(EdgeWeightedDigraph G)
        {
            all = new DijkstraSP[G.V()];
            for (int v = 0; v < G.V(); v++)
            {
                all[v] = new DijkstraSP(G,v);
            }
        }

        public IEnumerable<DirectedEdge> Path(int s, int t)
        {
            return all[s].Path(t);
        }

        public double Dist(int s, int t)
        {
            return all[s].Dist(t);
        }
    }

歐幾里得圖中的最短路徑

在頂點(diǎn)為平面上的點(diǎn)且邊的權(quán)重于頂點(diǎn)歐幾里得間距成正比的圖中，解決單點(diǎn)，給定兩點(diǎn)和任意頂點(diǎn)對(duì)之間的最短路徑。

下圖是Dijkstra 算法在處理歐幾里得圖時(shí)用若干不同的起點(diǎn)產(chǎn)生最短路徑樹(shù)的過(guò)程。

下面，將會(huì)考慮加權(quán)無(wú)環(huán)圖中的最短路徑算法并且將在線(xiàn)性時(shí)間內(nèi)解決該問(wèn)題。然后是負(fù)權(quán)重的加權(quán)有向圖中的最短路徑問(wèn)題，Dijkstra 算法并不適用于這種情況。

5.無(wú)環(huán)加權(quán)有向圖中的最短路徑算法

許多應(yīng)用中的加權(quán)有向圖都是不含有有向環(huán)的?，F(xiàn)在來(lái)看一種比Dijkstra 算法更快，更簡(jiǎn)單的在無(wú)環(huán)加權(quán)有向圖中找出最短路徑的算法，它的特點(diǎn)是：

• 1.能夠在線(xiàn)性時(shí)間內(nèi)解決單點(diǎn)最短路徑的問(wèn)題；
• 2.能夠處理負(fù)權(quán)重的邊；
• 3.能夠解決相關(guān)的問(wèn)題，例如找出最長(zhǎng)的路徑。

這種算法是在有向圖中學(xué)過(guò)的無(wú)環(huán)有向圖的拓?fù)渑判蛩惴ǖ暮?jiǎn)單擴(kuò)展。

特別的是，只要將頂點(diǎn)的放松和拓?fù)渑判蚪Y(jié)婚起來(lái)，馬上就能夠得到一種解決無(wú)環(huán)加權(quán)有向圖中的最短路徑問(wèn)題 的算法。首先，將 distTo[s] 初始化為 0 ，其他 distTo[ ] 元素初始化為無(wú)窮大，然后一個(gè)一個(gè)地按照拓?fù)漤樞蚍潘伤许旤c(diǎn)。

命題 S ：按照拓?fù)漤樞蚍潘身旤c(diǎn)，就能在和 E+V 成正比的時(shí)間內(nèi)解決無(wú)環(huán)加權(quán)有向圖的單點(diǎn)最短路徑問(wèn)題。每條邊 v --> w 都只會(huì)被放松一次。當(dāng) v 被放松時(shí)，得到：distTo[w] <= distTo[v] + e.Weight() 。在算法結(jié)束前該不等式都成立，因?yàn)閐istTo[v] 是不會(huì)變化的（因?yàn)槭前凑胀負(fù)漤樞蚍潘身旤c(diǎn)，在 v 被放松之后算法不會(huì)再處理任何指向 v 的邊）而distTo[w] 只會(huì)變小（任何放松操作都只會(huì)減小 distTo[ ] 中元素的值）。因此，在所有從 s 可達(dá)的頂點(diǎn)都被加入到樹(shù)中后，最短路徑的最優(yōu)性條件成立。

namespace ShortestPaths
{
    /// <summary>
    /// 基于拓?fù)涞臒o(wú)環(huán)加權(quán)有向圖的最短路徑算法
    /// </summary>
    public class AcyclicSP
    {
        private DirectedEdge[] edgeTo;
        private double[] distTo;

        public AcyclicSP(EdgeWeightedDigraph G, int s)
        {
            edgeTo = new DirectedEdge[G.V()];
            distTo = new double[G.V()];

            for (var i = 0; i < G.V(); i++)
            {
                distTo[i] = Double.MaxValue;
            }
            distTo[0] = 0;

            Topological top = new Topological(G);
            foreach (var v in top.Order())
            {
                Relax(G,v);
            }
        }

        private void Relax(EdgeWeightedDigraph G, int v)
        {
            foreach (DirectedEdge e in G.Adj(v))
            {
                int w = e.To();
                if (distTo[w] > distTo[v] + e.Weight())
                {
                    distTo[w] = distTo[v] + e.Weight();
                    edgeTo[w] = e;
                }
            }
        }
    }
}

示例軌跡：

• 1.用深度優(yōu)先搜索得到圖的頂點(diǎn)的拓?fù)渑判?5 1 3 6 4 7 0 2；
• 2.將頂點(diǎn) 5 和從它指出的所有邊添加到樹(shù)中；
• 3.將頂點(diǎn) 1 和邊 1->3 添加到樹(shù)中；
• 4.將頂點(diǎn) 3 和邊 3->6 添加到樹(shù)中，邊 3->7 失效；
• 5.將頂點(diǎn) 6 和邊 6->2, 6->0 添加到樹(shù)中，邊 6->4 失效；
• 6.將頂點(diǎn) 4 和邊 4->0 添加到樹(shù)中，邊 4->7 和 6->0 失效；
• 7.將頂點(diǎn) 7 和邊 7->2 添加到樹(shù)中，邊 6->2 失效；
• 8.將頂點(diǎn) 0 添加到樹(shù)中，邊 0->2 失效；
• 9.將頂點(diǎn) 2 添加到樹(shù)中。

命題 S 很重要，因?yàn)樗?“無(wú)環(huán)” 能夠極大地簡(jiǎn)化問(wèn)題的論斷。對(duì)于最短路徑問(wèn)題，基于拓?fù)渑判虻姆椒ū?Diijkstra 算法快的倍數(shù)與Diijkstra 算法中所有優(yōu)先隊(duì)列操作的總成本成正比。另外，命題 S 的證明和邊的權(quán)重是否非負(fù)無(wú)關(guān)，因此無(wú)環(huán)加權(quán)有向圖不會(huì)受任何限制。用這個(gè)特點(diǎn)可以解決邊的負(fù)權(quán)重問(wèn)題。

最長(zhǎng)路徑

考慮在無(wú)環(huán)加權(quán)有向圖中尋找最長(zhǎng)路徑的問(wèn)題，邊的權(quán)重可正可負(fù)。

實(shí)現(xiàn)：復(fù)制原始無(wú)環(huán)加權(quán)有向圖得到一個(gè)副本并將副本中的所有邊的權(quán)重變?yōu)樨?fù)值。這樣，副本中的最短路徑即為原圖中的最長(zhǎng)路徑。要將最短路徑問(wèn)題的答案轉(zhuǎn)換為最長(zhǎng)路徑問(wèn)題的答案，只需將方案中的權(quán)重變?yōu)檎导纯伞Ｋ钑r(shí)間與 E+V 成正比。

軌跡：

在一般的加權(quán)有向圖（邊的權(quán)重可能為負(fù)）中尋找最長(zhǎng)簡(jiǎn)單路徑的已知最好算法在最壞情況下所需的時(shí)間是指數(shù)級(jí)別。出現(xiàn)環(huán)的可能性似乎使這個(gè)問(wèn)題的難度以指數(shù)級(jí)別增長(zhǎng)。

并行調(diào)度任務(wù)

這里再次考慮有向圖中出現(xiàn)過(guò)的任務(wù)調(diào)度問(wèn)題，這次解決一下調(diào)度問(wèn)題：

優(yōu)先級(jí)限制下的并行任務(wù)調(diào)度。給定一組需要完成的任務(wù)和每個(gè)任務(wù)所需的時(shí)間，以及一組關(guān)于任務(wù)完成的先后次序的優(yōu)先級(jí)限制。在滿(mǎn)足限制條件的前提下應(yīng)該如何在若干相同的處理器（數(shù)量不限）安排任務(wù)并在最短時(shí)間內(nèi)完成所有任務(wù)？

有向圖中調(diào)度的模型默認(rèn)只有單個(gè)處理器：將任務(wù)按照拓?fù)漤樞蚺判?，完成任?wù)的總耗時(shí)就是所有任務(wù)所需要的總時(shí)間。現(xiàn)在假設(shè)有足夠多的處理器并能夠同時(shí)處理任意多的任務(wù)，受到的只有優(yōu)先級(jí)的限制。

存在一種線(xiàn)性時(shí)間的算法 —— 一種叫做“關(guān)鍵路徑”的方法能夠證明這個(gè)問(wèn)題與無(wú)環(huán)加權(quán)有向圖中的最長(zhǎng)路徑問(wèn)題是等價(jià)的。

假設(shè)任意可用的處理器都能在任務(wù)所需的時(shí)間內(nèi)完成它，那么我們的重點(diǎn)就是盡早安排每一個(gè)任務(wù)。例如，下面表給出了一個(gè)任務(wù)調(diào)度問(wèn)題。下圖給出了解決方案，顯示了這個(gè)問(wèn)題所需的最短時(shí)間 173.0 。

這份調(diào)度方案滿(mǎn)足了所有限制條件，沒(méi)有其他調(diào)度方案比這耗時(shí)更少，因?yàn)槿蝿?wù)必須按照 0 -> 9 -> 6 -> 8 -> 2 的順序完成。這個(gè)順序就是這個(gè)問(wèn)題的關(guān)鍵路徑。由優(yōu)先級(jí)限制指定的每一列任務(wù)都代表了調(diào)度方案的一種可能的時(shí)間下限。如果將一系列任務(wù)的長(zhǎng)度定義為完成所有任務(wù)的最早可能時(shí)間，那么最長(zhǎng)的任務(wù)序列就是問(wèn)題的關(guān)鍵路徑，因?yàn)樵谶@份任務(wù)序列中任何任務(wù)的啟動(dòng)延遲都會(huì)影響到整個(gè)項(xiàng)目的完成時(shí)間。

解決：

解決并行任務(wù)調(diào)度問(wèn)題的關(guān)鍵路徑方法的步驟如下：創(chuàng)建一幅無(wú)環(huán)加權(quán)有向圖，其中包含一個(gè)起點(diǎn) s 和一個(gè)終點(diǎn) t 且每個(gè)人物都對(duì)應(yīng)著兩個(gè)頂點(diǎn)（一個(gè)起始頂點(diǎn)和一個(gè)結(jié)束頂點(diǎn)。對(duì)于每個(gè)任務(wù)都有一條從它的起始頂點(diǎn)指向結(jié)束頂點(diǎn)的邊，邊的權(quán)重為任務(wù)所需要的時(shí)間。對(duì)于每條優(yōu)先級(jí)限制 v -> w ，添加一條從 v 的結(jié)束頂點(diǎn)指向 w 的起始頂點(diǎn)的權(quán)重為零的邊。我們還需要為每個(gè)任務(wù)添加一條從起點(diǎn)指向該任務(wù)的起始頂點(diǎn)的權(quán)重為零的邊以及一條從該任務(wù)的結(jié)束頂點(diǎn)到終點(diǎn)的權(quán)重為零的邊。這樣，每個(gè)任務(wù)預(yù)計(jì)的開(kāi)始時(shí)間即為從起點(diǎn)到它的起始頂點(diǎn)的最長(zhǎng)距離。

接下來(lái)就是在無(wú)環(huán)加權(quán)有向圖中尋找一個(gè)最長(zhǎng)路徑——關(guān)鍵路徑。

        static void Main(string[] args)
        {
            string[] strs = File.ReadAllLines(@"jobs.txt");
            var N = Int32.Parse(strs[0]);//任務(wù)數(shù)
            EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*N+2);//2*N+2 為節(jié)點(diǎn)數(shù)，每個(gè)任務(wù)兩個(gè)我節(jié)點(diǎn)，再加上起始兩個(gè)節(jié)點(diǎn)
            int s = 2 * N, t = 2 * N + 1;//起點(diǎn)和終點(diǎn)
            for (var i = 0; i < N; i++)
            {
                string[] a = strs[i].Split(" ");
                double duration = Double.Parse(a[0]);
                G.AddEdge(new DirectedEdge(i,i+N,duration));//任務(wù)起點(diǎn)指向任務(wù)終點(diǎn)
                G.AddEdge(new DirectedEdge(s,i,0));
                G.AddEdge(new DirectedEdge(i+N,t,0));

                for (var j = 1; j < a.Length; j++)
                {
                    int successor = Int32.Parse(a[j]);
                    G.AddEdge(new DirectedEdge(i+N,successor,0));
                }
            }

            AcyclicSP lp = new AcyclicSP(G,s);
            for (var i = 0; i < N; i++)
                Console.WriteLine($"{i} 開(kāi)始時(shí)間:"+lp.DistTo(i));
            Console.WriteLine("t distTo:" + lp.DistTo(t));

        }

這里實(shí)現(xiàn)的任務(wù)調(diào)度問(wèn)題的關(guān)鍵路徑方法將問(wèn)題歸約為尋找無(wú)環(huán)加權(quán)有向圖的最長(zhǎng)路徑問(wèn)題。它會(huì)根據(jù)任務(wù)調(diào)度問(wèn)題的描述用關(guān)鍵路徑的方法構(gòu)造一幅加權(quán)有向圖，然后使用 AcylicLP 找到圖中的最長(zhǎng)路徑，最后打印出各條最長(zhǎng)路徑的長(zhǎng)度，也就是正好是每個(gè)任務(wù)的開(kāi)始時(shí)間。

解決優(yōu)先級(jí)限制下的并行任務(wù)調(diào)度問(wèn)題的關(guān)鍵路徑法所需的時(shí)間為線(xiàn)性級(jí)別。為什么 CPM 類(lèi)能解決問(wèn)題？算法的正確性依賴(lài)于兩個(gè)因素。首先，在相應(yīng)的有向無(wú)環(huán)圖中，每條路徑都是由任務(wù)的起始頂點(diǎn)和結(jié)束頂點(diǎn)組成的并由權(quán)重為零的優(yōu)先級(jí)限制條件的邊分隔 —— 從起點(diǎn) s 到任意頂點(diǎn) v 的任意路徑的長(zhǎng)度都是任務(wù) v 的開(kāi)始 / 結(jié)束時(shí)間的下限，因?yàn)檫@已經(jīng)是在同一臺(tái)處理器上順序完成這些任務(wù)的最優(yōu)的排列順序了。因此，從起點(diǎn) s 到終點(diǎn) t 的最長(zhǎng)路徑就是所有任務(wù)的完成時(shí)間的下限。第二，由最長(zhǎng)路徑得到的所有開(kāi)始和結(jié)束時(shí)間都是可行的 —— 每個(gè)任務(wù)都只能在優(yōu)先級(jí)限制指定的先導(dǎo)任務(wù)完成之后開(kāi)始，因?yàn)樗拈_(kāi)始時(shí)間就是頂點(diǎn)到它的起始頂點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。因此，從起點(diǎn) s 到 終點(diǎn) t 的最長(zhǎng)路徑長(zhǎng)度就是所有任務(wù)完成時(shí)間的上限。

相對(duì)最后期限限制下的并行任務(wù)調(diào)度

一般的最后期限（deadline）都是相對(duì)于第一個(gè)任務(wù)的開(kāi)始時(shí)間而言的。假設(shè)在任務(wù)調(diào)度問(wèn)題中加入一種新類(lèi)型的限制，需要某個(gè)任務(wù)必須在指定的時(shí)間點(diǎn)之前開(kāi)始，即指定和另一個(gè)任務(wù)的開(kāi)始時(shí)間的相對(duì)時(shí)間。這種類(lèi)型的限制條件在爭(zhēng)分奪秒的生產(chǎn)線(xiàn)上以及許多其他應(yīng)用中都很常見(jiàn)，但它也會(huì)使得任務(wù)調(diào)度問(wèn)題更難解決。如下表，假設(shè)要在前面的示例中加入一個(gè)限制條件，使 2 號(hào)任務(wù)必須在 4 號(hào)任務(wù)啟動(dòng)后的 12 個(gè)時(shí)間單位之內(nèi)開(kāi)始。實(shí)際上，在這里最后期限限制的是 4 號(hào)任務(wù)的開(kāi)始時(shí)間：它的開(kāi)始時(shí)間不能早于 2 號(hào)任務(wù)開(kāi)始 12 個(gè)時(shí)間單位。在示例中，調(diào)度表中有足夠的空檔來(lái)滿(mǎn)足這個(gè)最后期限限制：我們可以令 4 號(hào)任務(wù)開(kāi)始于 111 時(shí)間，即 2 號(hào)任務(wù)計(jì)劃開(kāi)始時(shí)間前的 12 個(gè)時(shí)間單位處。需要注意的是，如果 4 號(hào)任務(wù)耗時(shí)很長(zhǎng)，這個(gè)修改可能會(huì)延長(zhǎng)整個(gè)調(diào)度計(jì)劃的完成時(shí)間。同理，如果再添加一個(gè)最后期限的限制條件，令 2 號(hào)任務(wù)必須在 7 號(hào)任務(wù)啟動(dòng)后的 70 個(gè)時(shí)間單位內(nèi)開(kāi)始，還可以將 7 號(hào)任務(wù)的開(kāi)始時(shí)間調(diào)整到 53，這樣就不用修改 3 號(hào)任務(wù)和 8 號(hào)任務(wù)的計(jì)劃開(kāi)始時(shí)間。但是如果繼續(xù)限制 4 號(hào)任務(wù)必須在 0 號(hào)任務(wù)啟動(dòng)后的 80 個(gè)時(shí)間單位內(nèi)開(kāi)始，那么就不存在可行的調(diào)度計(jì)劃了：限制條件 4 號(hào)任務(wù)必須在 0 號(hào)任務(wù)啟動(dòng)后的 80 個(gè)時(shí)間單位內(nèi)開(kāi)始以及 2 號(hào)任務(wù)必須在 4 號(hào)任務(wù)啟動(dòng)后的 12 個(gè)時(shí)間單位之內(nèi)開(kāi)始，意味著 2 號(hào)任務(wù)必須在 0 號(hào)任務(wù)啟動(dòng)后的 93 個(gè)時(shí)間單位之內(nèi)開(kāi)始，但因?yàn)榇嬖谌蝿?wù)鏈 0（41 個(gè)時(shí)間單位）-> 9（29 個(gè)時(shí)間單位）-> 6（21 個(gè)時(shí)間單位）-> 8（32 個(gè)時(shí)間單位）-> 2，2 號(hào)任務(wù)最早也只能在 0 號(hào)任務(wù)啟動(dòng)后的 123 個(gè)時(shí)間單位之內(nèi)開(kāi)始。

向任務(wù)調(diào)度問(wèn)題中添加的最后期限限制

相對(duì)最后期限限制下的并行任務(wù)調(diào)度問(wèn)題是一個(gè)加權(quán)有向圖中的最短路徑問(wèn)題（可能存在環(huán)和負(fù)權(quán)重邊）。根據(jù)任務(wù)調(diào)度的描述構(gòu)造加權(quán)有向圖，為每條最后期限限制添加一條邊：如果任務(wù) v 必須在任務(wù) w 啟動(dòng)后的 d 個(gè)單位時(shí)間內(nèi)開(kāi)始，則添加條從 v 指向 w 的負(fù)權(quán)重為 d 的邊。將所有邊的權(quán)重取反即可將該問(wèn)題轉(zhuǎn)化為一個(gè)最短路徑問(wèn)題。如果存在可行的調(diào)度方案，證明也就完成了。判斷一個(gè)調(diào)度方案是否可行也是計(jì)算的一部分。

上面的示例說(shuō)明了負(fù)權(quán)重的邊在實(shí)際應(yīng)用的模型中也能起到重要作用。它說(shuō)明，如果能夠有效解決負(fù)權(quán)重邊的最短路徑問(wèn)題，那就能夠找到相對(duì)最后期限限制下的并行任務(wù)調(diào)度問(wèn)題的解決方案。之前學(xué)過(guò)的算法都無(wú)法完成這個(gè)任務(wù)：Dijkstra 算法只適用于正權(quán)重的邊，AcylicSP 算法要求有向圖是無(wú)環(huán)的。下面解決含有負(fù)權(quán)重且不一定是無(wú)環(huán)的有向圖中的最短路徑問(wèn)題。

6.一般加權(quán)有向圖中的最短路徑問(wèn)題

上面討論的最后期限限制下的任務(wù)調(diào)度問(wèn)題告訴我們負(fù)權(quán)重的邊不僅僅是一個(gè)數(shù)學(xué)問(wèn)題。相反，它能夠極大地?cái)U(kuò)展解決最短路徑問(wèn)題模型的應(yīng)用范圍。接下來(lái)，考慮既可能含有環(huán)也可能含有負(fù)權(quán)重的邊的加權(quán)有向圖中的最短路徑算法。

開(kāi)始之前，先學(xué)習(xí)一下這種有向圖的基本性質(zhì)以及更新我們對(duì)最短路徑的認(rèn)識(shí)。下圖展示的是負(fù)權(quán)重的邊對(duì)有向圖中的最短路徑的影響。也許最明顯的改變就是當(dāng)存在負(fù)權(quán)重的邊時(shí)，權(quán)重較小的路徑含有的邊可能會(huì)比權(quán)重較大的路徑更多。在只存在正權(quán)重的邊時(shí)，我們的重點(diǎn)在于尋找近路；但當(dāng)存在負(fù)權(quán)重的邊時(shí)，我們可能會(huì)為了經(jīng)過(guò)負(fù)權(quán)重的邊而繞遠(yuǎn)。這種效應(yīng)使得我們要將查找 “最短” 路徑的感覺(jué)轉(zhuǎn)變?yōu)閷?duì)算法本質(zhì)的理解。因此需要拋棄直覺(jué)并在一個(gè)簡(jiǎn)單，抽象的層面上考慮這個(gè)問(wèn)題。

嘗試一

第一個(gè)想法是先找到權(quán)重最小（最小負(fù)值）的邊，然后將所有邊的權(quán)重加上這個(gè)負(fù)值的絕對(duì)值，這樣原有向圖就轉(zhuǎn)變成了一幅不含有負(fù)權(quán)重邊的有向圖。但這種做法不會(huì)解決任何問(wèn)題，因?yàn)樾聢D中的最短路徑和原圖中的最短路徑毫無(wú)關(guān)系。

嘗試二

第二個(gè)想法是改造 Dijkstra 算法。這種算法最根本的缺陷在于原算法的基礎(chǔ)在于根據(jù)距離起點(diǎn)的遠(yuǎn)近依次檢查路徑，添加一條邊會(huì)使路徑變得更長(zhǎng)。但添加任意負(fù)權(quán)重的邊只會(huì)使得路徑更短。

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

當(dāng)我們?cè)谘芯亢胸?fù)權(quán)重邊的有向圖時(shí)，如果該圖中含有一個(gè)權(quán)重為負(fù)的環(huán)，那么最短路徑的概念就失去意義了。如下圖，除了邊 5 -> 4 的權(quán)重為 -0.66 外，它和前面的示例完全相同。這里，環(huán) 4-> 7 -> 5 -> 4 的權(quán)重為：

0.37 + 0.28 - 0.66 = -0.01；

我們只要圍著這個(gè)環(huán)兜圈子就能得到權(quán)重任意短的路徑！注意，有向環(huán)的所有邊的權(quán)重并不一定都必須是負(fù)的，只要權(quán)重之和是負(fù)的即可。

定義：加權(quán)有向圖中的負(fù)權(quán)重環(huán)是一個(gè)總權(quán)重為負(fù)的有向環(huán)。

現(xiàn)在，假設(shè)從 s 到可達(dá)的某個(gè)頂點(diǎn) v 的路徑上的某個(gè)頂點(diǎn)在一個(gè)負(fù)權(quán)重環(huán)上。在這種情況下，從 s 到 v 的最短路徑是不可能存在的，因?yàn)榭梢岳眠@個(gè)負(fù)權(quán)重環(huán)構(gòu)造權(quán)重任意小的路徑。換句話(huà)說(shuō)，在負(fù)權(quán)重環(huán)存在的情況下，最短路徑問(wèn)題是沒(méi)有意義的。

當(dāng)且僅當(dāng)加權(quán)有向圖中至少存在一條從 s 到 v 的有向路徑且所有從 s 到 v 的有向路徑上的任意頂點(diǎn)都不存在于任何負(fù)權(quán)重環(huán)中時(shí)，s 到 v 的最短路徑才是存在的。

注意，要求最短路徑上的任意頂點(diǎn)都不存在于負(fù)權(quán)重環(huán)中意味著最短路徑是簡(jiǎn)單的，而且與正權(quán)重邊的圖一樣都能夠得到此類(lèi)頂點(diǎn)的最短路徑樹(shù)。

嘗試三

無(wú)論是否存在負(fù)權(quán)重環(huán)，從 s 到可達(dá)的其他頂點(diǎn)的一條最短的簡(jiǎn)單路徑都是存在的。為什么不定義最短路徑以方便尋找呢？但是，已知解決這個(gè)問(wèn)題的最好算法在最壞情況下所需的時(shí)間是指數(shù)級(jí)別的（后面會(huì)降到）。一般來(lái)說(shuō)，這種問(wèn)題太難了，只會(huì)研究它的簡(jiǎn)單版本。

因此，一個(gè)定義明確且可以解決加權(quán)有向圖最短路徑的算法要能夠：

• 1.對(duì)于從起點(diǎn)不可達(dá)的頂點(diǎn)，最短路徑為正無(wú)窮；
• 2.對(duì)于從起點(diǎn)可達(dá)但路徑上的某個(gè)頂點(diǎn)屬于一個(gè)負(fù)權(quán)重環(huán)的頂點(diǎn)，最短路徑為負(fù)無(wú)窮；
• 3.對(duì)于其他所有頂點(diǎn)，計(jì)算最短路徑的權(quán)重。

從文章的開(kāi)始到現(xiàn)在，我們?yōu)樽疃搪窂絾?wèn)題加上了各種限制，使得我們能夠找到解決相應(yīng)問(wèn)題的辦法。首先，我們不允許負(fù)權(quán)重邊的存在；其次不接受有向環(huán)?，F(xiàn)在我們放寬所有這些條件并重點(diǎn)解決一般有向圖中的問(wèn)題。

負(fù)權(quán)重環(huán)的檢測(cè)。給定的加權(quán)有向圖中含有負(fù)權(quán)重環(huán)嗎？如果有，找到它。

負(fù)權(quán)重環(huán)不可達(dá)時(shí)的單點(diǎn)最短路徑。給定一幅加權(quán)有向圖和一個(gè)起點(diǎn) s 且從 s 瓦法到達(dá)任何負(fù)權(quán)重環(huán)。是否存在一條從 s 到給定的頂點(diǎn) v 的有向路徑？如果有，找出最短的那條路徑。

總結(jié)：盡管在含有環(huán)的有向圖中最短路徑是一個(gè)沒(méi)有意義的問(wèn)題，而且也無(wú)法有效解決在這種有向圖中高效找出最短簡(jiǎn)單路徑的問(wèn)題，在實(shí)際應(yīng)用中仍然需要能夠識(shí)別其中的負(fù)權(quán)重環(huán)。例如，在最后期限限制下的任務(wù)調(diào)度問(wèn)題中，負(fù)權(quán)重環(huán)的出現(xiàn)可能相對(duì)較少；限制條件和最后期限都是從現(xiàn)實(shí)世界中的實(shí)際限制得來(lái)的，因此負(fù)權(quán)重環(huán)大多可能來(lái)自于問(wèn)題陳述中的錯(cuò)誤。找出負(fù)權(quán)重環(huán)，改正相應(yīng)的錯(cuò)誤，找到?jīng)]有負(fù)權(quán)重環(huán)問(wèn)題的調(diào)度方案才是解決問(wèn)題的正確方式。在其他情況下，找到負(fù)權(quán)重環(huán)就是計(jì)算的目標(biāo)。

Bellman-Ford 算法能夠有效解決這些問(wèn)題并且同樣適用于正權(quán)重邊的有向圖。

Bellman-Ford 算法。在任意含有 V 個(gè)頂點(diǎn)的加權(quán)有向圖中給定起點(diǎn) s ，從 s 無(wú)法到達(dá)任何負(fù)權(quán)重環(huán)，以下算法能夠解決其中的單點(diǎn)最短問(wèn)題：將 distTo[s] 初始化為 0 ，其他 distTo[ ] 元素初始化為無(wú)窮大。以任意順序放松有向圖所有邊，重復(fù) V 輪。

這個(gè)方法非常通用，因?yàn)樗鼪](méi)有指定邊的放松順序。下面將注意力集中在一個(gè)通用性稍遜的方法上，其中只放松從任意頂點(diǎn)指定的所有邊（任意順序）：

            for (int pass = 0; pass < G.V(); pass++)
            {
                for (v = 0; v < G.V(); v++)
                {
                    foreach (DirectedEdge e in G.Adj(v))
                        Relax(e);
                }
            }

它總是會(huì)放松 VE 條邊且只需稍作修改即可使算法在一般情景下更高效。

基于隊(duì)列的 Bellman-Ford 算法

其實(shí)，根據(jù)經(jīng)驗(yàn)我們很容易知道在任意一輪中許多邊的放松都不會(huì)成功：只有上一輪中的 distTo[ ] 值發(fā)生變化的頂點(diǎn)指出的邊才能夠改變其他 distTo[ ] 元素的值。為了記錄這樣的頂點(diǎn)，我們使用了一條 FIFO 隊(duì)列。算法在處理正權(quán)重標(biāo)準(zhǔn)樣圖中進(jìn)行的操作軌跡如下圖，在圖中，左側(cè)是每一輪中隊(duì)列中的有效頂點(diǎn)（紅色），緊接著是下一輪中的有效頂點(diǎn)（黑色）。首先將起點(diǎn)加入隊(duì)列，然后按照以下步驟計(jì)算最短路徑樹(shù)：

• 1.放松邊 1 -> 3 并將頂點(diǎn) 3 加入隊(duì)列；
• 2.放松邊 3 -> 6 并將頂點(diǎn) 6 加入隊(duì)列；
• 3.放松邊 6 -> 4, 6 -> 0 和 6 -> 2 并將頂點(diǎn) 4,0 和 2 加入隊(duì)列；
• 4.放松邊 4 -> 7，4 -> 5 并將頂點(diǎn) 7 和 5 加入隊(duì)列。放松已經(jīng)失效的邊 0 -> 4 和 0 -> 2。然后再放松邊 2 -> 7 （并重新為 4 -> 7 著色）。
• 5.放松邊 7 -> 5 （并重新為 4 -> 5 著色）但不將頂點(diǎn) 5 加入隊(duì)列（它已經(jīng)在隊(duì)列中了）。放松已經(jīng)失效的邊 7 -> 3。然后放松已經(jīng)失效的邊 5 -> 1， 5 -> 4 和 5 -> 7。此時(shí)隊(duì)列為空。

實(shí)現(xiàn)

根據(jù)上面的描述實(shí)現(xiàn) Bellman-Ford 算法所需的代碼很少，它基于以下兩種其他的數(shù)據(jù)結(jié)構(gòu)：

• 1.一條用來(lái)保存即將被放松的頂點(diǎn)的隊(duì)列 Queue；
• 2.一個(gè)由頂點(diǎn)索引的 bool 數(shù)組 OnQ[ ] ，用來(lái)指示頂點(diǎn)是否已經(jīng)存在于隊(duì)列中，以防止將頂點(diǎn)重復(fù)加入隊(duì)列。

首先，將起點(diǎn) s 加入隊(duì)列中，然后進(jìn)入一個(gè)循環(huán)，其中每次都從隊(duì)列中取一個(gè)頂點(diǎn)并將其放松。要將一個(gè)頂點(diǎn)插入隊(duì)列，需要修改之前的 Relax 方法實(shí)現(xiàn)，以便將被成功放松的邊所指向的頂點(diǎn)加入隊(duì)列中。這些數(shù)據(jù)結(jié)構(gòu)能夠保證：

• 1.隊(duì)列中不會(huì)出現(xiàn)重復(fù)的頂點(diǎn)；
• 2.在某一輪中，改變了 edgeTo[ ] 和 distTo[ ] 的值得所有頂點(diǎn)都會(huì)在下一輪中處理。

要完整地實(shí)現(xiàn)該算法，我們就需要保證在 V 輪后算法能夠終止。實(shí)現(xiàn)它的一種方法是顯式記錄放松的輪數(shù)。下面的代碼使用了另一種算法，后面詳細(xì)說(shuō)：它會(huì)在有向圖的 edgeTo[ ] 中檢測(cè)是否存在負(fù)權(quán)重環(huán)，如果找到則結(jié)束運(yùn)行。

    public class BellmanFordSP
    {
        private double[] distTo;//從起點(diǎn)到某個(gè)頂點(diǎn)的路徑長(zhǎng)度
        private DirectedEdge[] edgeTo;//從起點(diǎn)到某個(gè)頂點(diǎn)的最后一條邊
        private bool[] onQ;//該頂點(diǎn)是否存在于隊(duì)列中
        private Queue<int> queue;//正在被放松的頂點(diǎn)
        private int cost;//relax 的調(diào)用次數(shù)
        private IEnumerable<DirectedEdge> cycle;//edgeTo[] 中的是否有負(fù)權(quán)重環(huán)

        public BellmanFordSP(EdgeWeightedDigraph G,int s)
        {
            distTo = new double[G.V()];
            edgeTo = new DirectedEdge[G.V()];
            onQ = new bool[G.V()];
            queue = new Queue<int>();
            for (int v = 0; v < G.V(); v++)
                distTo[v] = Double.MaxValue;
            distTo[s] = 0;
            queue.Enqueue(s);
            onQ[s] = true;
            while (queue.Count != 0 && !HasNegativeCycle())
            {
                int v = queue.Dequeue();
                onQ[v] = false;
                Relax(G,v);
            }
        }

        //負(fù)權(quán)重環(huán)的檢測(cè)
        private bool HasNegativeCycle()
        {
            throw new NotImplementedException();
        }

        private void Relax(EdgeWeightedDigraph G, int v)
        {
            foreach (DirectedEdge e in G.Adj(v))
            {
                int w = e.To();
                if (distTo[w] > distTo[v] + e.Weight())
                {
                    distTo[w] = distTo[v] + e.Weight();
                    edgeTo[w] = e;
                    if (!onQ[w])
                    {
                        queue.Enqueue(w);
                        onQ[w] = true;
                    }
                }

                if (cost++ % G.V() == 0)
                    FindNegativeCycle();
            }
        }

        //查找負(fù)權(quán)重環(huán)
        private void FindNegativeCycle()
        {
            throw new NotImplementedException();
        }
    }

Relax 方法將成功放松的邊指向的所有頂點(diǎn)加入到一條 FIFO 隊(duì)列中（隊(duì)列中不出現(xiàn)重復(fù)的頂點(diǎn)）并周期性地檢查 edgeTo[ ] 表示的子圖中是否存在負(fù)權(quán)重環(huán)。

對(duì)于任意含有 V 個(gè)頂點(diǎn)的加權(quán)有向圖和給定的起點(diǎn) s ，在最壞情況下基于隊(duì)列的 Bellman-Ford 算法解決最短路徑問(wèn)題（或者找到從 s 可達(dá)的負(fù)權(quán)重環(huán)）所需的時(shí)間與 EV 成正比，空間和 V 成正比。

如果不存在從 s 可達(dá)的負(fù)權(quán)重環(huán)，算法會(huì)在進(jìn)行 V-1 輪放松操作后結(jié)束（因?yàn)樗凶疃搪窂胶械倪厰?shù)都小于 V-1）。如果的確存在一個(gè)從 s 可達(dá)的負(fù)權(quán)重環(huán)，那么隊(duì)列永遠(yuǎn)不可能為空。在第 V 輪放松之后，edgeTo[ ] 數(shù)組必然會(huì)包含一條含有一個(gè)環(huán)的路徑（從某個(gè)頂點(diǎn) w 回到它自己）且該環(huán)的權(quán)重必然是負(fù)的。因?yàn)?w 會(huì)在路徑上出現(xiàn)兩次且 s 到 w 的第二次出現(xiàn)處的路徑長(zhǎng)度小于 s 到 w 的第一次出現(xiàn)的路徑長(zhǎng)度。在最壞情況下，該算法的行為和通用算法相似并會(huì)將所有的 E 條邊全部放松 V 輪。

基于隊(duì)列的 Bellman-Ford 算法對(duì)于相同的問(wèn)題比較路徑長(zhǎng)度的次數(shù)少于 Disjkstra 算法。

負(fù)權(quán)重的邊

下圖顯示了Bellman-Ford 算法在處理含有負(fù)權(quán)重邊的有向圖的軌跡。首先將起點(diǎn)加入隊(duì)列 queue ，然后按照以下步驟計(jì)算最短路徑樹(shù)。

• 1.放松邊 0 -> 2 和 0 -> 4 并將頂點(diǎn) 2，4 加入隊(duì)列。
• 2.放松邊 2 -> 7 并將頂點(diǎn) 7 加入隊(duì)列。放松邊 4 -> 5 并將頂點(diǎn) 5 加入隊(duì)列。然后放松失效的邊 4 -> 7。
• 3.放松邊 7 -> 3 和 5 -> 1 并將頂點(diǎn) 3 和 1 加入隊(duì)列。放松失效的邊 5 -> 4 和 5 -> 7 。
• 4.放松邊 3 -> 6 并將頂點(diǎn) 6 加入隊(duì)列。放松失效的邊 1 -> 3 。
• 5.放松邊 6 -> 4 并將頂點(diǎn) 4 加入隊(duì)列。這條負(fù)權(quán)重的邊使得到頂點(diǎn) 4 的路徑變短，因此它的邊需要被再次放松。從起點(diǎn)到頂點(diǎn) 5 和 1 的距離已經(jīng)失效并會(huì)在下一輪修正。
• 6.放松邊 4 -> 5 并將頂點(diǎn) 5 加入隊(duì)列。放松失效的邊 4 -> 7 。
• 7.放松邊 5 -> 1 并將頂點(diǎn) 1 加入隊(duì)列。放松失效的邊 5 -> 4 和 5 -> 7 。
• 8.放松失效的邊 1 -> 3 。隊(duì)列為空。

在這個(gè)例子中，最短路徑樹(shù)就是一條從頂點(diǎn) 0 到頂點(diǎn) 1 的路徑。從頂點(diǎn) 4，5 和 1 指出的所有邊都被放松了兩次。

負(fù)權(quán)重環(huán)的檢測(cè)

實(shí)現(xiàn) BellmanFordSP 會(huì)檢測(cè)負(fù)權(quán)重環(huán)來(lái)避免陷入無(wú)限的循環(huán)中。我們也可以將這段檢測(cè)代碼獨(dú)立出來(lái)使得用例可以檢查并得到負(fù)權(quán)重環(huán)。在 BellmanFordSP 的構(gòu)造函數(shù)運(yùn)行之后，在將所有邊放松 V 輪之后當(dāng)且僅當(dāng)隊(duì)列非空時(shí)有向圖中才存在從起點(diǎn)可達(dá)的負(fù)權(quán)重環(huán)。如果是這樣， edgeTo[ ] 數(shù)組所表示的子圖必然含有這個(gè)負(fù)權(quán)重環(huán)。我們修改有向圖中的 DirectedCycle 類(lèi)來(lái)在加權(quán)有向圖中尋找環(huán)。這種檢查的成本分為以下幾個(gè)部分：

• 1.添加一個(gè)變量 cycle 和一個(gè)私有函數(shù)FindNegativeCycle 。如果找到負(fù)權(quán)重環(huán)，該方法會(huì)將 cycle 的值設(shè)為含有環(huán)中所有邊的一個(gè)迭代器（如果沒(méi)有找到則設(shè)為 null）。
• 2.每調(diào)用 V 次 Relax 方法后即調(diào)用FindNegativeCycle 方法。

這種方法能夠保證構(gòu)造函數(shù)中的循環(huán)必然終止。另外，用例可以調(diào)用HasNegativeCycle 來(lái)判斷是否存在從起點(diǎn)可達(dá)的負(fù)權(quán)重環(huán)。

        //查找負(fù)權(quán)重環(huán)
        private void FindNegativeCycle()
        {
            int V = edgeTo.Length;
            EdgeWeightedDigraph spt;
            spt = new EdgeWeightedDigraph(V);
            for (int v = 0; v < V; v++)
            {
                if (edgeTo[v] != null)
                    spt.AddEdge(edgeTo[v]);
            }

            EdgeWeightedCycleFinder cf;
            cf = new EdgeWeightedCycleFinder(spt);

            cycle = cf.Cycle();
        }

        //負(fù)權(quán)重環(huán)的檢測(cè)
        private bool HasNegativeCycle()
        {
            return cycle != null;
        }

        public IEnumerable<DirectedEdge> NegativeCycle()
        {
            return cycle;
        }

下圖是 Bellman-Ford 算法在一幅含有負(fù)權(quán)重環(huán)的有向圖中的運(yùn)行軌跡。頭兩輪放松操作與前面的例子一樣，在第三輪中，算法放松了邊 7 -> 3 和 5 -> 1 并將頂點(diǎn) 3 和 1 加入隊(duì)列后開(kāi)始放松負(fù)權(quán)重邊 5 -> 4 。在這次放松操作中算法發(fā)現(xiàn)了一個(gè)負(fù)權(quán)重環(huán) 4 -> 5 -> 4 。它將5 -> 4 加入最短路徑樹(shù)中并在 edgeTo[ ] 將環(huán)和起點(diǎn)隔離起來(lái)。從這時(shí)開(kāi)始，算法沿著環(huán)繼續(xù)運(yùn)行并減少到達(dá)所遇到的所有頂點(diǎn)的距離，直至檢測(cè)到環(huán)的存在，此時(shí)隊(duì)列非空。環(huán)被保存在 edgeTo[ ] 中，F(xiàn)indNegativeCycle 會(huì)在其中找到它。

7.總結(jié)

下表總結(jié)了上面的各種最短路徑算法的重要性質(zhì)。在這些算法中進(jìn)行選擇的第一個(gè)條件是問(wèn)題所涉及的有向圖的基本性質(zhì)。它含有負(fù)權(quán)重的邊嗎？它含有環(huán)嗎？它含有負(fù)權(quán)重的環(huán)嗎？除了這些基本性質(zhì)之外，加權(quán)有向圖的特性多種多樣，因此在有多個(gè)合適的選擇時(shí)就需要通過(guò)實(shí)驗(yàn)找出最佳算法。

到此這篇關(guān)于C#圖表算法之最短路徑的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。