Shortest Paths (20)
Michael L. Littman
November 10th, 1998
ANNOUNCEMENTS
MST WRAP UP
Review
Correctness Analysis
Running Time Analysis
SHORTEST PATH PROBLEM
Route Finding
Single-Source Shortest-Path Problem
Variations
Some Properties of Shortest Paths
Optimal Substructure Property
Shortest Path Tree
DIJKSTRA'S ALGORITHM
Idea
Bookkeeping
Initialization and Improvement
Algorithm
Connection to Prim's
Correctness
Running Time
A
*
Obvious Waste
Admissible Heuristic
Important Properties
Observations
New Algorithm
Basic Concepts
Running Time and Heuristic Quality
Running Time
Generating Heuristics
Varying Quality
Next:
ANNOUNCEMENTS
