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->6使用1个反边的最小距离为15)

14

9

13

2

12

不可能(这两条边之间没有路径使用 0 个反向边)

17

24

16

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

Answer 1

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

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

我们将节点 3 初始化为 (0,0)，将所有其他节点初始化为 (INFINITY,0)。从节点 3，我们可以沿直线方向到达节点 2，也可以反向到达节点 1。于是我们得到

Node 1(8,1) and Node 2(7,0)

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

Node1(8,1)(9,0). This means Minimum value from node 3 to node 1 is 9 if 0 edges are reversed and 8 if 1 edge is reversed.

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

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