# Shortest paths in $k$-partite DAG

Let

• $$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.

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$$.
• 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}\}$$.
• 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)$.) Commented Mar 20 at 19:06