Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

Question

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.

Answer 1

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

---

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

Answer 2

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.