One minor foible. Don't select edges that are part of the minimum path, instead remove edges that are not part of the minimum path until only the minimum path remains. This strategy works even on graphs with multiple minimum paths.
I don't get why having multiple optimal paths would falsify my algorithm. Can you provide an explicit counter-example?
Here is why I think the algorithm is correct:
At each step the edge that we are considering is either contained in all the optimal solutions or only some of them. If the edge is contained in all the solutions, increasing its weight to infinity would change the optimal solution and we pick that edge in our solution. Otherwise (if the edge is contained in only some of the solutions) increasing the weight would not change the solution because there is another optimal solution that does not contain that edge so we do not pick that edge.
So we can prove this theorem: At every step of the algorithm if an edge is picked, it is contained in all the optimal solutions.
So the algorithm does not pick any extra edges. Now we have to prove that it includes all the necessary edges. But that is easy because each time that we choose not to including an edge, we are sure that there is an optimal solution in the remaining graph so we are never left with a graph with no optimal solution.
I think you assumed that I meant we change the edge weights
from infinity back to their original value at each step but that is not what I meant.
