• $D(V, A)$ be a $k$-partite DAG;
  • $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ be the set of partitions;
  • $A = \{ (i, j) : \forall_{1 \leqslant k \leqslant |P| - 1} (i \in p_k \wedge j \in p_{k + 1}) \}$ be the set of arcs; And
  • $d_{ij}$ be the distance of arc $(i, j) \in A$.

For instance, consider the following DAG example.


We aim to calculate the shortest paths length $l_{ij}$, $\forall i, j \in V$. For this purpose, straightforwardly, we could take the Floyd & Warshall algorithm, consuming $\mathcal{O}(|V|^3)$. But, I am looking for better ways of doing this, since the general Floyd & Warshall simply does not consider the specificities of the input graph.

Thanks and regards.


1 Answer 1


If $|p_k|\leqslant N$ for all $k\in \{1, …, |P|\}$, then a dynamic programming algorithm can compute all those distance in $\mathcal{O}(|V|^2\times N)$ which could be lesser than $|V|^3$.

The idea is the following:

  • if $i\in p_k$ and $j \in p_{k+1}$ for some $k$, $\ell_{ij} = d_{ij}$ (or $\infty$ if there is no edge between $i$ and $j$);
  • if $i \in p_k$ and $j\in p_{k'}$, $k'>k+1$, then $\ell_{ij} = \min\limits_{v\in p_{k'-1}}\{\ell_{iv} + d_{vj}\}$.
  • $\begingroup$ Thank you so much. $\endgroup$ Commented Mar 18 at 9:58
  • 1
    $\begingroup$ Doesn't the better bound $|V|\times |E|$ hold? For any given source $i$, just calculate shortest paths from $i$ to all $j$. In a (connected) DAG this takes time $O(|V| + |E|)) = O(|E|)$ per $i$ using the standard linear-time algorithm and recurrence. (Comparing to your bound: each vertex has degree at most $2 N$, so this bound $|V|\times |E|$ is always no worse than $O(|V|^2 N)$.) $\endgroup$
    – Neal Young
    Commented Mar 20 at 19:06
  • $\begingroup$ @NealYoung, thank you so much for the enhancement. $\endgroup$ Commented Mar 21 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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