加权图肥度算法

Question

考虑一个连通的加权有向图G = (V, E, w)。路径 P 的肥度是 P.

中任意边的最大权重

如何找到图形的最小可能肥度？可以使用 Dijkstra 算法找到最小脂肪吗？

Answer 1

实际上你的思考方向是正确的，但 Djkstra 的算法只会让你知道来自单一来源的路径的最小肥度（即单一来源最短路径），但要找到整个图的肥度，你需要找到最短路径从所有节点到每个其他节点，因此您需要应用 Floyd–Warshall 算法.

希望对您有所帮助。