Proof Verification - Weighted Paths in Digraphs

Question

I found this lemma in my notes for a Combinatorial Optimization course I am revising for and I tried proving it myself. The Lemma is as follows:

Let $D$ be a weighted digraph that has no negative length cycles and let $i,j$ be any two vertices. If there is an $(i,j)$-walk then (a) there exists a shortest $(i,j)$-walk and (b) there exists a shortest $(i,j)$-walk that is a path.

My attempt at proving this is as follows:

(a) (I am making the strong assumption that all weights are integers and hence all total lengths are integers). Let $S$ be the set of all lengths of all $(i,j)$-walks in $D$. $S$ is a finite set since $D$ is a finite graph. By the well-ordering principle, there must be a smallest element in $S$, hence there is a shortest walk.

(b) (for the second part, there is another lemma in my notes that essentially says that we can keep removing cycles from a walk until we get a path). Let $W'$ denote the shortest walk. From (a) we know it exists. Now if there is no repeated vertex in $W'$, we are done. Otherwise, repeatedly delete any circuits.

Is this correct?

Thanks!

Answer 1

Your proof is correct, in the case where all weights are integers. As Mees de Vries pointed out, you cannot assume that $S$ is finite, but that does not impede your proof, since any subset of $\mathbb Z^+$ has a smallest element, finite or not.

For the general case where weights are arbitrary real numbers, you can proceed as follows.

• First, show that there is a shortest path from $i$ to $j$. This follows because there are only finitely many paths from $i$ to $j$. Let $P$ be the shortest path.

• Second, let $W$ be any walk. In order to show that the shortest walk exists, it suffices to show the length $W$ is at least the length of $P$. As you proved before, this follows by short-circuiting $W$, then applying the minimality of $P$.

Answer 2

As it stands, your proof is not correct. In particular, the set $S$ need not be finite. Consider a graph like $$ a \rightarrow^1 b \leftrightarrow^1 c \rightarrow^1 d $$ (where the weights are as "superscripts" on the arrows). Then there are $(a, d)$-walks of lengths $3, 5, 7, 9, \ldots$.