1. 首页
  2. 问答
  3. 加权图胖图算法

加权图胖图算法

2017-10-04 32 views
1

考虑一个连通的加权有向图G =（V，E，w）。路径P的肥胖是P中任何边的最大权重。如何找到图的最小可能肥胖程度？ Dijkstra的算法可以用来发现最小的肥胖吗？加权图胖图算法

来源

2017-10-04 Alviss Min

+4

图的肥胖程度是多少？您已经为路径定义了它，但不是图形 – m7mdbadawy

+3

您是否在特定约束条件下搜索路径？如果没有限制，最小重量的边缘是否是一个解决方案？ – Codor

+0

该图有很多路径，基本上我需要找到的是具有最小权重的路径。 –

回答

1

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

希望它有帮助。

来源

2017-10-04 13:02:28

相关问题

 相关问题