CS 61B Shortest Paths and MSTs Spring 2021 Discussion 10: March 29, 2021
1 The Shortest Path To Your Heart
For the graph below, let g(u, v) be the weight of the edge between any nodes u and v. Let h(u, v) be the value returned by the heuristic for any nodes u and v.
Below, the pseudocode for Dijkstra¡¯s and A* are both shown for your reference throughout the problem.
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
PQ = new PriorityQueue()
PQ.add(A, 0) 4
Dijkstra¡¯s Pseudocode
A* Pseudocode
1 PQ = new PriorityQueue()
2 PQ.add(A, h(A))
3 PQ.add(v, infinity) # (all nodes except A).
5 distTo = {} # map
6 distTo[A] = 0
7 distTo[v] = infinity # (all nodes except A).
9 while (not PQ.isEmpty()):
10 poppedNode, poppedPriority = PQ.pop() 11 if (poppedNode == goal): terminate
13 for child in poppedNode.children:
14 if PQ.contains(child):
15 potentialDist = distTo[poppedNode] + 16 edgeWeight(poppedNode, child)
PQ.add(v, infinity) # (all nodes except A).
distTo = {} # map
distTo[A] = 0 8
distTo[v] = infinity # (all nodes except A).
while (not PQ.isEmpty()):
popNode, popPriority = PQ.pop() 12
for child in popNode.children: if PQ.contains(child):
potentialDist = distTo[popNode] + edgeWeight(popNode, child) 17
if potentialDist < distTo[child]: distTo.put(child, potentialDist) PQ.changePriority(child, potentialDist) 20
18 if potentialDist < distTo[child]: 19 distTo.put(child, potentialDist)
PQ.changePriority(child, potentialDist + h(child))
2 Shortest Paths and MSTs
(a) Run Dijkstra¡¯s algorithm to find the shortest paths from A to every other vertex. You may find it helpful to keep track of the priority queue. We have provided a table to keep track of best distances, and the edge leading to each vertex on the currently known shortest paths.
ABCDEFG
DistTo EdgeTo
(b) Extra: Given the weights and heuristic values for the graph above, what path would A* search return, starting from A and with G as a goal? Note that the edge weights provided below for your convenience are the same as in the image.
Edge weights g(A,B)=1 g(B,C)=3 g(C,F)=2 g(C,G)=4 g(F, G) = 1 g(A,D)=2 g(D,E) = 3 g(E,G) = 4 g(A,E) = 7
Heuristics h(A, G) = 7 h(B, G) = 6 h(C, G) = 3 h(F, G) = 1 h(D, G) = 6 h(E,G) = 3
ABCDEFG
DistTo EdgeTo
2 Minimalist Moles
Mindy the mole wants to dig a network of tunnels connecting all of their secret hideouts. There are a set few paths between the secret hideouts that Mindy can choose to possibly include in their tunnel system, shown below. However, some portions of the ground are harder to dig than others, and Mindy wants to do as little work as possible. In the diagram below, the numbers next to the paths correspond to how hard that path is to dig for Mindy.
(a) How can Mindy figure out a tunnel system to connect their secret hideouts while doing minimal work?
(b) Extra: Find a valid MST for the graph above using Kruskal¡¯s algorithm, then Prims. For Prim¡¯s algorithm, take A as the start node. In both cases, if there is ever a tie, choose the edge that connects two nodes with lower alphabetical order.
Shortest Paths and MSTs 3
(c) Extra: Are the above MSTs different or the same? Is there a different tie-breaking scheme that would change your answer?