Algorithm Initialization and Data Structures
What You'll Learn
You'll learn how to set up the essential data structures—distance arrays, predecessor tracking, and a priority queue—that power Dijkstra's algorithm before it begins processing nodes.
Why Initialization Matters
Before Dijkstra's algorithm can find shortest paths, it needs a proper workspace. Think of it like setting up a GPS navigation system: you need to mark your starting location, prepare a way to track the best routes found so far, and maintain a to-do list of places to explore next.
The Three Core Structures
Distance Array
Create an array to store the shortest known distance from the source to every node. Initialize the source node to 0 (distance to itself) and all other nodes to infinity (∞), meaning "unreachable so far."
Predecessor Tracking
Set up an array or dictionary to remember which node leads to each node on the shortest path. Initialize all predecessors as null or undefined. This lets you reconstruct the actual path later, not just know its length.
Priority Queue
Initialize a min-priority queue (often a min-heap) with the source node at distance 0. This queue always gives you the unvisited node with the smallest known distance, making Dijkstra's greedy choice efficient. As the algorithm runs, you'll insert nodes with their current distances and extract the minimum repeatedly.
Why This Setup Works
The distance array prevents recalculating paths you've already improved. The predecessor array builds a "breadcrumb trail" back to the source. The priority queue ensures you always expand the most promising node next, enabling the greedy strategy.
Key Takeaway: Dijkstra's algorithm relies on three initialized structures—a distance array (source = 0, others = ∞), a predecessor tracker (all null), and a min-priority queue (starting with the source)—to efficiently explore and record shortest paths.