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$.
Existence of shortest path in a graph with no negative cycles?
graph theory;graphs;shortest path;weighted graphs
If there is a path $P$ from $s$ to $v$, there is one where no vertexoccurs more than once, with a weight that is less or equal to $P$. Indeed, if a vertex $x$ occurs twice, there is necessarily a loopfrom $x$ to itself. This loop cannot have a negative weight byhypothesis. So by removing it, we get a path that is no heavier. Thiscan be repeated until we obtain a path where no vertex occurs morethan once. Hence there are at most $n$ vertices on such a path, whichmeans that the path has at most $n-1$ edges.Thus we can consider only paths with at most $n-1$ edges, with eachedge occurring at most once, since any other path is no lighter than apath in that set.Since this set is finite, the number of edge conbinations to be used for apath is necessarily finite too (further limited by the constraint orforming a path from $s$ to $v$). Thus the set of weights has a minimumcorresponding to some path(s) wich is (are) the minimum /shortest path(s).