4
$\begingroup$

We are given directed weighted graph with edges having strictly positive weight(>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this graph, finding the single-source-shortest paths from $1$ in the normal graph and the single-source-shortest path from $N$ in the inverse graph we can check for each edge whether it belongs to some shortest path or not.

If we take all the edges that belong on some shortest path and build a separate graph we will get a directed acyclic graph. How can we prove that this graph will never have a cycle? I haven't written many proofs on graphs before, so I solved the problem, however I'm not sure why this will always hold.

$\endgroup$
  • $\begingroup$ Try a proof by contradiction: assume the graph of shortest paths you described has a cycle. Now prove that the paths that form the cycle cannot be shortest. $\endgroup$ – Daniel Mar 16 at 10:42
1
$\begingroup$

Suppose there is a cycle $v_1v_2\ldots v_kv_1$ such that every edge in this cycle belongs to some shortest path. Suppose $v_1v_2$ belongs to the shortest path $1\ldots u_1v_1v_2u_2\ldots N$ and $v_2v_3$ belongs to the shortest path $1\ldots u_3v_2v_3u_4\ldots N$, then the weight of the path $v_2v_3u_4\ldots N$ is no greater than that of the path $v_2u_2\ldots N$1. Hence, $1\ldots u_1v_1v_2v_3u_4\ldots N$ is another shortest path.

Repeating similar argument for the edges $v_3v_4,\ldots,v_kv_1$, we can get a shortest path $1\ldots u_1v_1v_2\ldots v_kv_1u_{2k}\ldots N$. This is impossible because $1\ldots u_1v_1u_{2k}\ldots N$ is obviously shorter.


1 Otherwise the weight of the path $1\ldots u_3v_2v_3u_4\ldots N$ is greater than that of the walk $1\ldots u_3v_2u_2\ldots N$, which contradicts to the assumption that $1\ldots u_3v_2v_3u_4\ldots N$ is a shortest path.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The claim you are trying to prove is not true. Consider a graph that contains a cycle consisting solely of edges of weight 0, where the cycle is reachable from 1 and can reach N.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ All edges have weight positive number, I forgot to mention that $\endgroup$ – someone12321 Mar 17 at 8:03

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.