CODEWITHSUNDEEP
algorithmgraph-algorithmshortest-pathdirected-graph
Urysohn Lemma
Urysohn Lemma

Reputation: 141

Finding all shortest paths from source to all vertices in a digraph

We are given a directed graph G (possibly with cycles) with positive edge weights, and the minimum distance D[v] to every vertex v from a source s is also given (D is an array this way). The problem is to find the array N[v] = number of paths of length D[v] from s to v, in linear time.

Now this is a homework problem that I've been struggling with for quite long. I was working along the following thought : I'm trying to remove the cycles by suitably choosing an acyclic subgraph of G, and then try to find shortest paths from s to v in the subgraph.

But I cannot figure out explicitly what to do, so I'd appreciate any help, as in a qualitative idea on what to do.

Upvotes: 4

Views: 782

Answers (1)

amit
amit

Reputation: 178471

You can use dynamic programming approach in here, and fill up the number of paths as you go, 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]

Complexity is O(VlogV + E), assuming the graph is not sparsed, O(E) is dominanting.

Explanation:

If there is a shortest path v0->v1->...->v_(k-1)->v_k from v0 to v_k, then v0->...->v_(k-1) is a shortest path from v0 to v_k-1, thus - when iterating v_k - N[v_(k-1)] was already computed fully (remember, all edges have positive weights, and D[V_k-1] < D[v_k], and we are iterating by increasing value of D[v]).
Therefor, the path v0->...->v_(k-1) is counted in the number N[V_(k-1)] at this point.
Since v0->...->v_(k-1)-v_k is a shortest path - it means D[v_(k-1)] + w(v_k-1,v_k) = D[v_k] - thus the condition will hold, and we will add the count of this path to N[v_k].

Note that the proof for this algorithm will basically be induction that will follow the guidelines from this explanation more formally.

Upvotes: 3

Related Questions