Shortest Path

Reading

• Shortest path problem.
• Dijkstra's algorithm.
• A* search algorithm.

Exercise

• Source codes.
• Unit tests.

Quiz

• Prove the soundness of Dijkstra's algorithm using induction.
• Write a report that includes your proof and save it as quiz9.pdf. Submit your report to https://canvas.emory.edu/courses/32845/assignments/93013

Proof by Induction

• Let S be the set of all vertices on the shortest path found by Dijkstra’s algorithm.
• Prove that the distances[u] is the minimum length between the vertex u and the target vertex t.
• Base case
• When |S| = 1, it is true.
• Induction case
• Assume that it is true for |S| = k > 1.
• Fill the rest!