上一章節介紹了Topological Sort是什麼，這章節會介紹其實際應用。

我們來看看找出DAG shortest path可以怎麼找：

以上圖為例，看來一樣可以透過Dijkstra(粉紅色的數字為relax後，距離原點s的距離)來找出答案：0, 1, 3, 4, 5, 2。

但有個問題，假若graph有edge是負值呢？

丸子，由於點5已經從點4 relax完了，雖然有成功從點2 relax到點4 最正確distTo數值，但是點5就更新不到了，因為已經從點3 → 點4 → 點5的路徑用掉了。

該如何克服這個問題呢？沒有錯，就是應用topological sort：

這樣就不會因為先後順序的關係而更新不到最正確的distTo數值：

接著來想想，若我們想要找出最長的路線該如何走呢？實際上這個議題還沒有人能夠找出一個正面去解決的演算法！但是其實有個取巧的方法就可以做到一樣的效果：

那就是把所有edge的值 * -1，然後一樣進行DAG的shortest path演算法，就可以得到一樣的結果了~

先前介紹地找出longest path的手法其實也有專有名詞，就是Reduction：

The problem solving we just used probably felt a little different than usual:

• Given a graph G, we created a new graph G’ and fed it to a related (but different) algorithm, and then interpreted the result.

This process is known as Reduction.

• Since DAG-SPT can be used to solve DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License