algorithm - 加权图肥胖算法

Question

考虑一个连通的加权有向图G = (V, E, w)。路径 P 的胖度是 中任何边的最大权重P。

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

Answer 1

实际上你的想法是正确的，但 Djkstra 的算法只会让你知道来自单个源的路径的最小胖度（即单源最短路径），但是要找到整个图的胖度，你需要找到从所有节点到每个节点的最短路径其他节点，所以你需要应用Floyd-Warshall 算法。

希望能帮助到你。