All algorithms are in pseudocode

Shortest path in a weighted graph. 2.1 (5p) Give an explanation of why Dijkstra greedy algorithm doesn't work for graphs that have negative weights. Assume there are NO negative cycles. 2.2 (5p) Give an example of a graph with negative weights (but NO neg- ative cycles) where Dijkstra doesn't nd the shortest path. Trace the algorithm on your example and show which path is not the minimum path. 2.3 (5p) Show (by tracing) that the Bellman-Ford algorithm works for your example.