Algorithm to modify the weights of the edges of a graph, given a shortest path
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.
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.