0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour.if you have not yet done so. When posting a question, make sure to give enough context, and show how you tried to answer it on your own, and what may have blocked you, so as to be very precise regarding your problem. This helps better answers. So, what have you tried to solve it? Where did you get blocked? $\endgroup$ – babou Jul 20 '15 at 21:48
  • $\begingroup$ Why do you distinguish a source vertex? This applies to any pair of vertices. $\endgroup$ – babou Jul 20 '15 at 23:04
  • $\begingroup$ I removed the tag algorithms since your question does not ask for an algorithm, but only for a proof of existence. $\endgroup$ – babou Jul 20 '15 at 23:49
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Basically you have not much options here – do relaxation on each vertex peeking them from the list like Bellman-Ford does and you'll end up with a shortest path to one vertex, and move on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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