Course contentsShow
← Computer Science
Lesson 968 of 2,87223. Shortest Path AlgorithmsFree lesson

Algorithm Initialization and Data Structures

Setting up distance arrays, predecessor tracking, and the priority queue for Dijkstra's algorithm.

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.