Transcript PPT printable - Simpson College

Mark Allen Weiss: Data Structures and Algorithm Analysis in Java
Chapter 9: Graphs
Shortest Paths
Lydia Sinapova, Simpson College
Shortest Paths
 Shortest Paths in Unweighted
Graphs
 Shortest Paths in Weighted
Graphs - Dijkstra’s Algorithm
 Animation
2
Unweighted Directed Graphs
V1
V3
V2
V4
V6
V5
V7
What is the shortest path from V3 to V5?
3
Problem Data
The problem: Given a source vertex s, find the
shortest path to all other vertices.
Data structures needed:
Graph representation:
Adjacency lists / adjacency matrix
Distance table:
distances from source vertex
paths from source vertex
4
Example
Let s = V3, stored in a queue
Adjacency lists :
Initialized distance table:
distance parent
V1: V2, V4
V1
-1
-1
V2: V4, V5
V2
-1
-1
V3: V1, V6
V3
0
0
V4: V3, V5, V6, V7
V4
-1
-1
V5: V7
V5
-1
-1
V6: -
V6
-1
-1
V7: V6
V7
-1
-1
5
Breadth-first search in graphs
Take a vertex and examine all
adjacent vertices.
Do the same with each of the
adjacent vertices .
6
Algorithm
1. Store s in a queue, and initialize
distance = 0 in the Distance Table
2. While there are vertices in the queue:
Read a vertex v from the queue
For all adjacent vertices w :
If distance = -1 (not computed)
Distance = (distance to v) + 1
Parent = v
Append w to the queue
7
Complexity
Matrix representation: O(|V|2)
Adjacency lists - O(|E| + |V|)
We examine all edges (O(|E|)),
and we store in the queue each
vertex only once (O(|V|)).
8
Weighted Directed Graphs
V1
V3
V2
V4
V6
V5
V7
What is the shortest distance from V3 to V7?
9
Comparison
Similar to the algorithm for unweighted graphs
Differences:
- weights are included in the graph representation
- priority queue : the node with the smallest
distance is chosen for processing
- distance is not any more the number of edges,
instead it is the sum of weights
- Distance table is updated if newly computed
distance is smaller.
10
Algorithm
1. Store s in a priority queue with distance = 0
2. While there are vertices in the queue
DeleteMin a vertex v from the queue
For all adjacent vertices w:
Compute new distance
Store in / update Distance table
Insert/update in priority queue
11
Processing Adjacent Nodes
For all adjacent vertices w:
Compute new distance = (distance to v) + (d(v,w))
If distance = -1 (not computed)
store new distance in table
path = v
Insert w in priority queue
If old distance > new distance
Update old_distance = new_distance
Update path = v
Update priority in priority queue
12
Complexity
O(E logV + V logV) = O((E + V) log(V))
Each vertex is stored only once in the queue – O(V)
DeleteMin operation is :
O( V logV )
Updating the priority queue –
search and inseart:
performed at most for each edge:
O(log V)
O(E logV)
13
Historical Notes
Invented by Edsger Dijkstra in 1955
http://www.cs.utexas.edu/users/EWD/
14