Announcements
Announcements
Homework 1 Due today
No class/discussion/OH on Monday
Exam 1 Next Friday
3 Questions in 1 hour
During class time unless you cannot make it
Cover Chapter 3 + BFS
Using gradescope time limited submission
Exam instructions assignment
Paths in Graphs (Ch 4)
Breadth First Search
Dijkstra
Priority Queues
Bellman-Ford
Shortest Paths in DAGs
Motivation
DFS/explore allow us to determine if it is possible to get from one vertex to another, and using the DFS tree, you can also find a path. But this often is not an efficient path.
s
t
Goal
Problem: Given a graph G with two vertices s and t in the same connected component, find the best path from s to t.
What do we mean by best?
Least expensive
Best scenery
Shortest
For now: fewest edges
Example
s
t
4 edges
2 edges
1 edge
Best is 1 edge.
Question: Shortest Path Length
What is the shortest path length from s to t in the graph below?
1
2
3
4
5
s
t
How do you know?
It is not hard to convince yourself that the shortest s-t path below has 3 edges, but how do we know there is nothing better?
s
t
Observation
If there is a length ≤d s-v path, then there is some w adjacent to v with a length ≤(d-1) s-w path.
Proof: w is the next to last vertex on the path.
This means that if we know all of the vertices at distance ≤(d-1), we can find all of the vertices at distance ≤d.
Example
0
1
2
3
s
t
Algorithm Idea
For each d create a list of all vertices at distance d from s.
For d=0, this list is just {s}.
For larger d, we want all new vertices adjacent to vertices at distance d-1.
ShortestPaths(G,s)
For v ∈ V, dist(v) ← ∞
A[0] ← {s}
dist(s) ← 0
For d = 0 to n
For u ∈ A[d]
For (u,v) ∈ E
If dist(v) undefined
dist(v) ← d+1
add v to A[d+1]
Initialize Array A
If dist(v) = ∞
What if dist(v) undefined at end?
Algorithm goes through A[0], A[1],… in order. Can just use a queue.
Initialize Queue Q
Q.enqueue(s)
u ← front(Q)
Q.enqueue(v)
Keep track of paths
v.prev ← u
BreadthFirstSearch(G,s)
While Q not empty
dist(v) ← dist(u)+1
Runtime
BFS(G,s)
For v ∈ V, dist(v) ← ∞
Initialize Queue Q
Q.enqueue(s)
dist(s) ← 0
While(Q nonempty)
u ← front(Q)
For (u,v) ∈ E
If dist(v) = ∞
dist(v) ← dist(u)+1
Q.enqueue(v)
v.prev ← u
O(|V|)
O(|V|) iterations
O(|E|) total iterations
Total runtime:
O(|V|+|E|)
DFS vs BFS
Processed vertices (visited, dist < ∞)
For each vertex, process all unprocessed neighbors
Difference:
DFS uses a stack to store vertices waiting to be processed
BFS uses a queue
Big effect
DFS goes depth first – very long path
BFS is breadth first – visits all side paths
DFS vs BFS vs Others?
https://xkcd.com/2407/
Edge Lengths
The number of edges in a path is not always the right measure of distance. Sometimes, taking several shorter steps is preferable to taking a few longer ones.
We assign each edge (u,v) a non-negative length ℓ(u,v). The length of a path is the sum of the lengths of its edges.
Problem: Shortest Paths
Problem: Given a Graph G with vertices s and t and a length function ℓ, find the shortest path from s to t.
Question: Shortest Path
What is the length of the shortest s-t path below?
5
6
7
8
9
1
1
1
2
3
4
4
4
5
5
1+2+1+3 = 7
s
t