Grokking Algorithms

Terminology
I want to show you some more examples of Dijkstra’s algorithm in 
action. But first let me clarify some terminology.
When you work with Dijkstra’s algorithm, each edge in the graph has a 
number associated with it. These are called 
weights.
A graph with weights is called a 
weighted graph
. A graph without 
weights is called an 
unweighted graph
.

---

121
Terminology
To calculate the shortest path in an unweighted graph, use 
breadth-first 
search
. To calculate the shortest path in a weighted graph, use 
Dijkstra’s 
algorithm
. Graphs can also have 
cycles
. A cycle looks like this.
It means you can start at a node, travel around, and end up at the same 
node. Suppose you’re trying to find the shortest path in this graph that 
has a cycle.
Would it make sense to follow the cycle? Well, you can use the path that 
avoids the cycle.
Or you can follow the cycle.

---

122
Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
You end up at node A either way, but the cycle adds more weight. You 
could even follow the cycle twice if you wanted.
But every time you follow the cycle, you’re just adding 8 to the total 
weight. So following the cycle will never give you the shortest path. 
Finally, remember our conversation about directed versus undirected 
graphs from chapter 6?
An undirected graph means that both nodes point to each other. That’s 
a cycle!
With an undirected graph, each edge adds another cycle.
Dijkstra’s algorithm only works with 
directed acyclic graphs
,
called DAGs for short.