An exercise I'm working on asks me to devise an $O(m)$ algorithm for the all-pairs shortest paths of the graph $G = (V, A)$, where $(v_i, v_j) \in A$ implies $i < j$.
I'm wondering whether this is at all possible, since so far I've not been able to come up with any suitable $O(m)$ algorithm and an internet search has come up short as well..
I think that you have to cycle through every edge $(v_i, v_j)$, but then (if we call $u_{ij}$ the shortest distance between $v_i$ and $v_j$) you have to calculate $u_{kj} = \min\{ u_{kj}, u_{ki} + l_{ij} \}$ for every $k = \{ 1, 2, ..., j - 1 \}$, every time. Clearly this is not an $O(m)$ algorithm (I think it is an $O(1/2(m - 1)m)$ algorithm).
If this would be a shortest path problem, where only $u_{1j}$ has to be determined, this could be done in $O(m)$ steps, using the method described above I think.
Thank you for any help you can provide!