给定：无向加权连接图。 s，t 是顶点。
问题：找到一个尽可能有效的算法，返回从 s 到 t 的路径。在该路径中，具有最高权重的边缘将具有尽可能小的权重。因此，如果我们从 s，t 有 5 条路径，并且对于每条路径，我们都有最重的边，所以这 5 条的最小边。
我尝试过：
- 使用某种算法找到 s 和 t 之间的最短路径。
- 删除所有不属于我们发现的最短路径的边
- 使用BFS并进行一些修改，我们根据从s到t的路径数量运行BFS。每次我们找到最大边并将其存储在数组中时，我们都会找到数组的最小值。
我正在努力寻找一种可以在 (1( 中运行的算法，贝尔曼福特不起作用 - 因为它必须是有向图。Dijkstra 不起作用，因为我们不知道它是否有负圆圈或负边。Prim用于查找MST，我不知道它如何帮助我们找到最短路径。 有什么想法吗？
除此之外，如果您有可以解决此问题的算法，将不胜感激。
你可以用Kruskal的算法解决这个问题。 像往常一样添加边，并在 s 和 t 在同一聚类中时立即停止。
这个想法是，在算法的每个阶段，我们有效地添加了低于某个权重阈值的所有边。 因此，如果 s 和 t 位于同一聚类中，则它们之间存在一条路由，该路由完全由权重小于阈值的边组成。
您可以通过转换为 MST 问题来解决它，基本上 MST 中从 s 到 t 的路径将是具有最小可能最大权重的路径
- 在图形中找到最负的边
- 将其(权重+1(添加到每条边。
- 现在所有边缘都是正的，所以你可以应用Dijkstra的算法
- 您可以获取源和目标之间的shortest_path
- 现在计算源和目标之间的边数(例如 x(
- 真正的最短路径将是：shortest_path - x * (权重+1(