[peterderivaz]

I guess you could find the shortest path by iteratively deleting an edge and checking whether the best cost has got worse. If it does get worse, then put that edge back in and try deleting another edge. If it does not get worse, then permanently delete that edge.

I think this should terminate (after trying all edges once each) with an example of the shortest path (that consists of all remaining edges).