Search for all shortest paths from a source to all vertices in a digraph

Question

We are given an oriented graph G (possibly with cycles) with positive edge weights, as well as the minimum distance D[v]to each vertex vfrom the source s (D is an array in this way). The problem is to find an array of N[v] = numberpaths of length D[v]from s to v, in linear time.

Now this is a domestic problem that I struggled with for a long time. I worked on the following thought: I am trying to remove loops by selecting a suitable acyclic subgraph G, and then trying to find short paths from s to v in the subgraph.

But I can’t determine exactly what to do, so I will be grateful for any help, as in the qualitative idea of ​​what to do.

Answer 1

You can use dynamic programming and fill in the number of paths along the way, if D[u] + w(u,v) = D[v], something like:

N = [0,...,0]
N[s] = 1 //empty path
For each vertex v, in *ascending* order of `D[v]`:
   for each edge (u,v) such that D[u] < D[v]:
       if D[u] + w(u,v) = D[v]: //just found new shortest paths, using (u,v)!
           N[v] += N[u]

Difficulty O(VlogV + E), assuming the graph is not sparse, O(E)is dominant.

---

Explanation:

v0->v1->...->v_(k-1)->v_k v0 v_k, v0->...->v_(k-1) v0 v_k-1, - v_k - N[v_(k-1)] (, D[V_k-1] < D[v_k], D[v]).
v0->...->v_(k-1) N[v_(k-1)]. v0->...->v_(k-1)-v_k - D[v_(k-1)] + w(v_k-1,v_k) = D[v_k] - , , N[v_k].

, , .