<p>Iterate DAG-Shortest-Paths (in Cormen, Lesierson, Rivest, and Stein's text <a href="http://mitpress.mit.edu/books/introduction-algorithms" rel="nofollow">"Introduction to Algorithms"</a>).</p>

CC BY-SA 3.0
2014-07-13T14:48:22.073Z
Such algorithm would have teta (|V|^3) running time in the worst case, not better than Floyd-Warshall and Johnson.
Francesco Riccio
CC BY-SA 3.0
2014-07-13T14:52:41.180Z
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
CC BY-SA 3.0
2014-07-13T16:36:04.080Z
Do you know a mechanism to determine which vertices and in which order to give in input to DAG-shortest-paths?
Francesco Riccio
CC BY-SA 3.0
2014-07-13T18:18:02.917Z
Any order at all.
Jeffε
CC BY-SA 3.0
2014-07-13T14:20:46.617Z
2014-07-13T14:20:46.617Z
Ari Trachtenberg
<p>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?</p>

CC BY-SA 3.0
2014-07-12T10:04:43.373Z
@R B is that the worst case running time? Can you also please tell me the source of what you state?
Francesco Riccio
CC BY-SA 3.0
2014-07-12T10:06:19.453Z
This can easily be solved in $O(VE)$ with dynamic programming.
R B
CC BY-SA 3.0
2014-07-13T00:53:04.247Z
@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
CC BY-SA 3.0
2014-07-13T01:13:35.910Z
@KlausDraeger, Yes you are right.
Saeed
<graph-algorithms><directed-acyclic-graph><topological-graph-theory>
All pairs shortest paths in a DAG
Francesco Riccio
# All pairs shortest paths in a DAG

(Asked by: username_0 on 2014-07-12)

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?

**Tags:** graph-algorithms, directed-acyclic-graph, topological-graph-theory

> **Comments:**
> **username_0**: @username_1 is that the worst case running time? Can you also please tell me the source of what you state?  
> **username_1**: This can easily be solved in $O(VE)$ with dynamic programming.  
> **username_2**: @username_3: 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.  
> **username_3**: @KlausDraeger, Yes you are right.  

---

## 1 answers

### Answer by username_4 on 2014-07-13. Score: 1

Iterate DAG-Shortest-Paths (in Cormen, Lesierson, Rivest, and Stein's text ["Introduction to Algorithms"](http://mitpress.mit.edu/books/introduction-algorithms)).

> **Comments:**
> **username_0**: Such algorithm would have teta (|V|^3) running time in the worst case, not better than Floyd-Warshall and Johnson.  
> **username_4**: 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.  
> **username_0**: Do you know a mechanism to determine which vertices and in which order to give in input to DAG-shortest-paths?  
> **username_5**: Any order at all.  

---

