Outline

• Distance in graphs
  ordinary (unit) distance, definition and properties, triangle inequality, BFS
• Weighted distance in digraphs
  negative or positive weights, Bellman-Ford algorithm, negative cycles
• Finding shortest paths
  Dijkstra's algorithm (for positive lengths), bidirectional Dijkstra, Floyd-Warshall dynamic algorithm
• ~optional~  Some (slightly) advanced ideas
  practical path finding in huge graph: A* search, reach, and combinations

Goals

Students should understand the concept of distance in graphs and digraphs (both in the unit and weighted variants), and be able to work with the distance between graph vertices. The main part is to show and prove several beautiful and educational algorithms; Bellman-Ford, Floyd-Warshall and Dijkstra. These algorithms not only belong to a basic algorithmic toolbox of CS students, but they are very interesting from the graph-theoretical points of view, too.

Study materials

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Finish studying the whole Section 4.2 (distances in graphs).

Algorithmic aspects, which form majority of our lecture, are not much covered in this book. (The 2010 new Czech edition already includes a dedicated section on Dijkstra's algorithm.)

Algorithmic aspects of the lecture

The presented algorithmic part of Lecture 3 - path finding (route planning), is not primarily covered by the course books, and we instead refer to some great online resources below.

Interactive tutorials

IS Questionnaires