Greedy Algorithms: Dijkstra’s Algorithm

• Read section 9.3 (pages 333-337)
• What problem does Dijkstra’s algorithm?
  • What information does it need to maintain?
  • How does it update this information?
  • What other data structure is needed in Dijkstra’s algorithm?
• Describe how Dijkstra’s algorithm operates.
• In what sense is Dijkstra’s algorithm a greedy algorithm?
• Write pseudocode for Dijkstra’s algorithm.
• Why is it important for Dijkstra’s algorithm that all edge weights are non-negative?
• Possibly: Talk about Fibonacci heaps
• Practice problems: 9.3.1, 9.3.2, 9.3.3, 9.3.4