Question

Examining Dijsktra's Algorithm [10 MARKS]

Suppose we (1) have a directed graph as, and (2) allow negative weights of edges in the input to Dijsktra's
algorithm.
• Demonstrate a graph with these two properties, such as Dijkstra's algorithm from class returns an incorrect
output. Explain what the correct output is, what output Dijkstra's algorithm produces, and why.
Which of the above two properties causes the algorithm to fail?
1. Show exactly where our proof of correctness of Dijkstra's algorithm fails if we allow the property

Answer 1

Dijkstra's Algorithm fails with negative edge weights, as demonstrated with a graph where the algorithm returns an incorrect shortest path due to a negative weight reducing the path length of previously determined paths.

Step-by-step explanation:

When examining Dijkstra's Algorithm with a directed graph that has negative edge weights, the algorithm can produce incorrect results. Consider a graph with three nodes A, B, and C, where the edges are A -> B with a weight of 1, B -> C with a weight of -2, and A -> C with a weight of 4. If we run Dijkstra's algorithm starting from A, it will first choose the edge A -> B since it has the smallest weight. Then, it would choose A -> C as the next smallest weight, concluding the shortest path to C is of length 4. However, the correct shortest path is A -> B -> C with a total weight of -1 (1 - 2).

The proof of correctness for Dijkstra's algorithm relies on the assumption that once a node's shortest path is determined, it cannot change. However, when negative weights are introduced, this assumption fails because encountering a negative weight in subsequent steps can reduce the shortest path length of previously determined paths.

The property causing this failure is the allowance of negative edge weights in the graph, which is contrary to the conditions needed for Dijkstra's algorithm to function correctly.