algorithm - 图形中的所有最短路径，只有一次更改

Question

假设我有一个边上有正整数权重的有向图 G(V,E)。我需要做的是找到其中一些节点之间的最小距离。在这个最小距离路径中，我最多可以使用 K 个反向边. 例如，对于这个输入：

6（节点）

9（边）

2（正整数 K）

10（我需要找到最小距离的边对数）

2 1 2（2->1 的边，重量为 2）

3 2 7（边缘为 3->2，重量为 7）

4 5 6

1 3 8

1 4 4

5 2 8

5 6 10（边缘 7）

1 5 5（边 8）

4 2 5（边 9）

1 6 1（问题 1：使用 1 个反向边缘找到从 1->6 的最小距离）

3 5 0 （问题 2：使用 0 反向边缘找到从 3->5 的最小距离）

1 2 0

3 5 1

1 2 1

4 3 1

6 4 0

2 6 2

6 4 1

6 4 2（问题 10）

输入的不同部分可以使用边数（9，前 9 行包含 3 个数字）和所问问题的数量（10，边之后的 10 行）来分隔

输出必须是：

15（对问题 1 的回答：使用 1 个反向边缘从 1->6 的最小距离为 15）

14

9

13

2

12

不可能（这两个边缘之间没有使用 0 个反向边缘的路径）

17

24

16

我考虑过为每个问题和每个边缘运行 Dijkstra，而不是仅仅计算与源的单个最小距离也使用反向边缘并在不使用超过 K 个反向边缘的情况下尽可能地更新值。（标签类似于 (节点号，与源的最小距离，使用的反向边缘）。但是 dijkstra 找到了从源到所有其他节点的最短路径，我认为这对我的实例来说可能是一种过度杀伤。这能以某种方式更有效地完成吗？

标签： algorithm

Answer 1

您可以在每个节点上运行 dijkstra，将图视为无向图。您需要跟踪最小距离和使用的反向节点数。例如，我们将起始节点设为 3。

假设我们需要在问题中找到 (3 1 0) 和 (3 1 1)。

我们将节点 3 初始化为 (0,0)，将所有其他节点初始化为 (INFINITY,0)。从节点 3，我们可以直接到节点 2 或反向到节点 1。所以我们得到

节点 1(8,1) 和节点 2(7,0)

从节点 2，我们沿直线方向到达节点 1。因此我们得到

节点 1(8,1)(9,0)。这意味着从节点 3 到节点 1 的最小值如果 0 条边被反转，则为 9，如果 1 条边反转，则为 8。

对于每个节点，您可以在 HashMap 中跟踪它们，答案是 0 到 k 之间的最小距离。例如，我们可能会得到 Node2(7,0)(10,2)。当两个边缘被允许反转时，答案仍然是 7，因为 10>7。

该算法的复杂度为 O(n*(n+m))。