1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ A better question could be "what is an efficient algorithm to determine that a subpath optimality holds for a given graph?" or "How fast can we determine whether the subpath optimality holds for a given graph faster than the obvious approach?". The obvious approach is basically, of course, to determine all optimal paths and verify that for every optimal path p, p without its last edge is also optimal. $\endgroup$
    – John L.
    Commented May 3, 2022 at 15:38
  • $\begingroup$ Is there a polynomial-time algorithm? $\endgroup$
    – John L.
    Commented May 3, 2022 at 15:40
  • $\begingroup$ Thanks for your comments that shows that the scope of the question was not explicit enough : I am not presently interested in what is concretely true in one or another graph ; I want to now if there exists a presentation of the notions that allows for a passable lemma. Eg. I know that not everybody uses the same definition of a path wrt repetition of edges. $\endgroup$
    – ysalmon
    Commented May 3, 2022 at 15:44

1 Answer 1

Reset to default
2
$\begingroup$

You actually have the idea here:

... 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.

If you apply the implementation of Dijkstra's algorithm to an undirected graph, it will treat the graph as if it is directed such that undirected edges are treated as two directed edges - one going in and another going out, and both edges having the same weight. The reason is simple, for every vertex $u$, if $u$ is selected in an iteration of the algorithm such that $v$ is one of its neighbor, vertex $u$ will again be considered when $v$ is selected in a later time. Hence, you can say that the algorithms treat each undirected edge as if they are edges in a cycle.

With that, you can claim that your graph essentially has a negative weight cycle, hence the problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.