一种修改图边权的算法，基于给定的最短路径。

Question

给出一张带有正权边的图、一对节点和它们之间的路径，想要找到一种最佳算法，该算法可以告诉我如何修改图的边权重，使得指定的路径尽可能地成为A*算法计算的节点间的最短路径。当然，如果我将最短路径作为输入，输出将是“不做任何更改”。

注意：最小程度指的是对边权进行的总更改。例如，另一个极端情况是将未在指定路径上的所有边的权重更改为无穷大，而沿着路径的权重更改为零。

- Mikhil Masli

Answer 1

这让我想起了神经网络训练中常见的反向传播策略。我将概述两种策略，第一种将存在缺陷：

1. 计算候选路径P的成本，我们将其称为c(P)。 2. 计算最短路径S的成本，我们将其称为c(S)。 3. 将P中的每条边权重w(p)减少(c(P) - c(S) - epsilon) / |P|，其中epsilon是您希望路径小于c(S)的某个非常小的常数，|P|是P中边的数量。

当然，问题在于你可能会把路径S（或其他路径）的成本减少得比P的成本更多！这使我想到这将需要一种迭代方法，在该方法中，您从前往后开始，并相对于重新计算的最短路径成本减少给定权重的成本。这要昂贵得多，但幸运的是，最短路径算法通常具有良好的动态规划解决方案！

所以修改后的算法大致如下（假定起始时i = 0）：

1. 计算候选路径P的前i步的成本，我们称之为c(p_0...p_i)。
2. 计算最短路径S的成本，我们称之为c(S)，以及它的前i个组件的成本，我们用c(s_0...s_i)表示。
3. 将边权重w(p_n)减少c(p_0...p_i) - c(s_0...s_i) - epsilon，其中epsilon是一些接近于零的常数，您希望路径小于c(S)。
4. 从步骤1开始重复，将i增加1。

如果epsilon为0，则P = S。否则，你应该不超过理想更新的epsilon * |P|减少。

优化这个算法需要你找出如何以高效的方式计算c(s_0...s_i+1)，从c(s_0...s_i)中推导出来，但是这留给读者自己思考。;-)

- Gian

Answer 2

你可以使用Floyd-Warshall算法来计算所有路径的距离，然后修改所需路径使其成为最短路径。例如，想象一下以下3个节点的图形。 让路径为a-> b-> c。 Floyd-Warshall算法将计算以下矩阵。

绿色圆圈中的数字表示a->b（2）和b->c（4）之间的距离。红色圆圈中的数字表示a和c之间路径的最短距离（3）。由于2 + 4 = 6 ≠ 3，因此您知道路径必须调整3才能成为最小路径。我建议采用这种方法而不是仅计算最短路径的距离并相应地调整所需的路径，因为这种方法允许您查看任意两个节点之间的距离，以便您可以根据需要调整边缘的权重。

- isaach1000

---

你如何避免这种方法的不稳定性呢？如果最短路径与候选路径重叠怎么办？修改候选路径权重将使最短路径更短！ - Gian

弗洛伊德-沃舍尔算法可以存储每个节点的前一个节点以存储最短路径。您可以修改与最短路径不重叠的理想路径的部分。 - isaach1000