Shortest paths are not always unique: sometimes there are two or more different

Question

Shortest paths are not always unique: sometimes there are two or more different paths between two vertices, with the minimum possible length. Now consider the following problem. A directed, edge-weighted graph G = (V, E), a source vertex s V. A Boolean array usp[ ] such that for each vertex u V, the entry usp[u] is True if and only if there is unique shortest path from s to u. For the following directed, edge-weighted graph and given source vertex s, write down the values in the array usp given a directed graph with n vertices and m edges, describe an algorithm that solves the above problem in O((m + n) log n) time.

Explanation / Answer

s a b c d

0 - - - -

1st step-> get the values of all the branches from s.

0 5 3 - -

the minimum value here is 3, therefore check for any branches from b.

s a b c d

0 5 3 7 4 (the value of c/d= source weight to b + weight of edge from b to c/d)

Dijkstra's Algo:

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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