Introduction
Syllabus
Guidelines for labs
Lab sections
Take quiz & check grades
 
Single Source Shortest Paths
Chapter 25
Given a graph and a source vertex "s", compute
the shortest route to each of all other vertices.
The graph is weighted, directed or undirected.
Examples:
 compute least cost travel itinerary 
 compute fastest itinerary 
 compute shortest path 
Variants of the problem:
 single destination (as opposed to single source) 
 Single pair  compute shortest path to a given vertex 
 All pairs 
Properties and Theorems
Relaxation
Dijkstra's algorithm
