There is an alternative way of implementing Dijkstra’s algorithm that avoids use

Question

There is an alternative way of implementing Dijkstra’s algorithm that avoids use of the locator pattern but increases the space used for the priority queue, Q, from O(n) to O(m) for a weighted graph, G, with n vertices and m edges. The main idea of this approach is simply to insert a new key-value pair, (D[v], v), each time the D[v] value for a vertex, v, changes, without ever removing the old key-value pair for v. This approach still works, even with multiple copies of each vertex being stored in Q, since the first copy of a vertex that is removed from Q is the copy with the smallest key. Describe the other changes that would be needed to the description of Dijsktra’s algorithm for this approach to work.

Explanation / Answer

It is necessary in this changed implementation to check if the inserting vertex already exists in the new key value pair because this will increase the duplicity in the new graph and more than one path will then exists in the case when duplicity exists in the graph.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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