Introduction to Algorithms and Data Structures, Fall 2005, Episode 11

Lecture, November 16

Subject: Single-source shortest paths in weighted graphs. The Bellman-Ford algorithm. Shortest paths in DAGs. Dijkstra's algorithm.

Text: CLRS 24.0-24.3.

Prerequisites : Directed and undirected graphs. Paths in graphs. Topological sorting. Priority queuees.

Time : Wednesday, November 16, 9:00–12:00 (3×45min), Room 4A14

Tutorial : 13:00–16:00 (3×45min), Room 2A14

No hand-ins on this weeks material.

CLRS exercise 24.1-3, p. 591
CLRS exercises 24.3-1, 24.3-2, 24.3-3 p. 600.
Self study: Now almost all old exam questions are relevant. For this weeks material exam questions on graphs are the most relevant, e.g. E2004 Problem 4, F2003 Problem 3, E2002 Problem 2, and E2000 Problem 2..