Grokking Algorithms

Trading for a piano
Enough terminology, let’s look at another example! This is Rama.
Rama is trying to trade a music book for a piano.

---

123
Trading for a piano
“I’ll give you this poster for your book,” says Alex. “It’s a poster of 
my favorite band, Destroyer. Or I’ll give you this rare LP of Rick 
Astley for your book and $5 more.” “Ooh, I’ve heard that LP has a 
really great song,” says Amy. “I’ll trade you my guitar or drum set 
for the poster or the LP.”
“I’ve been meaning to get into guitar!” exclaims Beethoven. “Hey, 
I’ll trade you my piano for either of Amy’s things.”
Perfect! With a little bit of money, Rama can trade his way from a piano 
book to a real piano. Now he just needs to figure out how to spend the 
least amount of money to make those trades. Let’s graph out what he’s 
been offered.
In this graph, the nodes are all the items Rama can trade for. The 
weights on the edges are the amount of money he would have to pay 
to make the trade. So he can trade the poster for the guitar for $30, or 
trade the LP for the guitar for $15. How is Rama going to figure out 
the path from the book to the piano where he spends the least dough? 
Dijkstra’s algorithm to the rescue! Remember, Dijkstra’s algorithm has 
four steps. In this example, you’ll do all four steps, so you’ll calculate 
the final path at the end, too.
Before you start, you need some 
setup. Make a table of the cost for 
each node. The cost of a node is how 
expensive it is to get to.

---

124
Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
You’ll keep updating this table as the algorithm goes on. To calculate the 
final path, you also need a 
parent
column on this table.
I’ll show you how this column works soon. Let’s start the algorithm.
Step 1:
Find the cheapest node. In this case, the poster is the cheapest 
trade, at $0. Is there a cheaper way to trade for the poster? This is a 
really important point, so think about it. Can you see a series of trades 
that will get Rama the poster for less than $0? Read on when you’re 
ready. Answer: No. 
Because the poster is the cheapest node Rama can get 
to, there’s no way to make it any cheaper.
Here’s a different way to look at 
it. Suppose you’re traveling from home to work.
If you take the path toward the school, that takes 2 minutes. If you take 
the path toward the park, that takes 6 minutes. Is there any way you can 
take the path toward the park, and end up at the school, in less than 
2 minutes? It’s impossible, because it takes longer than 2 minutes just 
to get to the park. On the other hand, can you find a faster path to the 
park? Yup.

---

125
Trading for a piano
This is the key idea behind Dijkstra’s algorithm: 
Look at the cheapest 
node on your graph. There is no cheaper way to get to this node!
Back to the music example. The poster is the cheapest trade.
Step 2:
Figure out how long it takes to get to its neighbors (the cost).
You have prices for the bass guitar and the drum set in the table. Their 
value was set when you went through the poster, so the poster gets set 
as their parent. That means, to get to the bass guitar, you follow the edge 
from the poster, and the same for the drums.