算法：有向無環圖的最短路徑

        介紹

        我們已經知道了如何通過 Dijkstra 算法在非負權圖中找到最短路徑。即使圖中有負權邊，我們也知道通過 Bellman-Ford 算法找到一個從給定的源點到其它所有節點的最短路徑。現在我們將看到一個在線性時間內運行得更快的算法，它可以在有向無環圖中找到從一個給定的源點到其它 所有可達頂點的最短路徑，又名有向無環圖（DAG）。

        由于有向無環圖無環所以我們不必擔心負環的問題。正如我們已經知道在負環里討論最短路徑是毫無意義的一樣，因為我們可以在這些環里不斷“循環”，但實際上我們得到的路徑將變得越來越短（構成負的環路，存在死循環）。

        負環的存在使我們試圖找到最短路徑的行為變得毫無意義！

        因此，我們要解決 Dijkstra 算法和的 Bellman-Ford 算法中的兩個問題。首先，我們只需要非負的權重，其次，圖中不能有環。好了，這樣我們就可以通過這個算法處理滿足這兩種情況的例子了。

        概述

        關于有向無環圖（DAGs）我們首先要知道，它們可以很容易地進行拓撲排序。拓撲排序應用范圍非常之廣，其中最常用的或許就是用于安排依賴任務（依賴任務是同屬于一個工作中相同任務的實體，這些實體是保證互連的，它們解決共同的問題）。

        拓撲排序通常是用來“排序”依賴任務的！

        經過拓撲排序，我們最終會得到一張 DAG 圖的頂點列表，我們確信在拓撲排序列表中如果存在一條邊（u，v），那么頂點u會先于頂點v進入列表中。

        如果有一條邊（u，v），那么頂點u一定在頂點v前面。這個結果通過這張圖片變得更加通俗易懂。其中B和D之間沒有邊，但在列表中B在D前面！

        此信息異常重要，我們唯一需要做的事情就是通過這個排序列表來計算距離最短的路徑，這和 Dijkstra 算法比較相似。

        好了，讓我們來總結一下這個算法：

        -首先，我們必須對有向無環圖進行拓撲排序;

        -其次，我們將到源點的距離初始化為 0 并將到其它所有頂點的距離設置為無窮大;

        -最后，對于列表中的每一個頂點，我們從它的所有鄰節點中找到最短路徑的那個頂點;

        這很像 Dijkstra 算法，但是其主要區別是我們使用了一個優先級隊列，并且此次我們使用的是經過拓撲排序的列表。

        代碼

        此次的代碼實際上是一段偽代碼。雖然目前為止所有的例子都是用 PHP 編寫，但是偽代碼更易于理解，也不會將你與某一特定的語言實現綁定在一起。此外，如果你對給定的語言感到難以理解，那么對你而言讀懂代碼比閱讀偽代碼更加困難。
來自: www.importnew.com