Shortest Paths
1
Lecture 24 (Graphs 3)
CS61B, Fall 2023 @ UC Berkeley
Slides credit: Josh Hug
Shortest Paths: Why BFS Doesn't Work
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Graph Problems
Last time, saw two ways to find paths in a graph.
Which is better?
Problem | Problem Description | Solution | Efficiency (adj. list) |
s-t paths | Find a path from s to every reachable vertex. | DepthFirstPaths.java | O(V+E) time Θ(V) space |
s-t shortest paths | Find a shortest path from s to every reachable vertex. | BreadthFirstPaths.java | O(V+E) time Θ(V) space |
BFS vs. DFS for Path Finding
Possible considerations:
BFS vs. DFS for Path Finding
BreadthFirstSearch for Google Maps
As we discussed last time, BFS would not be a good choice for a google maps style navigation application.
Let’s see a quick example.
Breadth First Search for Mapping Applications
Suppose we’re trying to get from s to t.
s
t
Breadth First Search for Mapping Applications
Suppose we’re trying to get from s to t.
s
t
260
70
70
10
70
40
20
15
30
50
Breadth First Search for Mapping Applications
BFS yields the wrong route from s to t.
BFS Result
Correct Result
s
t
260
70
70
10
70
30
40
20
15
50
s
t
260
70
70
10
70
40
20
15
30
50
Goal: The Shortest Paths Tree
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Problem: Single Source Single Target Shortest Paths
Goal: Find the shortest paths from source vertex s to some target vertex t.
Challenge: Try to find the shortest path from town 0 to town 5.
B
C
D
E
F
G
A
s
5
2
1
15
3
2
11
5
1
1
4
1
Problem: Single Source Single Target Shortest Paths
Goal: Find the shortest paths from source vertex s to some target vertex t.
B
C
D
E
F
G
A
s
5
2
1
15
3
2
11
5
1
1
4
1
Best path from 0 to 5 is
The path 0 -> 2 -> 5 only involves three towns, but total length is 16 miles.
Problem: Single Source Single Target Shortest Paths
Goal: Find the shortest paths from source vertex s to some target vertex t.
Observation: Solution will always be a path with no cycles (assuming non-negative weights).
B
C
D
E
F
G
A
s
5
2
1
15
3
2
11
5
1
1
4
1
v distTo[] edgeTo[]
0 0.0 -
1 2.0 0→1
2 - -
3 - -
4 5.0 1→4
5 9.0 4→5
6 - -
Shortest path from s=0 to t=5
Problem: Single Source Shortest Paths
Goal: Find the shortest paths from source vertex s to every other vertex.
Challenge: Try to write out the solution for this graph.
B
C
D
E
F
G
A
s
5
2
1
15
3
2
11
5
1
1
4
1
Problem: Single Source Shortest Paths
Goal: Find the shortest paths from source vertex s to every other vertex.
Observation: Solution will always be a tree.
v distTo[] edgeTo[]
0 0.0 -
1 2.0 0→1
2 1.0 0→1
3 11.0 6→3
4 5.0 1→4
5 9.0 4→5
6 10.0 4→6
B
C
D
E
F
G
A
s
5
2
1
15
3
2
11
5
1
1
4
1
Shortest paths from s=0
SPT Edge Count: yellkey.com/TODO
If G is a connected edge-weighted graph with V vertices and E edges, how many edges are in the Shortest Paths Tree (SPT) of G? [assume every vertex is reachable]
B
C
D
E
F
G
A
s
SPT Edge Count
If G is a connected edge-weighted graph with V vertices and E edges, how many edges are in the Shortest Paths Tree (SPT) of G? [assume every vertex is reachable]
V: 7
Number of edges in SPT is 6
Always V-1:
B
C
D
E
F
G
A
s
Dijkstra's Algorithm: Some Bad Algorithms
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Finding a Shortest Paths Tree (By Hand)
What is the shortest paths tree for the graph below? Note: Source is A.
B
C
A
s
5
5
D
1
2
2
1
Finding a Shortest Paths Tree (By Hand)
What is the shortest paths tree for the graph below?
4
B
C
A
s
5
5
D
1
1
0
2
2
2
1
Creating an Algorithm
Let’s create an algorithm for finding the shortest paths.
Will start with a bad algorithm and then successively improve it.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
Finding a Shortest Paths Tree Algorithmically (Incorrect)
Bad algorithm #1: Perform a depth first search. When you visit v:
dfs(A):
Add A->B to SPT
Add A->C to SPT
dfs(B):
Add B->D to SPT
A already in SPT.
dfs(C):
B already in SPT.
D already in SPT.
7
B
C
A
s
5
5
D
1
1
0
5
3
2
1
B
C
A
s
5
1
D
1
∞
0
∞
∞
3
2
5
5
1
B
C
A
s
5
1
5
D
1
1
0
5
∞
3
2
7
Older slide, used on the web videos.
Finding a Shortest Paths Tree Algorithmically (Incorrect)
Bad algorithm #2: Perform a depth first search. When you visit v:
dfs(A):
A->B is 5, < than ∞
A->C is 1, < than ∞
dfs(B):
B->D is 5 + 2 = 7, better than ∞.
B->A is 5 + 3 = 8, worse than 0.
dfs(C):
C->B is 1 + 1 = 2, better than 5.
C->D is 1 + 5 = 6, better than 7.
B
C
A
s
5
1
D
1
∞
0
∞
∞
3
2
5
We’ll call this process “edge relaxation”.
Improvements:
1
5
B
C
A
s
5
1
5
D
1
1
0
5
∞
3
2
7
7
B
C
A
s
5
5
D
1
1
0
5
3
2
1
2
6
Older slide, used on the web videos.
Finding a Shortest Paths Tree Algorithmically (Incorrect)
Dijkstra’s Algorithm: Perform a best first search (closest first). When you visit v:
A has lowest dist, so dfs(A):
A->B is 5, < than ∞
A->C is 1, < than ∞
C has lowest dist, so dfs(C):
C->B is 1 + 1 = 2, better than 5.
C->D is 1 + 5 = 6, better than ∞.
B has lowest dist, so dfs(B):
B->A is 2 + 3 = 5, worse than 0.
B->D is 2 + 2 = 4, better than 6.
B
C
A
s
5
1
D
1
∞
0
∞
∞
3
2
5
Improvements:
1
5
B
C
A
s
5
1
5
D
1
1
0
5
∞
3
2
2
6
6
B
C
A
s
5
5
D
1
1
0
2
3
2
1
4
Older slide, used on the web videos.
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
Fringe: [A]
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
Fringe: [A]
Removed vertex: A
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
Fringe: [A, B, C]
Removed vertex: A
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
Fringe: [A, B, C]
Removed vertex: B
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
7
The edge B→A is not added to SPT, because A is already part of the SPT.
Fringe: [A, B, C, D]
Removed vertex: B
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
7
Fringe: [A, B, C, D]
Removed vertex: C
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
7
Nothing happens.
C→B not added, B already in SPT.
C→D not added, D already in SPT.�
Fringe: [A, B, C, D]
Removed vertex: C
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
7
Fringe: [A, B, C, D]
Removed vertex: D
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
5
1
7
Fringe: [A, B, C, D]
Removed vertex: D
Nothing happens.
D has no neighbors (there are no edges going out of D).
Bad Algorithm #1 (Inspired by BFS)
Add the start (A) to the fringe.
While fringe is not empty:
Remove a vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Takeaways:
Algorithm #1 (BFS) visits:� every node 1 edge away,�then every node 2 edges away,�then every node 3 edges away, etc.
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
B
C
A
s
D
∞
∞
∞
Order of visited nodes:
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
B
C
A
s
D
∞
0
∞
∞
∞
Order of visited nodes: A
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
1
0
∞
2
2
1
B
C
A
s
D
1
0
∞
∞
∞
Order of visited nodes: AC
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
1
0
2
2
2
1
B
C
A
s
D
1
0
2
∞
∞
Order of visited nodes: ACB
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
1
0
2
2
2
1
B
C
A
s
D
1
0
2
∞
∞
Order of visited nodes: ACB
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
1
0
2
2
2
1
B
C
A
s
D
1
0
2
4
4
Order of visited nodes: ACBD
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
B
C
A
s
5
5
D
1
1
0
2
2
2
1
B
C
A
s
D
1
0
2
4
4
Order of visited nodes: ACBD
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
Takeaways:
B
C
A
s
316800
D
∞
∞
∞
∞
316800
126720
126720
63360
63360
Bad Algorithm #2 (Dummy Nodes)
Bad algorithm #2: Create a new graph by adding a bunch of dummy nodes every unit along an edge, then run breadth-first search.
Takeaways:
Algorithm #1 (BFS) visits:� every node 1 edge away,�then every node 2 edges away,�then every node 3 edges away, etc.
Algorithm #2 (dummy nodes) visits:� every node distance 1 away,�then every node distance 2 away,�then every node distance 3 away, etc.
Bad Algorithm #3 (Best-First Search)
Bad algorithm #3: Perform best-first search.
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0]
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
Only difference from Algorithm #1: We added the word "closest".
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0]
Removed vertex: A
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5]
Removed vertex: A
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5]
Removed vertex: C
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
In BFS, we removed B here, but in best-first, we're removing C because it's closer.
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: C
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: B
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: B
The only outgoing edge is B→D.�D is already part of the SPT, so do nothing.
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: D
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
1
6
Bad Algorithm #3 (Best-First Search)
Add the start (A) to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if w is not already part of SPT,� add the edge, and add w to fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: D
No outgoing edges from D, so do nothing.
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
1
6
Bad Algorithm #3 (Best-First Search)
Bad algorithm #3: Perform best-first search.
Takeaways:
Bad Algorithm #3 (Best-First Search)
For each outgoing edge v→w: if w is not already part of SPT, add the edge,�mark w, and add w to fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: C
We should have added edge C→B, and thrown out the old edge (A→B) to B. Why?
The distance to B via C→B is 2.
This is better than the currently best known distance to B (5, via A→B).
C→B edge: B was in the SPT (via A→B), so we did nothing.
What should we have done here?
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
Finding a Shortest Paths Tree Algorithmically
Dijkstra's Algorithm:
∞
B
C
A
s
5
5
D
1
∞
∞
∞
2
2
1
We'll call this process “edge relaxation”.
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, B=∞, C=∞, D=∞]
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
Key difference from Algorithm #3: The condition for adding an edge.
(This used to say "if w not in SPT").
Extra bookkeeping: Instead of adding to the fringe as we go, we'll add all vertices to start.
This lets us track the best known distance to each vertex.
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, B=∞, C=∞, D=∞]
Removed vertex: A
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=∞]
Removed vertex: A
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=∞]
Removed vertex: C
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: C
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
2
Improvement: We used C→B because the distance via C→B (2) is better than the distance via A→B (5).
This also means we throw out the old edge (A→B) to B.
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: B
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
2
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: B
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
2
B→A (total=4) is not better than the best known way to A (0).
B→D (total=4) is better than the best known way to D (6, via C→D).�So, we'll update the path to D.
4
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: D
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
2
4
Finding a Shortest Paths Tree Algorithmically
Add all vertices to the fringe.
While fringe is not empty:
Remove the closest vertex from the fringe and mark it.
For each outgoing edge v→w: if the edge gives a better distance to w, � add the edge, and update w in the fringe.
Fringe: [A=0, C=1, B=5, D=6]
Removed vertex: D
No outgoing edges from D, so do nothing.
∞
B
C
A
s
5
5
D
1
∞
0
∞
2
2
1
5
1
6
2
4
Dijkstra's Algorithm
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
5
2
1
15
3
2
11
5
1
1
4
0
∞
∞
∞
∞
∞
∞
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B ∞ -
C ∞ -
D ∞ -
E ∞ -
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(B: ∞), (C: ∞), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
∞
∞
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D ∞ -
E ∞ -
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(C: 1), (B: 2), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
∞
∞
1
2
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D ∞ -
E ∞ -
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(B: 2), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
1
2
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D ∞ -
E ∞ -
F 16 C
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(B: 2), (F: 16), (D: ∞), (E: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
1
2
16
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D ∞ -
E ∞ -
F 16 C
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(F: 16), (D: ∞), (E: ∞), (G: ∞)]
4
0
∞
∞
∞
1
2
16
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 16 C
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(E: 5), (D: 13), (F: 16), (G: ∞)]
4
0
∞
∞
∞
1
2
16
5
13
1
Vertex C unchanged since 2+5 > 1
Which vertex is removed next?
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 16 C
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(D: 13), (F: 16), (G: ∞)]
4
0
∞
1
2
16
5
13
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 16 C
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(D: 13), (F: 16), (G: ∞)]
4
0
∞
1
2
16
5
13
1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: [(F: 9), (G: 10), (D: 13)]
4
0
∞
1
2
16
5
13
1
9
10
Vertex 2 unchanged since 5+1 > 1
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: [(G: 10), (D: 13)]
4
0
1
2
5
13
1
9
10
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 11 G
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: [(D: 11)]
4
0
1
2
5
13
1
9
10
11
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 11 G
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: []
4
0
1
2
5
11
1
9
10
Vertex E unchanged since 11 + 2 > 5
Note: If non-negative weights, impossible for any inactive vertex (white, not on fringe) to be improved!
Dijkstra’s Demo
Insert all vertices into fringe PQ, storing vertices in order of distance from source.
Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 11 G
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: []
4
1
Why Dijkstra's is Correct
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Dijkstra’s Algorithm Pseudocode
Key invariants:
Important properties:
Dijkstra’s:
Relaxing an edge p → q with weight w:
Guaranteed Optimality
Dijkstra’s Algorithm:
Dijkstra’s is guaranteed to return a correct result if all edges are non-negative.
Guaranteed Optimality
Dijkstra’s is guaranteed to be optimal so long as there are no negative edges.
Proof sketch: Assume all edges have non-negative weights.
Guaranteed Optimality
At start, distTo[source] = 0, which is optimal.
S
s
0
v2
v1
>c
c
∞
∞
v3
>c
∞
>c
v4
∞
Guaranteed Optimality
After relaxing all edges from source, let vertex v1 be the vertex with minimum weight, i.e. that is closest to the source.
S
s
0
v2
v1
>c
c
>c
c
v3
>c
>c
>c
v4
>c
Guaranteed Optimality
Claim: distTo[v1] is optimal, and thus future relaxations will fail. Why?
S
s
0
v2
v1
>c
c
>c
c
v3
>c
>c
>c
p
>c
w
This argument holds no matter which vertex you label as p.
Here, we set p = v4.
Guaranteed Optimality
Claim: distTo[v1] is optimal, and thus future relaxations will fail. Why?
S
s
0
v2
v1
>c
c
>c
c
v3
>c
>c
>c
v4
>c
w
p
>c
This argument holds no matter which vertex you label as p.
Here, we set p = some deeper vertex. Cost is still >c because you reach p via v3.
Negative Edges
Dijkstra’s Algorithm:
Dijkstra’s can fail if graph has negative weight edges. Why?
Algorithm #2 (dummy nodes) visits:� every node distance 1 away,�then every node distance 2 away,�then every node distance 3 away, etc.
Add negatively many dummy nodes??
Nodes that are distance -1 away??
Negative Edges
Dijkstra’s Algorithm:
Dijkstra’s can fail if graph has negative weight edges. Why?
X
Y
-67
82
101
Negative Edges
Dijkstra’s Algorithm:
Dijkstra’s can fail if graph has negative weight edges. Why?
X
Y
-67
82
101
34
Even though vertex Y has greater distTo at the time of its visit, it is still able to modify the distTo of a visited (white) vertex.
Runtime Analysis
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Dijkstra’s Algorithm Runtime
Priority Queue operation count, assuming binary heap based PQ:
Overall runtime: O(V*log(V) + V*log(V) + E*logV).
| # Operations | Cost per operation | Total cost |
PQ add | V | O(log V) | O(V log V) |
PQ removeSmallest | V | O(log V) | O(V log V) |
PQ changePriority | E | O(log V) | O(E log V) |
A* Idea and Demo
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Single Target Dijkstra’s
Is this a good algorithm for a navigation application?
The Problem with Dijkstra’s
Dijkstra’s will explore every place within nearly two thousand miles of Denver before it locates NYC.
The Problem with Dijkstra’s
We have only a single target in mind, so we need a different algorithm. How can we do better?
How can we do Better?
Explore eastwards first?
Introducing A*
Simple idea:
Compared to Dijkstra’s which only considers d(source, v).
Example: Henderson is farther than Englewood, but probably overall better for getting to NYC.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
1
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B ∞ -
C ∞ -
D ∞ -
E ∞ -
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(B: ∞), (C: ∞), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
∞
∞
1
h(v, goal) is arbitrary. In this example, it’s the min weight edge out of each vertex.
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
1
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D ∞ -
E ∞ -
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(B: 5), (C: 16), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
∞
∞
1
2
1
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
2
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D ∞ -
E ∞ -
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(C: 16), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
1
1
2
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
2
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(E: 6), (D: 15), (C: 16), (F: ∞), (G: ∞)]
4
0
∞
∞
∞
∞
1
1
2
5
13
Which vertex is removed next?
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
2
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F ∞ -
G ∞ -
5
2
1
15
3
2
11
5
1
1
Fringe: [(D: 15), (C: 16), (F: ∞), (G: ∞)]
4
0
∞
∞
1
1
2
5
13
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
2
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: [(G: 10), (D: 15), (C: 16), (F: ∞)]
4
0
∞
∞
1
1
2
5
13
10
9
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
2
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
Fringe: [(G: 10), (D: 15), (C: 16), (F: ∞)]
4
0
1
1
2
5
13
10
9
Next vertex to be dequeued is our target, so we’re done!
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Demo, with s = 0, goal = 6.
h(v, goal)
1
3
15
2
1
∞
0
B
C
D
E
F
G
A
s
Node distTo edgeTo
A 0 -
B 2 A
C 1 A
D 13 B
E 5 B
F 9 E
G 10 E
5
2
1
15
3
2
11
5
1
1
4
0
1
1
2
5
13
10
9
Observations:
Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).
Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.
A* Heuristic Example
How do we get our estimate?
For the map to the right, what could we use?
A* Heuristic Example
How do we get our estimate?
For the map to the right, what could we use?
/** h(v, goal) DOES NOT CHANGE as algorithm runs. */
public method h(v, goal) {
return computeLineDistance(v.latLong, goal.latLong);
}
A* vs. Dijkstra’s Algorithm
http://qiao.github.io/PathFinding.js/visual/
Note, if edge weights are all equal (as here), Dijkstra’s algorithm is just breadth first search.
This is a good tool for understanding distinction between order in which nodes are visited by the algorithm vs. the order in which they appear on the shortest path.
A* Heuristics (CS188 Preview)
Lecture 24, CS61B, Fall 2023
Shortest Paths:
Dijkstra’s Algorithm
A*
Impact of Heuristic Quality
Suppose we throw up our hands and say we don’t know anything, and just set h(v, goal) = 0 miles. What happens?
What if we just set h(v, goal) = 10000 miles?
A* Algorithm:
Visit vertices in order of d(Denver, v) + h(v, goal), where h(v, goal) is an estimate of the distance from v to NYC.
Impact of Heuristic Quality
Suppose we throw up our hands and say we don’t know anything, and just set h(v, goal) = 0 miles. What happens?
What if we just set h(v, goal) = 10000 miles?
A* Algorithm:
Visit vertices in order of d(Denver, v) + h(v, goal), where h(v, goal) is an estimate of the distance from v to NYC.
Impact of Heuristic Quality
Suppose you use your impressive geography knowledge and decide that the midwestern states of Illinois and Indiana are in the middle of nowhere: h(Indianapolis, goal)=h(Chicago, goal)=...=100000.
Impact of Heuristic Quality
Suppose you use your impressive geography knowledge and decide that the midwestern states of Illinois and Indiana are in the middle of nowhere: h(Indianapolis, goal)=h(Chicago, goal)=...=100000.
Heuristics and Correctness (EXTRA: Beyond Course Scope)
For our version of A* to give the correct answer, our A* heuristic must be:
This is an artificial intelligence topic, and is beyond the scope of our course.
Our heuristic was inadmissible and inconsistent.
Consistency and Admissibility (EXTRA: Beyond Course Scope)
All consistent heuristics are admissible.
Admissibility and consistency are sufficient conditions for certain variants of A*.
Heuristics that Yield Correct NYC Route
Admissible
Consistent
Our version of A* is called “A* graph search”. There’s another version called “A* tree search”. You’ll learn about it in 188.
Summary: Shortest Paths Problems
Single Source, Multiple Targets:
Single Source, Single Target:
Graph Problems
Problem | Problem Description | Solution | Efficiency |
paths | Find a path from s to every reachable vertex. | DepthFirstPaths.java | O(V+E) time Θ(V) space |
shortest paths | Find the shortest path from s to every reachable vertex. | BreadthFirstPaths.java | O(V+E) time Θ(V) space |
shortest weighted paths | Find the shortest path, considering weights, from s to every reachable vertex. | DijkstrasSP.java | O(E log V) time Θ(V) space |
shortest weighted path | Find the shortest path, consider weights, from s to some target vertex | A*: Same as Dijkstra’s but with h(v, goal) added to priority of each vertex. | Time depends on heuristic. Θ(V) space |