Transcript Unweighted Shortest Path Neil Tang 4/1/2010

Unweighted Shortest Path
Neil Tang
3/11/2010
CS223 Advanced Data Structures and Algorithms
1
Class Overview
 The unweighted shortest path problem
 Breadth First Search (BFS)
 The algorithms
 Time complexity
CS223 Advanced Data Structures and Algorithms
2
Unweighted Shortest Path Problem
 The unweighted shortest path problem: Given an
unweighted graph G and a source vertex s, find a path from
s to every other vertex in G with a minimum number of
edges.
CS223 Advanced Data Structures and Algorithms
3
BFS
CS223 Advanced Data Structures and Algorithms
4
An Algorithm
Time complexity: O(|V|2)
CS223 Advanced Data Structures and Algorithms
5
Time Complexity
 A bad case
 More efficient implementation: Use a queue
 Time complexity of a queue-based implementation:
O(|V|+|E|)
CS223 Advanced Data Structures and Algorithms
6