algorithm - 具有最小最大边权重的路径

Question

假设我们有一个有向非负加权图。

我们必须找到 (u, v) 之间的最小成本路径。路径的成本定义为路径包含的第二最昂贵的边的最大成本。

这是一个例子。

具有 4 个节点和 4 个边的图:

• 从 1 到 2，费用为 3
• 从 1 到 3，成本为 7
• 从 2 到 3，费用为 5
• 从 3 到 4，费用为 2

1 和 4 之间的最佳路径应该是 1 - 3 - 4，总成本为 2(成本是 2 和 7，第二高的是 2)。

Dijkstra标准的SSSP(重构路径，寻找次高边)显然行不通。我在 MST 考虑过(这应该没问题)但不能保证覆盖最佳路径 (u,v)。

Answer 1

我们可以得到 O(E + V log V)，对于足够密集的图，它是 o(E log E)。将 Dijkstra 与 Fibonacci 堆一起使用，计算两棵最大权重(相对于第二最大权重)最短路径树，一棵从根 u 指向叶方向，一棵指向根方向到根 v。对于每条边 s->t，考虑由从 u 到 s 的最大权重最短路径、边 s->t 和从 t 到 v 的最大权重最短路径组成的路径，其第二个最大权重以 u-> 的最大值为界s 和 t->v 段。