# All pairs shortest paths in a DAG [closed]

I have studied the Floyd-Warshall and Johnson algorithms. I am trying to understand if the all pairs shortest paths research in a directed graph G can be implemented in a more efficient way if I already know that G is acyclic. Do you have any ideas?

• @R B is that the worst case running time? Can you also please tell me the source of what you state? Jul 12, 2014 at 10:04
• This can easily be solved in $O(VE)$ with dynamic programming.
– R B
Jul 12, 2014 at 10:06
• @Saeed: That won't work. Consider the case $V=\{v_0,v_1,v_2\}$ and $E=\{(v_0,v_1),(v_0,v_2),(v_1,v_2)\}$. Then $v_0$ is a source, and $d_1=d_2=1$, so $d_{1,2}=\infty$ (rather than $1$) according to your algorithm. Jul 13, 2014 at 0:53
• @KlausDraeger, Yes you are right. Jul 13, 2014 at 1:13