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?

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

1 Answer 1


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

  • $\begingroup$ Such algorithm would have teta (|V|^3) running time in the worst case, not better than Floyd-Warshall and Johnson. $\endgroup$ Jul 13, 2014 at 14:48
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 13, 2014 at 14:52
  • $\begingroup$ Do you know a mechanism to determine which vertices and in which order to give in input to DAG-shortest-paths? $\endgroup$ Jul 13, 2014 at 16:36
  • 3
    $\begingroup$ Any order at all. $\endgroup$
    – Jeffε
    Jul 13, 2014 at 18:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.