考虑一个连通的加权有向图。路径p的胖度是G = (V, E, w)中任何边的最大权重。
如何求出图的最小可能胖度？Dijkstra的算法可以用来寻找最小脂肪吗？
最佳答案
实际上，您的想法是正确的，但djkstra的算法只会让您知道从一个单一源（即单一源最短路径）的路径的最小胖度，但要找到整个图形的胖度，您需要找到从所有节点到每个其他节点的最短路径，所以您需要应用floyd–warshall算法。
希望有帮助。
考虑一个连通的加权有向图。路径p的胖度是G = (V, E, w)中任何边的最大权重。
如何求出图的最小可能胖度？Dijkstra的算法可以用来寻找最小脂肪吗？
最佳答案
实际上，您的想法是正确的，但djkstra的算法只会让您知道从一个单一源（即单一源最短路径）的路径的最小胖度，但要找到整个图形的胖度，您需要找到从所有节点到每个其他节点的最短路径，所以您需要应用floyd–warshall算法。
希望有帮助。