graph - 给定最短路径，修改图边权重的算法

Question

给定具有正权重的边、一对节点和节点之间的路径的图，什么是最好的算法，它会告诉我如何将图的边权重修改到尽可能小的程度，以使指定的路径成为节点之间的最短路径（由 A* 计算）？（当然，如果我指定最短路径作为输入，输出将是“不做任何更改”）。

注意：最小范围是指对边权重所做的总更改。例如，另一个极端（最具破坏性的变化）是将不沿指定路径的所有边的权重更改为无穷大，将沿路径的所有边的权重更改为零。

Answer 1

您可以使用 Floyd-Warshall 算法计算所有路径的距离，然后修改所需路径，使其成为最短路径。例如，想象下图的 3 个节点。

设路径为 a -> b -> c。Floyd-Warshall 算法将计算以下矩阵。

带绿色圆圈的数字是 a -> b (2) 和 b -> c (4) 的距离。红色圆圈数字是 a 和 c (3) 之间路径的最短距离。由于 2 + 4 = 6 ≠ 3，所以你知道路径必须调整 3 才能成为最小路径。

我建议这种方法而不是仅仅计算最短路径的距离并相应地调整所需路径的原因是，这种方法允许您查看任意两个节点之间的距离，以便您可以根据需要调整边缘的权重.

Answer 2

这让我隐约想起了神经网络训练中常见的反向传播策略。我将勾勒出两种策略，其中第一种是有缺陷的：

1. 计算你的候选路径 P 的成本，我们称之为c(P)。
2. 计算最短路径 S 的成本，我们称之为c(S)。
3. 将每条边的权重w(p) ∈ 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 开始重复，增加i1。

从哪里P = S开始，如果epsilon为 0，则应保持原始路径不变。否则，您应该减少不超过epsilon * |P|理想更新。

优化此算法将需要您弄清楚如何以有效的方式计算c(s_0...s_i+1)，c(s_0...s_i)但这留给读者作为练习;-)