Shortest paths in $k$-partite DAG

Question

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.

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}\}$.