In an introductory course on Dijkstra's algorithm, I enunciated the following lemma :
Let x →* z be a shortest path in a weighted graph and let y be any vertex along that path. It follows that x →* y and y →* z are shortest paths too.
To which one of my students pointed out that it does not seem to hold in the undirected graph that I used to explain that Dijkstra's algorithm needs weights to be nonnegative :
B (-7) / \ (8) / \ A C \ / (3) \ / (2) D
Indeed, a shortest path from C to A is C -> B -> A with total weight 1, but path C -> B with weight 8 is not a shortest path : C -> D -> A -> B with weight -2 is better.
In the short term I could continue by restricting my lemma to nonnegative weights. Cormen et al. give that lemma for arbitrary weights but for directed graphs only, and this holds.
I feel my counter-example is an… edge(!) case about the notion, wrt undirected graphs, of paths, cycles and the prohibition of negatively weighted cycles for shortest-path problems. The example does not have a negative-weight cycle for any reasonable notion of a cycle, but to create the same contradiction to the lemma in a directed graph, we would need an edge A -> B and an edge B -> A both with weight -7, which would give a cycle of weight -14.
Does anybody have a satisfactory version of the lemma that would work in both directed and undirected graphs, for arbitrary weights ? ie., are there versions of the notions of path, shortest path and so on, were a version of the lemma would hold ?
Especially in relation to proving eg. the validity of Floyd-Warshall's or Bellman-Ford's algorithms, which iirc also work with undirected graphs, provided they do not have a negative-weight cycle.