最小权重路径
Minimum Weight Path
"Given a connected undirected weighted graph, find the maximum weight of the edge in the path from s to t where the maximum weight of the edges in the path is the minimum."
这似乎是一个 Floyd–Warshall 算法问题。有没有比 O(V^3) 更快的方法？
我提出广度优先搜索 (BFS) 以确定 s 是否通过任何路径连接到 t 可以 运行 in O(V) 次，因为每个顶点只需要访问一次。
因此，我建议解决这个问题的方法是按权重对边进行排序，然后
while the BFS succeeds in finding a path from s to t
remove the highest weighted edge from the graph
在 BFS 失败之前要删除的最后一条边是您要查找的最大加权边。
总 运行ning 时间是 O(E log E) 按权重对边进行排序，加上 O(VE) 到 运行 BFS，直到删除边断开图形。
"Given a connected undirected weighted graph, find the maximum weight of the edge in the path from s to t where the maximum weight of the edges in the path is the minimum."
这似乎是一个 Floyd–Warshall 算法问题。有没有比 O(V^3) 更快的方法？
我提出广度优先搜索 (BFS) 以确定 s 是否通过任何路径连接到 t 可以 运行 in O(V) 次，因为每个顶点只需要访问一次。
因此，我建议解决这个问题的方法是按权重对边进行排序，然后
while the BFS succeeds in finding a path from s to t
remove the highest weighted edge from the graph
在 BFS 失败之前要删除的最后一条边是您要查找的最大加权边。
总 运行ning 时间是 O(E log E) 按权重对边进行排序，加上 O(VE) 到 运行 BFS，直到删除边断开图形。