In cases where there are several different shortest paths between two nodes, the

Question

In cases where there are several different shortest paths between two nodes, the most convenient of these paths is often the one with the fewest number of edges. For instance, if nodes represent cities and edge lengths represent costs of flying between cities, there may be many ways to get from city s to city t all of which have the same cost. The most appealing of these alternatives is the one which involves the fewest stopovers. Accordingly, for a specific starting node s, let best [u] = minimum number of edges in a shortest path from ,s to u. In the example below, the best values for nodes s, a, b, c, d are 0,1,2,1,2 respectively. Given a graph G = (V, E). positive edge weights w(e) for each edge e and a starting node s, Design an efficient algorithm that computes the values of best[u] for all nodes Briefly argue why it is a correct algorithm. What is its running time?

Explanation / Answer

Dijkstra;s Algorithm:

Dijkstra;s is used to calculate the shortest path first. It only gives the optimal solution for any graph with given weights. Dijkstra;s is not only used in Data Structures but olso used in computer networking in routers.

Time Complexity for Dijkstra;s in big O notation is O(ELogV) where, E=number of edges & V= number of vertices

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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