Prove or disprove by counterexample:
In a weighted acyclic digraph (D= (V,E), w) where all weights are positive, for every vertex $s \in V$ the tree of shortest paths from a s to all vertices reachable from s is uniquely determined.
Solution
I am trying to prove the statement and I tried by contradiction. Assume that the tree of shortest paths from s in a directed, weighted acyclic graph is not uniquely determined. Assume that there are two such tree say $T$ and $T'$. Which means that there exist a vertex in a graph, say $v \in V$ such that the shortest path in $T$ differ from the shortest path in $T'$. Which means there are two shortest paths, say $P$ and $P'$ in our directed acyclic graph with positive weights from s to v.
I don't know how to proceed next, I even tried to go "back" and look on neighbours going into $v$ but couldn't find a contradiction… maybe because there is no and there exist a counter example?
Question Please help me to find out if it's statement I need to prove or to find counter example, if I need to find counter example I will try to figure it out, if I have to prove it please give me a hint where is the contradiction.
Best Answer
You've done a good job analyzing the situation. There is nothing stopping an acyclic digraph from having two different directed paths between two vertices -- that causes a cycle in the underlying undirected graph, but you're fine as long as there is no directed cycle. All you need is a case where the weights of those two directed paths are the same and you have found a counterexample. It can even be as simple as this: