Algorithm to modify the weights of the edges of a graph, given a shortest path

Question

Given a graph with edges having positive weights, a pair of nodes, and a path between the nodes, what's the best algorithm that will tell me how to modify the edge weights of the graph to the minimum extent possible such that the specified path becomes the shortest path between the nodes (as computed by A*)? (Of course, had I specified the shortest path as input, the output would be "make no changes").

Note: Minimum extent refers to the total changes made to edge weights. For example, the other extreme (the most disruptive change) would be to change the weights of all edges not along the specified path to infinity and those along the path to zero.

Answer 1

You could use the Floyd-Warshall algorithm to compute the distances for all the paths, and then modify the desired path so that it becomes the shortest path. For example, imagine the following graph of 3 nodes.

Let the path be a -> b -> c. The Floyd-Warshall algorithm will compute the following matrix.

The numbers with green circles are the distances of a -> b (2) and b -> c (4). The red circled number is the shortest distance for a path between a and c (3). Since 2 + 4 = 6 ≠ 3, you know that the path must be adjusted by 3 to be the minimum path.

The reason I suggest this approach as opposed to just calculating the distance of the shortest path and adjusting the desired path accordingly is that this method allows you to see the distances between any two nodes so that you can adjust the weights of the edges as you desire.

Answer 2

This reminds me vaguely of a back-propagation strategy as is often found in neural network training. I'll sketch two strategies, the first of which is going to be flawed:

1. Compute the cost of your candidate path P, which we will call c(P).
2. Compute the cost of the shortest path S, which we will call c(S).
3. Reduce every edge weight w(p) ∈ P by (c(P) - c(S) - epsilon) / |P|, where epsilon is some vanishingly small constant by which you would like your path to be less than c(S), and |P| is the number of edges in P.

Of course, the problem with this is that you might well reduce the cost of path S (or some other path) by more than you reduce the cost of P! This suggests to me that this is going to require an iterative approach, whereby you start forwards and reduce the cost of a given weight relative to the shortest path cost which you recompute at each step. This is hugely more expensive, but thankfully shortest path algorithms tend to have nice dynamic programming solutions!

So the modified algorithm looks something like this (assume i = 0 to start):

1. Compute the cost of the first i steps of your candidate path P, which we will call c(p_0...p_i).
2. Compute the cost of the shortest path S, which we will call c(S), and the cost of its first i components, which we will denote by c(s_0...s_i).
3. Reduce edge weight w(p_n) by c(p_0...p_i) - c(s_0...s_i) - epsilon, where epsilon is some vanishingly small constant by which you would like your path to be less than c(S).
4. Repeat from step 1, increasing i by 1.

Where P = S to begin with, if epsilon is 0, you should leave the original path untouched. Otherwise you should reduce by no more than epsilon * |P| beyond the ideal update.

Optimizing this algorithm will require that you figure out how to compute c(s_0...s_i+1) from c(s_0...s_i) in an efficient manner, but that is left as an exercise to the reader ;-)