(15p) 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 negative cycles) where Dijkstra doesn't find 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.