126
Chapter 7
I
Dijkstra’s algorithm
The bass guitar is the next cheapest item. Update its neighbors.
Ok, you finally
have a price for the piano, by trading the guitar for the
piano. So you set the guitar as the parent. Finally,
the last node, the
drum set.
Rama can get the piano even cheaper by trading the drum set for the
piano instead.
So the cheapest set of trades will cost Rama $35
.
Now,
as I promised, you need to figure out the path. So far, you know
that the shortest path costs $35, but how do you figure out the path? To
start with,
look at the parent for
piano
.
The piano has drums as its parent. That means Rama trades the drums
for the piano. So you follow this edge.
127
Trading for a piano
Let’s see how you’d follow the edges.
Piano
has
drums
as its parent.
And
drums
has the LP as its parent.
So Rama will trade the LP for the drums. And of course, he’ll
trade the
book for the LP. By following the parents backward, you now have the
complete path.
Here’s the series of trades Rama needs to make.
