圖形上的動態規劃

習題預習

1. 在一個有向圖中，從起點到終點有多少條路徑可以經過恰好k個邊？

2. 在一個加權有向圖中，找到起點到終點的最短路徑。

3. 已知一個無向圖，選出一些邊使得所得的圖是一棵樹，並且所有邊權值總和最小。

4. 在一個有向圖中，找到從起點到終點的任意一條路徑上權值最小的邊的權值。

5. 已知一個有向無環圖（DAG），計算從起點到終點的最長路徑長度。

說明知識

動態規劃在圖形上的應用可以幫助我們找到圖形中的最優解。動態規劃基於一個子問題的累計解法，將問題分解為更小的子問題並將這些解合併為原始問題的解。在圖形中，這意味著找到圖形中所有可能路徑的最優解，並將這些最優解合併為圖形的整體最優解。

例如，考慮以下圖形：

A—>B
| \ |
v  v|
D—>C

假設我們想要找到從節點A到節點C的最短路徑。我們可以使用動態規劃來解決這個問題。我們首先從節點A開始，並計算到達節點B的最短路徑。然後，我們更新節點A到節點C的最短路徑，使用節點B到節點C的最短路徑來確定這個值。最後，我們找到到達節點D的最短路徑，並更新從節點A到節點D的路徑。這樣，我們就可以找到節點A到節點C的最短路徑。

動態規劃在圖形上的另一個應用是最大權重匹配。在這種情況下，我們需要準確地匹配每個節點，以確保獲得最大權重的匹配。使用動態規劃，我們可以搜索圖形並找到每個節點的最大權重匹配。然後，我們可以將這些最大權重匹配合併為圖形的整體最大權重匹配。

總體而言，動態規劃在圖形上的應用可以幫助我們有效地解決各種問題，包括最短路徑和最大權重匹配等。

彙總重點

1. 最短路徑算法

2. 最長路徑算法

3. 最小生成樹算法

4. 最大流算法

5. 最小割算法

6. 圖上最大匹配算法

7. 圖上最小點覆蓋算法

8. 圖上最大獨立集算法

9. 形成圖的演算法

10. 快速算法

11. 模型簽名

12. 圖形劃分算法

知識測驗

1. 雙語詞典（Bilingual Dictionary）
   給定一個雙語詞典，以及一系列的單詞對。你的任務是通過這個詞典進行翻譯，找到所有這些單詞對之間的翻譯路徑，並且使得翻譯路徑的總長度最小。

答案：https://www.acwing.com/problem/content/description/2573/

2. 網絡延遲時間（Network Delay Time）
   在給定的網絡上，有n個節點和m條有向邊。每條邊都有一個與之相關的時間代價。請你找到一個節點，使得從該節點出發，能夠到達其它所有節點的最短時間為何。

答案：https://leetcode-cn.com/problems/network-delay-time/

3. 拓撲排序問題（Topological Sorting）
   在一個有向無環圖中，進行所有節點的拓撲排序。

答案：https://www.acwing.com/problem/content/description/3689/

4. 最長路徑問題（Longest Path）
   在一個加權有向無環圖中，找到最長的路徑（邊權值之和最大的路徑）。

答案：https://www.acwing.com/problem/content/description/3691/

5. 尋找一條環（Finding a Cycle）
   在一個帶有權重的有向無環圖中，尋找其中一條環。

答案：https://www.acwing.com/problem/content/description/2577/