Problem 3 This problem explores why Dijkstra\'s shortest-path algorithm only wor

Question

Problem 3 This problem explores why Dijkstra's shortest-path algorithm only works when all edge weights are non-negative. Consider the following graph 4 -3 2 Now consider running Dijkstra's algorithm on the graph with A as the source node a. List the 4 vertices A, B, C, D in the order in which they would be extracted from the heap in our min-heap priority queue implementation of Dijkstra's algorithm, as well as the shortest-path value stored with each vertex at the time of its extraction First vertex Second vertex Third vertex: Fourth vertex: Shortest-path val Shortest-path val: Shortest-path val Shortest-path val c. Assume our implementation does not check whether the successor endpoint of a vertex has already been removed from the heap during a relaxation step, and that it performs the relaxation step for each vertex removed from the heap When vertex B is extracted from the heap, its outgoing edges will be considered for relaxation During the relaxation test of edge B -C, what numerical value will be tested as a candidate shortest-path value against vertex C's stored shortest-path value? d. In light of your answers to part (a), why is your answer to part (c) problematic? The existence of this problem is the reason Dijkstra's algorithm only works on graphs with non-negative-weight edges e. Suppose the weight of edge A-»C is some real-valued variable x rather than 2. State the largest possible range of x-values that will cause Dijkstra's algorithm to return an incorrect answer (example answer format: 1 s x

Explanation / Answer

Solution:

a)

FIrst vertex: A, Shortest path val: 0

Second Vertex: C Shortest path val: 2

Third vertex: B Shortest path val: 4

Fourth Vertex: D: Shortest path val: 3

c)

The valu of distance 2 from A to C will be considered, which will be updated after relaxation and changed to 1

so is the distance to D is going to change which will now be 2.

d)

Since the Dijkstra's algorithm is a greedy approach which doesn't consider the relaxation steps that is why it is problematic in part c.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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