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

Answer:

Both algorithms are guaranteed to produce the same shortestpath weight, but if there are multiple shortest paths, Dijkstra’s will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.No. There exists a zero-weight cycle, then it is possible that relaxing an edge will mess up parent pointers so that it is impossible to recreate a path back to the source node. The easiest example is if we had a vertex v that had a zero-weight edge pointing back to itself. If we relax that edge, v’s parent pointer will point back to itself. When we try to recreate a path from some vertex back to the source, if we go through v, we will be stuck there.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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