Grokking Algorithms

Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
So far, I’ve been using the term 
shortest path 
pretty literally: calculating 
the shortest path between two locations or between two people. I
hope this example showed you that the shortest path doesn’t have to
be about physical distance. It can be about minimizing something. In 
this case, Rama wanted to minimize the amount of money he spent. 
Thanks, Dijkstra!
Negative-weight edges
In the trading example, Alex offered to trade the book for 
two items.
Suppose Sarah offers to trade the LP for the poster, and
 
she’ll give Rama an additional $7.
It doesn’t cost Rama 
anything to make this trade; instead, he gets $7 back.
How would you show this on the graph?
The edge from the LP to the poster has a negative weight! Rama
gets $7 back if he makes that trade. Now Rama has two ways to get
to the poster.

---

129
Negative-weight edges
So it makes sense to do the second trade—Rama gets $2 back that way! 
Now, if you remember, Rama can trade the poster for the drums. There 
are two paths he could take.
The second path costs him $2 less, so he should take that path, right? 
Well, guess what? If you run Dijkstra’s algorithm on this graph, Rama 
will take the wrong path. He’ll take the longer path. 
You can’t use 
Dijkstra’s algorithm if you have negative-weight edges. 
Negative-weight 
edges break the algorithm. Let’s see what happens when you run 
Dijkstra’s algorithm on this. First, make the table of costs.
Next, find the lowest-cost node, and update the costs for its neighbors. 
In this case, the poster is the lowest-cost node. So, according to 
Dijkstra’s algorithm, 
there is no cheaper way to get to the poster than 
paying $0 
(you know that’s wrong!). Anyway, let’s update the costs for 
its neighbors.
Ok, the drums have a cost of $35 now. 

---

130