University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

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:

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

Relaxation

Dijkstra's algorithm