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.
Dostları ilə paylaş: