-1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Jeffε, Hsien-Chih Chang 張顯之, R B, David Eppstein, Kaveh Jul 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.

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

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

$\endgroup$
  • $\begingroup$ Such algorithm would have teta (|V|^3) running time in the worst case, not better than Floyd-Warshall and Johnson. $\endgroup$ – Francesco Riccio Jul 13 '14 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$ – Ari Trachtenberg Jul 13 '14 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$ – Francesco Riccio Jul 13 '14 at 16:36
  • 3
    $\begingroup$ Any order at all. $\endgroup$ – Jeffε Jul 13 '14 at 18:18

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