Outline

• Distance in graphs
  definitions of ordinary distance and weighted distance (when edges have lengths), triangle inequality, radius and diameter
  
• All-pairs distances
  computation of the distances between all pairs of vertices - dynamic Floyd-Warshall algorithm, its proof
• Single-source shortest path
  Dijkstra's algorithm (a variant of graph searching, Lecture 2), its proof, and an outline of the A* algorithm which enriches Dijkstra

Goals

Students should understand the concept of distance in graphs (also in the weighted variant), and be able to compute the distance between two vertices. The main goal is to show the beautiful and educational Floyd-Warshall and Dijkstra's algorithms. These algorithms not only solve the mentioned shortest path problems, but each one also illustrates some very powerful algorithm design concepts which students will find useful in other areas of CS. 

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

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

On the other hand, the algorithmic part of this lecture - finding shortest paths (Floyd-Warshall and Dijkstra), is not covered by the 2008 English edition of the book, and we refer to some great online resources below. (The 2010 new Czech edition already includes a dedicated section on Dijkstra's algorithm.)

IS Questionaries