加權圖胖圖算法

Question

考慮一個連通的加權有向圖G =（V，E，w）。路徑P的肥胖是P中任何邊的最大權重。如何找到圖的最小可能肥胖程度？ Dijkstra的算法可以用來發現最小的肥胖嗎？

Answer 1

其實你正在考慮正確的方向，但Djkstra的算法只會讓你知道從單一來源（即單一來源最短路徑）的路徑最小的肥胖，但要找到整個圖的肥胖，你需要找到最短路徑所有節點到每個其他節點，因此您需要應用Floyd-Warshall算法。

希望它有幫助。