给定最短路径来修改图的边的权重的算法
给定一个具有正权重的边，一对节点和一个节点之间的路径的图，告诉我如何在尽可能最小的范围内修改图的边权重以使指定的路径成为节点之间的最短路径（由A *计算）？ （当然，如果我将最短路径指定为输入，那么输出将是“不做任何更改”）。
注意：最小范围是指对边权进行的全部更改。 例如，另一个极端（最具破坏性的变化）是将所有边的权重不沿指定路径改变为无穷大，沿着路径改变为零。
您可以使用Floyd-Warshall算法计算所有路径的距离，然后修改所需的路径，使其成为最短路径。 例如，想象下面的3个节点的图。 
让路径是 - > b - > c。 Floyd-Warshall算法将计算以下矩阵。
带有绿色圆圈的数字是a→b（2）和b→c（4）的距离。 红色圆圈号码是a和c（3）之间路径的最短距离。 由于2 + 4 = 6≠3，所以您知道路径必须调整3以成为最小路径。
我建议这种方法的原因与计算最短路径的距离和相应地调整所需路径相反，这种方法允许您查看任意两个节点之间的距离，以便您可以根据需要调整边的权重。
这隐约提醒我神经网络训练中经常出现的后向传播策略。 我将草拟两种策略，第一种策略是有缺陷的：
c(P) 。 c(S) 。 (c(P) - c(S) - epsilon) / |P|降低每个边的权重w(p) ∈ P ，其中epsilon是一些消失的小常数，你希望你的路径小于c（S），并且|P| 是P的边数。 当然，这样做的问题在于，您可能会降低路径S （或其他路径）的成本，而不仅仅是降低P的成本！ 这暗示了这将需要一种迭代方法，从而您可以开始前进并减少相对于您在每个步骤重新计算的最短路径成本的给定权重的成本。 这是非常昂贵的，但感谢最短路径算法往往有很好的动态编程解决方案！
所以修改后的算法看起来像这样（假设i = 0开始）：
i步骤的成本，我们将称其为c(p_0...p_i) 。 c(S) ，以及它的第一个i分量的成本，我们用c(s_0...s_i) 。 c(p_0...p_i) - c(s_0...s_i) - epsilon降低边缘权重w(p_n) ，其中epsilon是一些消失的小常量，您希望您的路径小于c（S） 。 i增加1。 其中P = S开头，如果epsilon为0，则应该保持原路径不变。 否则，你应该减少不超过epsilon * |P| 超出理想的更新。
优化这个算法将需要你计算出如何以有效的方式从c(s_0...s_i)计算c(s_0...s_i+1) ，但是这对于读者来说是一个练习;-)
上一篇: Algorithm to modify the weights of the edges of a graph, given a shortest path