CODEWITHSUNDEEP
algorithmdepth-first-searchbreadth-first-search
Jmrapp
Jmrapp

Reputation: 520

BFS Modification For Total Shortest Paths

I was given the following problem as an assignment but it is really confusing me:

Consider the BFS algorithm. Given a digraph G = (V, E) and a starting vertex s ∈ V, this algorithm computes for each vertex u ∈ V the value d[u], which is the length (number of edges) on the shortest path from s to u. The objective of this problem is to modify the BFS algorithm of class to compute the number of shortest paths from s to each vertex of G.

This can be done in two steps:

(a) First run the standard BFS on G, starting from s. Explain how to use the result of this BFS to produce a new digraph G2 = (V 2,E2), where V 2 ⊆ V and E2 ⊆ E, such that every path in G2 that starts at s, is a shortest path in G starting from s, and conversely, every shortest path in G starting from s is a path in G2.

(b) Explain how to take the result of part (a) to compute for each vertex u ∈ V , a quantity n[u], which is the number of paths in G2 from s to u. (Hint: This can be done by a modification of BFS.) Both of your algorithms should run in O(V + E) time.

For part a I am not quite sure how to use the results from the BFS to produce a new digraph. I don't understand how/in what way it should be formed. Do I use the nodes that were visited to form a new graph? All nodes are visited when doing a BFS, how am I supposed to form a different graph.

Upvotes: 3

Views: 771

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10565

The question (a) can be solved by running the BFS normally, but for every edge (u, v) you find while doing it, if shortest-path(u)+1 <= shortest-path(v) (no matter if v was already visited) then (u, v) is a directed edge in G2.

Also, while doing it, to solve (b) you should increase n[v] += n[u]. In the beginning, n[u] = 0 for everyone except s, where n[s] = 1.

Here is an example Python implementation:

from collections import deque

def bfs(G, s):
    shortest = [float('+Inf')]*len(G)
    count = [0]*len(G)

    shortest[s] = 0
    count[s] = 1

    Q = deque([s])

    while Q:
        u = Q.popleft()
        for v in G[u]:
            if not count[v]: 
                Q.append(v)

            if shortest[u]+1 <= shortest[v]:
                shortest[v] = shortest[u]+1
                count[v] += count[u]
    return count

G = [
    [1, 2, 3],
    [4],
    [4],
    [4],
    []
]

print bfs(G, 0)

Upvotes: 1

Related Questions