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?

closed as off-topic by Jeffε, Hsien-Chih Chang 張顯之, R B, David Eppstein, KavehJul 14 '14 at 8:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jeffε, Hsien-Chih Chang 張顯之, R B, David Eppstein, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

• @R B is that the worst case running time? Can you also please tell me the source of what you state? – Francesco Riccio Jul 12 '14 at 10:04
• This can easily be solved in $O(VE)$ with dynamic programming. – R B Jul 12 '14 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. – Klaus Draeger Jul 13 '14 at 0:53
• @KlausDraeger, Yes you are right. – Saeed Jul 13 '14 at 1:13

Iterate DAG-Shortest-Paths (in Cormen, Lesierson, Rivest, and Stein's text "Introduction to Algorithms").

• Such algorithm would have teta (|V|^3) running time in the worst case, not better than Floyd-Warshall and Johnson. – Francesco Riccio Jul 13 '14 at 14:48
• Why do you say that? DAG-shortest paths runs in V+E, due to the topological sort that does not necessarily have to be repeated. – Ari Trachtenberg Jul 13 '14 at 14:52
• Do you know a mechanism to determine which vertices and in which order to give in input to DAG-shortest-paths? – Francesco Riccio Jul 13 '14 at 16:36
• Any order at all. – Jeffε Jul 13 '14 at 18:18