有向無環圖最短路徑（按拓樸排序鬆弛）
當路網完全沒有環——每條路都指向「前方」，你永遠無法回到離開過的城市——最短路徑問題就變得異常容易。你可以把所有城市排成一列，使每條路都由左指向右，然後嚴格按那個順序處理它們。當你抵達某城市時，所有通往它的路線都已被考慮過，故它的距離是最終值。不需要優先佇列，不需要重複趟數；一次掃過就夠。
圖必須是有向無環圖（DAG）。先算出一個拓樸排序——把頂點線性排列，使每條邊都從較前的頂點指向較後的頂點（正因沒有環才可能）。然後按那個順序處理頂點，對每一個鬆弛它所有的外向邊。為何一趟就夠？當你處理頂點 u 時，每個有邊指向 u 的頂點在順序中都更早，且都已被處理，故在你用到 d[u] 之前它就已是最終值。這是拓樸順序的不變量：距離嚴格由左到右定案。成本是 O(V + E)——線性——計入拓樸排序加上每條邊各鬆弛一次。
DAG 最短路徑出現在專案排程（有先決條件的任務）、建置系統與試算表中的關鍵路徑分析，以及在子問題 DAG 上的動態規劃——事實上許多 DP 遞迴式正是這個演算法的偽裝。漂亮的額外好處是：因為保證正確性的是順序而非權重的正負號，這個方法毫無困難地處理負權邊，而你只要把比較翻轉就能找最長路徑。唯一的要求是無環性；一旦存在環，就不存在有效的拓樸排序，你必須退回戴克斯特拉或貝爾曼-福特。
任務 a->b (3)、a->c (2)、b->d (1)、c->d (5)。拓樸順序 a、b、c、d。處理 a：d[b]=3、d[c]=2。處理 b：d[d]=3+1=4。處理 c：d[d]=min(4, 2+5)=4。處理 d：無事。dist(d)=4，在一次由左到右的掃過中找到——若改為取最大，同一方法給出最長路徑（關鍵路徑）。
在拓樸順序下，每個前驅在某頂點被使用前都已定案，故一趟即可在 O(V+E) 內定案所有距離。
這個線性時間方法只在 DAG 上有效。與戴克斯特拉不同，它容許負權重，但只要有一個有向環，拓樸排序就不可能，迫使你改用貝爾曼-福特。