Chapter 9: Dijkstra’s algorithm
This introduction contrasts finding the path with the fewest segments with finding the fastest path when graph edges have travel times.
After this chapter you will be able to
- Fewest Segments Versus Fastest Path. Distinguish the path breadth-first search finds from the path Dijkstra’s algorithm finds when graph edges have travel times. Explain why a path with fewer segments need not be faster.
- Cheapest-node cost updates. Trace how Dijkstra’s algorithm chooses the node with the lowest current time estimate and updates its out-neighbors when it finds cheaper routes. Describe the changing estimates in the Start-to-Finish example, without explaining how to reconstruct the final path.
- Weighted paths versus fewest segments. Distinguish Dijkstra’s smallest-total-weight path from breadth-first search’s path with the fewest segments, using the travel-time example.
- Weights and shortest-path choice. Distinguish weighted from unweighted graphs and explain which shortest-path algorithm the section assigns to each.
- Stated limits of Dijkstra’s algorithm. State the graph conditions the section gives for Dijkstra’s algorithm and identify the alternative it names for negative-weight edges.
- Trade graph and costs. Explain how Rama’s trading choices become a weighted graph: items are nodes, trade offers are edges, and edge weights are the money required for each trade.
- Cheapest node cost updates. Describe how the example repeatedly chooses the cheapest node and updates the costs of its out-neighbors, changing their parents when a cheaper route is found. Explain why the cheapest node’s cost cannot be improved by first going through a more expensive route.
- Parent links and final path. Trace the parent links backward from the piano to recover Rama’s trades, and state the resulting minimum cost.
- Failure of finalized node costs. Explain how the negative-weight edge causes Dijkstra’s algorithm to miss the cheaper route: after processing the poster at cost $0, it finds a cheaper way to reach the poster but does not use that discovery to find the $33 route to the drums.
- Weighted graph representation. Describe how the graph hash table stores each node’s out-neighbors and the cost of reaching each neighbor.
- Cost parent and processed records. Explain what the costs and parents hash tables and the processed set track, including how an unknown cost is initialized.
- Lowest cost path updates. Trace how the algorithm selects a lowest-cost node, compares routes through its out-neighbors, updates a cheaper cost and parent, and marks the node processed.
- Shortest path algorithm choice. Distinguish when to use breadth-first search, Dijkstra’s algorithm, and Bellman–Ford for shortest paths based on whether a graph is weighted and whether any weights are negative.
What it builds on
- Finding the shortest path (chapter 6) · Finding a shortest path by counting segments.
- What is a graph? (chapter 6) · The example assumes familiarity with graph nodes and edges.
- Implementing the graph (chapter 6) · Representing a graph’s out-neighbors in a hash table.
Section by section
Introduction
This introduction contrasts finding the path with the fewest segments with finding the fastest path when graph edges have travel times.
- Fewest Segments Versus Fastest Path: Distinguish the path breadth-first search finds from the path Dijkstra’s algorithm finds when graph edges have travel times. Explain why a path with fewer segments need not be faster.
Why it matters: The distinction tells you why finding a route with fewer segments may not answer a question about travel time.
Key terms: breadth-first search, Dijkstra’s algorithm, weighted graphs, shortest path
9.1 Working with Dijkstra’s algorithm
This section walks through Dijkstra’s algorithm on a travel-time graph and contrasts its lowest-total-time path with breadth-first search’s fewest-segments path.
- Cheapest-node cost updates: Trace how Dijkstra’s algorithm chooses the node with the lowest current time estimate and updates its out-neighbors when it finds cheaper routes. Describe the changing estimates in the Start-to-Finish example, without explaining how to reconstruct the final path.
Why it matters: Following the cost updates shows how the algorithm discovers a faster route than the first one it sees. - Weighted paths versus fewest segments: Distinguish Dijkstra’s smallest-total-weight path from breadth-first search’s path with the fewest segments, using the travel-time example.
Why it matters: It clarifies what “shortest” means when routes have different travel times.
Key terms: cheapest node, out-neighbors, costs, breadth-first search, weight, smallest total weight, shortest path
9.2 Terminology
Defines weighted graphs and cycles, then states when the section recommends breadth-first search, Dijkstra’s algorithm, or Bellman–Ford for shortest paths.
- Weights and shortest-path choice: Distinguish weighted from unweighted graphs and explain which shortest-path algorithm the section assigns to each.
Why it matters: The presence of edge weights changes which shortest-path method the section recommends. - Cycles and path weight: Explain what a cycle is and why taking the cycle in the section’s example does not improve the shortest path.
Why it matters: It explains why a detour around the example’s cycle only makes the path more costly. - Stated limits of Dijkstra’s algorithm: State the graph conditions the section gives for Dijkstra’s algorithm and identify the alternative it names for negative-weight edges.
Why it matters: These are the limits the section gives for deciding whether to use Dijkstra’s algorithm.
Key terms: weights, weighted graph, unweighted graph, breadth-first search, Dijkstra’s algorithm, cycle, total weight, shortest path, undirected graph, nonnegative
9.3 Trading for a piano
The section uses a series of trades to show how Dijkstra’s algorithm finds a minimum-cost path and how parent links reveal the trades on that path.
- Trade graph and costs: Explain how Rama’s trading choices become a weighted graph: items are nodes, trade offers are edges, and edge weights are the money required for each trade.
Why it matters: Recognizing what nodes and weights represent lets you apply shortest-path reasoning to costs other than distance. - Cheapest node cost updates: Describe how the example repeatedly chooses the cheapest node and updates the costs of its out-neighbors, changing their parents when a cheaper route is found. Explain why the cheapest node’s cost cannot be improved by first going through a more expensive route.
Why it matters: The cost updates explain how the algorithm discovers a cheaper series of trades instead of keeping its first option. - Parent links and final path: Trace the parent links backward from the piano to recover Rama’s trades, and state the resulting minimum cost.
Why it matters: A minimum cost alone does not tell Rama which trades to make; the parent links supply the route.
Key terms: nodes, weights, edges, shortest path, cheapest node, cost, out-neighbors, parent, path, drums
9.4 Negative-weight edges
The section uses a trade with a negative cost to show why Dijkstra’s algorithm can return the wrong shortest path.
- Negative trade edge weight: Explain why the edge from the LP to the poster has a negative weight: Rama receives $7 rather than paying to make that trade.
Why it matters: The negative edge is what makes the cheaper route possible in this example. - Failure of finalized node costs: Explain how the negative-weight edge causes Dijkstra’s algorithm to miss the cheaper route: after processing the poster at cost $0, it finds a cheaper way to reach the poster but does not use that discovery to find the $33 route to the drums.
Why it matters: It tells you when Dijkstra’s algorithm cannot be trusted to find the cheapest path.
Key terms: negative weight, edge, Dijkstra’s algorithm, negative-weight edges, processed node, costs
9.5 Implementation
This section shows how to represent a weighted graph and track costs, parents, and processed nodes while implementing Dijkstra’s algorithm.
- Weighted graph representation: Describe how the graph hash table stores each node’s out-neighbors and the cost of reaching each neighbor.
Why it matters: The algorithm needs edge weights to calculate the cost of a path through a neighbor. - Cost parent and processed records: Explain what the costs and parents hash tables and the processed set track, including how an unknown cost is initialized.
Why it matters: These records let the algorithm improve a route while keeping track of which nodes it has already handled. - Lowest cost path updates: Trace how the algorithm selects a lowest-cost node, compares routes through its out-neighbors, updates a cheaper cost and parent, and marks the node processed.
Why it matters: Comparing each newly found route with its recorded cost is how the implementation improves paths. - Lowest cost node search: State how this implementation finds a lowest-cost node and identify the more efficient alternative mentioned in the section.
Why it matters: It distinguishes the straightforward node search used here from the improvement the book mentions.
Key terms: graph, out-neighbors, cost, hash table, costs, parents, processed, infinity, lowest cost, parent
9.6 Recap
The recap distinguishes which shortest-path algorithm to use for unweighted graphs, nonnegatively weighted graphs, and graphs with negative weights.
- Shortest path algorithm choice: Distinguish when to use breadth-first search, Dijkstra’s algorithm, and Bellman–Ford for shortest paths based on whether a graph is weighted and whether any weights are negative.
Why it matters: Choosing a shortest-path algorithm depends on the graph’s edge weights.
Key terms: breadth-first search, unweighted graph, Dijkstra’s algorithm, weighted graph, nonnegative, negative weights
Where this is used later
- Min heaps and priority queues (chapter 13) · Introduces the priority queues and heaps named as the more efficient alternative.
Concepts explained in this chapter
- Dijkstra's algorithmDijkstra's algorithm is a graph shortest-path algorithm that repeatedly selects the lowest-cost unprocessed node and relaxes its outgoing edges, assuming edge weights are nonnegative.
- edge weightAn edge weight is a numerical value assigned to a graph edge to represent traversal cost, distance, time, or another quantity.
- costA cost is a numerical amount representing the time, distance, or other expense associated with reaching a node or traversing an edge.
- parent pointerA parent pointer is a recorded predecessor node that identifies the preceding step in a path to another node.
- MapA dictionary is a Python mapping data structure that associates keys with corresponding values.
- graphA graph is a data structure consisting of nodes and connections that represent relationships between entities.
- setA set is a collection that stores distinct elements without assigning significance to their insertion order.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.