This lecture is not on midterm 2!
CS61B
Lecture 25: Shortest Paths
¡ñ Summary So Far: DFS vs. BFS
¡ñ Dijkstra¡¯s Algorithm
¡ñ Dijkstra¡¯s Correctness and Runtime
¡ñ A*
¡ñ A* Heuristics (188 preview)
datastructur.es
Graph Problems
Problem
Problem Description
Solution
Efficiency (adj. list)
s-t paths
Find a path from s to every reachable vertex.
DepthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
s-t shortest paths
Find a shortest path from s to every reachable vertex.
BreadthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
Last time, saw two ways to find paths in a graph. ¡ñ DFS and BFS.
Which is better?
datastructur.es
BFS vs. DFS for Path Finding
Possible considerations:
¡ñ Correctness. Do both work for all graphs? ¡ð Yes!
¡ñ Output Quality. Does one give better results?
¡ð BFS is a 2-for-1 deal, not only do you get paths, but your paths are also
guaranteed to be shortest.
¡ñ Time Efficiency. Is one more efficient than the other?
¡ð Should be very similar. Both consider all edges twice. Experiments or very careful analysis needed.
datastructur.es
BFS vs. DFS for Path Finding
¡ñ Space Efficiency. Is one more efficient than the other?
¡ð DFS is worse for spindly graphs.
¡ö Call stack gets very deep.
¡ö Computer needs ¦¨(V) memory to remember recursive calls (see CS61C).
¡ð BFS is worse for absurdly ¡°bushy¡± graphs.
¡ö Queue gets very large. In worst case, queue will require ¦¨(V) memory.
¡ö Example: 1,000,000 vertices that are all connected. 999,999 will be
enqueued at once.
¡ð Note: In our implementations, we have to spend ¦¨(V) memory anyway
to track distTo and edgeTo arrays.
¡ö Can optimize by storing distTo and edgeTo in a map instead of an array.
datastructur.es
BreadthFirstSearch for Google Maps
As we discussed last time, BFS would not be a good choice for a google maps style navigation application.
¡ñ The problem: BFS returns path with shortest number of edges. Let¡¯s see a quick example.
datastructur.es
Breadth First Search for Mapping Applications
Suppose we¡¯re trying to get from s to t.
t
s
The reason the places are in Chinese is because I took this diagram from my Chinese language version of 61B.
datastructur.es
Breadth First Search for Mapping Applications
Suppose we¡¯re trying to get from s to t.
s
t
datastructur.es
Breadth First Search for Mapping Applications
BFS yields the wrong route from s to t.
¡ñ No: BFS yields a route of length ~190 instead of ~110.
¡ñ We need an algorithm that takes into account edge distances, also known
as ¡°edge weights¡±!
Correct Result
BFS Result
10 20
40
40 t
10 20
40
40
80
40
70
t
s
s
80
40
70
datastructur.es
Dijkstra¡¯s Algorithm
datastructur.es
Problem: Single Source Single Target Shortest Paths
Goal: Find the shortest paths from source vertex s to some target vertex t.
3
11
1
2
1
2
3
6
5
5
s
0
4
1
1
4
1
2
15
5
Challenge: Try to find the shortest path from town 0 to town 5.
¡ñ Each edge has a number representing the length of that road in miles.
datastructur.es
Problem: Single Source Single Target Shortest Paths
Goal: Find the shortest paths from source vertex s to some target vertex t.
3
11
1
2
1
Best path from 0 to 5 is
¡ñ 0 -> 2 -> 4 -> 5.
¡ñ Total length is 9 miles.
The path 0 -> 2 -> 5 only involves three towns, but total length is 16 miles.
2
3
6
5
5
s
0
4
1
1
4
1
2
15
5
datastructur.es
Problem: Single Source Single Target Shortest Paths
Goal: Find the shortest paths from source vertex s to some target vertex t.
3
11
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–
5
3
1
2
2
6
5
s
0
4
1
1
4
1
2
15
5
Shortest path from s=0 to t=5
Observation: Solution will always be a path with no cycles (assuming non-negative weights).
datastructur.es
Problem: Single Source Shortest Paths
Goal: Find the shortest paths from source vertex s to every other vertex.
3
11
1
2
1
2
3
6
5
5
s
0
4
1
1
4
1
2
15
5
Challenge: Try to write out the solution for this graph. ¡ñ You should notice something interesting.
datastructur.es
Problem: Single Source Shortest Paths
Goal: Find the shortest paths from source vertex s to every other vertex.
3
11
2
1
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
Shortest paths from s=0
2
3
6
5
5
s
0
4
1
1
4
1
2
15
Observation: Solution will always be a tree.
¡ñ Can think of as the union of the shortest paths to all vertices.
datastructur.es
5
1
SPT Edge Count: http://yellkey.com/?
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] 3
1
6
s
0
4
2
5
datastructur.es
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]
3
V: 7
Number of edges in SPT is 6
Always V-1:
1
¡ñ
For each vertex, there is exactly one input edge (except source).
6
s
0
4
2
5
datastructur.es
Finding a Shortest Paths Tree (By Hand)
What is the shortest paths tree for the graph below? Note: Source is A.
B
5
2
2
s
AD C
1
1
5
datastructur.es
Finding a Shortest Paths Tree (By Hand)
What is the shortest paths tree for the graph below?
¡ñ Annotation in magenta shows the total distance from the source.
2 04
B
5
2
s
2
A
1
D
1
5
C
1
datastructur.es
Creating an Algorithm
Let¡¯s create an algorithm for finding the shortest paths.
Will start with a bad algorithm and then successively improve it.
¡ñ Algorithm begins in state below. All vertices unmarked. All distances infinite.
No edges in the SPT.
¡Þ
B
5
2
¡Þ¡Þ
s
2
1
AD
C
¡Þ
1
5
datastructur.es
Finding a Shortest Paths Tree Algorithmically (Incorrect)
Bad algorithm #1: Perform a depth first search. When you visit v:
¡ñ For each edge from v to w, if w is not already part of SPT, add the edge.
dfs(A):
Add A->B to SPT Add A->C to SPT
¡Þ 5
B
dfs(B): 5 Add B->D to SPT
A already in SPT.
0 ¡Þ0 ¡Þ7
sDsD C5C
5
B
5
2
2
3
3
A
1
A
1
1
5
1
5
B
5
2
dfs(C):
B already in SPT. D already in SPT.
¡Þ11 07
s
A
3
1
D
1
5
C
1
datastructur.es
Finding a Shortest Paths Tree Algorithmically (Incorrect)
Bad algorithm #2: Perform a depth first search. When you visit v:
¡ñ For each edge from v to w, add edge to the SPT only if that edge yields
better distance.
5
We¡¯ll call this process ¡°edge relaxation¡±.
dfs(A):
A->B is 5, < than ¡Þ A->C is 1, < than ¡Þ
¡Þ
B
dfs(B): 5 B->D is 5 + 2 = 7, better than ¡Þ.
B->A is 5 + 3 = 8, worse than 0.
0 ¡Þ0 ¡Þ7
sDsD C52C
¡Þ1 61 07
5
A
B
5
2
5
2
3
3
A
1
1
1
5
B
1
5
2
s C->B is 1 + 1 = 2, better than 5.
3
A
1
D
dfs(C):
C->D is 1 + 5 = 6, better than 7.
1
Improvements:
¡ñ Use better edges if found.
datastructur.es
1
5
C
Finding a Shortest Paths Tree Algorithmically (Incorrect)
Dijkstra¡¯s Algorithm: Perform a best first search (closest first). When you visit v: ¡ñ For each from v to w, relax that edge.
A has lowest dist, so dfs(A): ¡Þ 5 A->B is 5, < than ¡Þ
A->C is 1, < than ¡Þ B
C has lowest dist, so dfs(C): 5 2 C->B is 1 + 1 = 2, better than 5.
C->D is 1 + 5 = 6, better than ¡Þ. B
0¡Þ0¡Þ6
sDsD
5
2
5
2
3
3
A
1
A
1
1
5
1
5
C
2
C
B
¡Þ1 41 06
s
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.
D
A
5
2
3
1
1
5
C
1
Improvements:
¡ñ Use better edges if found.
¡ñ Traverse ¡°best first¡±. datastructur.es
Dijkstra¡¯s Algorithm 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.
Dijkstra¡¯s Algorithm Demo Link
0
s
¡Þ
1
3
¡Þ
¡Þ
4
¡Þ
5
2
11
3
1
2
¡Þ
6
5
5
0
1
¡Þ
2
1
4
1
15
datastructur.es
Dijkstra¡¯s Correctness and Runtime
datastructur.es
Dijkstra¡¯s Algorithm Pseudocode
Dijkstra¡¯s:
¡ñ PQ.add(source, 0)
¡ñ For other vertices v, PQ.add(v, infinity)
¡ñ While PQ is not empty:
¡ð p = PQ.removeSmallest()
¡ð Relax all edges from p
Relaxing an edge p ¡ú q with weight w:
¡ñ If distTo[p] + w < distTo[q]:
¡ð distTo[q] = distTo[p] + w
¡ð edgeTo[q] = p
¡ð PQ.changePriority(q, distTo[q])
Key invariants:
¡ñ edgeTo[v] is the best known predecessor of v.
¡ñ distTo[v] is the best known total distance from source to v.
¡ñ PQ contains all unvisited vertices in order of distTo.
Important properties:
¡ñ Always visits vertices in order of total distance from source.
¡ñ Relaxation always fails on edges
to visited (white) vertices.
datastructur.es
Guaranteed Optimality
Dijkstra¡¯s Algorithm:
¡ñ Visit vertices in order of best-known distance from source. On visit, relax every edge from the visited vertex.
Dijkstra¡¯s is guaranteed to return a correct result if all edges are non-negative.
datastructur.es
Guaranteed Optimality
Dijkstra¡¯s is guaranteed to be optimal so long as there are no negative edges.
¡ñ Proof relies on the property that relaxation always fails on edges to visited (white) vertices.
Proof sketch: Assume all edges have non-negative weights.
¡ñ At start, distTo[source] = 0, which is optimal.
¡ñ After relaxing all edges from source, let vertex v1 be the vertex with
minimum weight, i.e. that is closest to the source. Claim: distTo[v1] is optimal, and thus future relaxations will fail. Why?
¡ð distTo[p] ¡Ý distTo[v1] for all p, therefore
¡ð distTo[p] + w ¡Ý distTo[v1]
¡ñ Can use induction to prove that this holds for all vertices after dequeuing.
datastructur.es
Negative Edges
Dijkstra¡¯s Algorithm:
¡ñ Visit vertices in order of best-known distance from source. On visit, relax every edge from the visited vertex.
Dijkstra¡¯s can fail if graph has negative weight edges. Why? ¡ñ Relaxation of already visited vertices can succeed.
14
101
34
1
82
-67
33
datastructur.es
Negative Edges
Dijkstra¡¯s Algorithm:
¡ñ Visit vertices in order of best-known distance from source. On visit, relax every edge from the visited vertex.
Dijkstra¡¯s can fail if graph has negative weight edges. Why? ¡ñ Relaxation of already visited vertices can succeed.
14
34 82
101
34
Even though vertex 34 has greater distTo at the time of its visit, it is still able to modify the distTo of a visited (white) vertex.
1
-67
33
datastructur.es
Dijkstra¡¯s Algorithm Runtime
Priority Queue operation count, assuming binary heap based PQ:
¡ñ add: V, each costing O(log V) time.
¡ñ removeSmallest: V, each costing O(log V) time.
¡ñ changePriority: E, each costing O(log V) time.
Overall runtime: O(V*log(V) + V*log(V) + E*logV).
¡ñ Assuming E > V, this is just O(E log V) for a connected graph.
# 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)
datastructur.es
A*
datastructur.es
Single Target Dijkstra¡¯s
Is this a good algorithm for a navigation application?
¡ñ Will it find the shortest path?
¡ñ Will it be efficient?
datastructur.es
The Problem with Dijkstra¡¯s
Dijkstra¡¯s will explore every place within nearly two thousand miles of Denver before it locates NYC.
datastructur.es
The Problem with Dijkstra¡¯s
We have only a single target in mind, so we need a different algorithm. How can we do better?
datastructur.es
How can we do Better?
Explore eastwards first?
datastructur.es
Introducing A*
Simple idea:
Compared to Dijkstra¡¯s which only considers d(source, v).
¡ñ Visit vertices in order of d(Denver, v) + h(v, goal), where h(v, goal) is an estimate of the distance from v to our goal NYC.
¡ñ In other words, look at some location v if:
¡ð We know already know the fastest way to
reach v.
¡ð AND we suspect that v is also the fastest way to
NYC taking into account the time to get to v.
Example: Henderson is farther than Englewood, but probably overall better for getting to NYC.
datastructur.es
A* Demo, with s = 0, goal = 6.
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 Link
# h(v, goal) 010 13s
2 15
¡Þ
1
3
¡Þ
¡Þ
4
¡Þ
5
11
2
1
¡Þ
6
3
2
5
5
0
1
1
4
1
32 45 5¡Þ 60
Heuristic h(v, goal) estimates that distance from 2 to 6 is 15.
¡Þ
2
15
datastructur.es
A* Heuristic Example
How do we get our estimate?
¡ñ Estimate is an arbitrary heuristic h(v, goal).
¡ñ heuristic: ¡°using experience to learn and improve¡±
¡ñ Doesn¡¯t have to be perfect!
For the map to the right, what could we use?
datastructur.es
A* Heuristic Example
How do we get our estimate?
¡ñ Estimate is an arbitrary heuristic h(v, goal).
¡ñ heuristic: ¡°using experience to learn and improve¡±
¡ñ Doesn¡¯t have to be perfect!
For the map to the right, what could we use?
¡ñ As-the-crow-flies distance to NYC.
/** h(v, goal) DOES NOT CHANGE as algorithm runs. */ public method h(v, goal) {
return computeLineDistance(v.latLong, goal.latLong); }
datastructur.es
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.
¡ñ Unless you¡¯re really lucky, vastly more nodes are visited than exist on the shortest path.
datastructur.es
A* Heuristics (188 Preview)
datastructur.es
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.
datastructur.es
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?
¡ñ We just end up with Dijkstra¡¯s algorithm. What if we just set h(v, goal) = 10000 miles?
¡ñ We just end up with Dijkstra¡¯s algorithm.
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.
datastructur.es
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.
¡ñ Is our algorithm still correct or does it just run slower?
datastructur.es
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.
¡ñ Is our algorithm still correct or does it just run slower?
¡ð It is incorrect. It will fail to find the shortest path by dodging Illinois.
datastructur.es
Heuristics and Correctness
For our version of A* to give the correct answer, our A* heuristic must be:
¡ñ Admissible: h(v, NYC) ¡Ü true distance from v to NYC.Our heuristic was
¡ñ Consistent: For each neighbor of w:
¡ð h(v, NYC) ¡Ü dist(v, w) + h(w, NYC). ¡ñ Inadmissible:
¡ð Where dist(v, w) is the weight of the edge from v to w.
This is an artificial intelligence topic, and is beyond the scope of our course.
¡ñ We will not discuss these properties beyond their definitions. See CS188 which will cover this topic in considerably more depth.
¡ñ You should simply know that the choice of heuristic matters, and that if you make a bad choice, A* can give the wrong answer.
¡ñ You will not be expected to tell us whether a given heuristic is admissible or consistent unless we define these terms on an exam.
inadmissible and
inconsistent.
datastructur.es
Consistency and Admissibility (EXTRA: Beyond Course Scope)
All consistent heuristics are admissible.
¡ñ ¡®Admissible¡¯ means that the heuristic never overestimates.
Admissibility and consistency are sufficient conditions for certain variants of A*.
¡ñ If heuristic is admissible, A* tree search yields the shortest path.
¡ñ If heuristic is consistent, A* graph search yields the shortest path.
¡ñ These conditions are sufficient, but not necessary.
Our version of A* is called ¡°A* graph search¡±. There¡¯s another version called ¡°A* tree search¡±. You¡¯ll learn about it in 188.
Consistent
Admissible
Heuristics that Yield Correct NYC Route
datastructur.es
Summary: Shortest Paths Problems
Single Source, Multiple Targets:
¡ñ Can represent shortest path from start to every vertex as a shortest paths tree with V-1 edges.
¡ñ Can find the SPT using Dijkstra¡¯s algorithm. Single Source, Single Target:
¡ñ Dijkstra¡¯s is inefficient (searches useless parts of the graph).
¡ñ Can represent shortest path as path (with up to V-1 vertices, but probably
far fewer).
¡ñ A* is potentially much faster than Dijkstra¡¯s.
¡ð Consistent heuristic guarantees correct solution.
datastructur.es
Graph Problems
Problem
Problem Description
Solution
Efficiency
paths
Find a path from s to every reachable vertex.
DepthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
shortest paths
Find the shortest path from s to every reachable vertex.
BreadthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
shortest weighted paths
Find the shortest path, considering weights, from s to every reachable vertex.
DijkstrasSP.java
Demo
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.
Demo
Time depends on heuristic. ¦¨(V) space
datastructur.es