Consider undirected graphs (with no weights). Often there are multiple shortest

Question

Consider undirected graphs (with no weights). Often there are multiple shortest paths between two nodes of a graph. For example, in a graph with vertices {1, 2, 3, 4, 5} and edges {(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)}, there are two shortest paths from 1 to 5: (1, 2, 4, 5), and (1, 3, 4, 5). Describe a linear-time algorithm such that, given an undirected, unweighted graph and two vertices u and v, the algorithm counts the number of distinct shortest paths from u to v. Justify its correctness and the running time.

Explanation / Answer

Starting from u run breadth first traversal algorithm as follows:

assign distance 0 to node u, and in breadth first traversal assign distance to each node with level

of that node while exploring that node. i.e. all adjacent s of u are at level 1 , so distance 1 is assigned and level 2 nodes with distance 2. When we reach at node v count number of nodes

in previous level those are adjacent to v and output that number.

Correctness: Let the minimum distance from u to v is k. As breadth first traversal explores nodes level by level, so in first iteration it finds all nodes at distance 1 from u, in general at ith

iteration it finds all nodes at distance i from u. Thus at kth iteration v node will de explored and we correctly count number of nodes in (k-1) level that are adjecent to v. So this algorithm gives correct minimum distance from u to v.

Running time:We know running time of breadth first traversal is O(|V|+|E|), so this algorithm also takes O(|V|+|E|) time.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.