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