World's most popular travel blog for travel bloggers.

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

, , No Comments
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$.

Asked By : doge

Answered By : babou

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44574

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback