World's most popular travel blog for travel bloggers.

# [Solved]: Existence of shortest path in a graph with no negative cycles?

, ,
Problem Detail:

Suppose that the input graph \$G\$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let \$s\$ be the source vertex.

How do I prove that for every vertex \$v\$ in \$G\$, there is a shortest \$s-v\$ path with \$<= n - 1\$ edges?

Where \$n\$ is the number of vertices in \$G\$.

If there is a path \$P\$ from \$s\$ to \$v\$, there is one where no vertex occurs more than once, with a weight that is less or equal to \$P\$. Indeed, if a vertex \$x\$ occurs twice, there is necessarily a loop from \$x\$ to itself. This loop cannot have a negative weight by hypothesis. So by removing it, we get a path that is no heavier. This can be repeated until we obtain a path where no vertex occurs more than once. Hence there are at most \$n\$ vertices on such a path, which means that the path has at most \$n-1\$ edges.

Thus we can consider only paths with at most \$n-1\$ edges, with each edge occurring at most once, since any other path is no lighter than a path in that set.

Since this set is finite, the number of edge conbinations to be used for a path is necessarily finite too (further limited by the constraint or forming a path from \$s\$ to \$v\$). Thus the set of weights has a minimum corresponding to some path(s) wich is (are) the minimum /shortest path(s).