University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000



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.


bulletcompute least cost travel itinerary
bulletcompute fastest itinerary
bulletcompute shortest path

Variants of the problem:

bulletsingle destination (as opposed to single source)
bulletSingle pair - compute shortest path to a given vertex
bulletAll pairs

Properties and Theorems


Dijkstra's algorithm