Implementing Dijkstra's Algorithm with Priority Queues

Welcome to our final lesson in the "Graph Modeling and Traversal" module. In our previous lesson, you learned how to compute a topological ordering for a Directed Acyclic Graph (DAG) using Kahn's algorithm. That was about establishing a valid sequence of nodes based on dependencies. Today, we shift our focus from ordering to optimization by tackling one of the most famous problems in computer science: finding the shortest path in a weighted graph.

You're already familiar with Breadth-First Search (BFS), which finds the shortest path in an unweighted graph by exploring level by level. But what happens when the connections, or edges, have different costs? Think of a GPS navigating a road network where different roads have different travel times. A path with more roads might be faster if they are all highways, while a path with fewer roads could be slower if it involves city traffic.

This is precisely the problem that Dijkstra's algorithm solves. By the end of this lesson, you will be able to compute the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights, using Dijkstra's algorithm implemented efficiently with a min-heap.

The Core Idea: A Greedy Approach to Pathfinding

BFS works because each step (crossing one edge) has a uniform cost of 1. When costs vary, we need a more intelligent strategy. Dijkstra's algorithm uses a greedy approach: at every step, it decides to visit the unvisited node that has the smallest known distance from the source. The intuition is that by always extending the shortest known path, we are building up the final shortest paths from the source outwards.

To implement this, we need to maintain a few key pieces of information:

1. Distances: An array or map to store the shortest distance we've found so far from the source to every other node. We initialize the source's distance to 0 and all others to infinity.
2. A Priority Queue (Min-Heap): To efficiently find the unvisited node with the smallest current distance. This is the heart of an efficient Dijkstra implementation.
3. Visited Nodes: A way to track which nodes have been "finalized"—meaning we've found their true shortest path and won't need to reconsider them.

To see this process in action, let's watch a fantastic video from the Spanning Tree channel that provides a clear, high-level walkthrough of the algorithm's logic.

The core operation you saw in the video is often called relaxation. When we are at a node u and consider its neighbor v, we check if the path to v through u is shorter than the currently known shortest path to v. If distance[u] + weight(u, v) < distance[v], we've found a better path, so we "relax" the edge by updating distance[v].

Visualizing the Algorithm with a Min-Heap

The previous video gave you the "what" and "why" of the algorithm. Now let's focus on the "how," specifically the role of the min-heap. A min-heap ensures that the step of "choosing the unexplored town with the smallest value" is extremely fast.

The following animated video from the Depth First channel does an exceptional job of showing the state of the graph, the distance estimates, and the min-heap at every single step. This will be invaluable for cementing your understanding.

To summarize the visual flow you've just seen, here is an excellent static diagram that lays out the graph, the state of the priority queue after each major step, and the final array of shortest distances.

From Algorithm to TypeScript Implementation

Now that you have a strong conceptual and visual model, let's codify it. We will follow a clear set of steps, which you can also review in the "Dijkstra's Algorithm" article from GeeksForGeeks.

A crucial point for you as a TypeScript developer is that JavaScript (and by extension, TypeScript) does not have a built-in priority queue or min-heap data structure. In an interview setting, you would either be provided with one, allowed to use a library, or expected to implement a basic version yourself.

The same GeeksForGeeks article provides a full JavaScript implementation, including a MinHeap class. This is a perfect template for solving this kind of problem.

Here's the logic adapted into a clean TypeScript function, assuming the MinHeap class from the resource is available.

// Assume MinHeap class from the resource is defined here.
// class MinHeap { ... }

/**
 * Computes shortest paths from a source node in a weighted graph.
 * @param adj Adjacency list where adj[i] is an array of [neighbor, weight] pairs.
 * @param V The total number of vertices in the graph.
 * @param src The source vertex.
 * @returns An array of shortest distances from the source to each vertex.
 */
function dijkstra(adj: number[][][], V: number, src: number): number[] {
    // 1. Initialize distances: infinity for all, 0 for source.
    const dist: number[] = new Array(V).fill(Number.MAX_SAFE_INTEGER);
    dist[src] = 0;

    // 2. Initialize min-heap with the source node.
    // The heap stores pairs of [distance, node].
    const pq = new MinHeap();
    pq.push([0, src]);

    // 3. Main loop
    while (!pq.isEmpty()) {
        // Extract the node with the smallest distance
        const [d, u] = pq.pop();

        // Optimization: If we've found a shorter path already, skip.
        if (d > dist[u]) {
            continue;
        }

        // 4. Relaxation: Check all neighbors of the current node
        for (const [v, weight] of adj[u]) {
            // If we found a shorter path to v through u...
            if (dist[u] + weight < dist[v]) {
                // ...update the distance and add it to the heap.
                dist[v] = dist[u] + weight;
                pq.push([dist[v], v]);
            }
        }
    }

    return dist;
}

// Example Usage:
const V = 6;
const src = 0;
// Adjacency list representation of the graph in the image
const adj = [
    [[1, 4], [2, 1]], // Node 0 neighbors
    [[3, 2], [4, 5]], // Node 1 neighbors
    [[1, 2], [4, 2]], // Node 2 neighbors
    [[5, 3]],         // Node 3 neighbors
    [[3, 3], [5, 1]], // Node 4 neighbors
    []                // Node 5 neighbors
];
// Note: This graph differs slightly from the one in the diagram to show more interesting paths.

const shortest_distances = dijkstra(adj, V, src);
console.log(shortest_distances); // Expected output would show shortest distances from node 0

Complexity and a Critical Limitation

• Time Complexity: With an adjacency list and a min-heap, the complexity is $O((E+V)\log V)$. Each vertex is extracted from the heap once ($O(V\log V)$), and for every edge, we might perform an update, which also takes logarithmic time ($O(E\log V)$).
• Space Complexity: $O(V+E)$ to store the adjacency list, the distance array, and the priority queue (which can hold up to $V$ vertices in some cases, or $E$ entries if duplicates are added before being processed).

Important Limitation: No Negative Weights!

Dijkstra's greedy strategy relies on a key assumption: once we select a node u from the priority queue, we have found the absolute shortest path to it, and its distance will never be updated again. This holds true only if all edge weights are non-negative. If a negative edge existed, we might later discover a "shortcut" through it that leads to a shorter path to u after we've already finalized it. For graphs with negative edges, other algorithms like Bellman-Ford are required.

Conclusion

Congratulations on completing the Graph Traversal module! You have now added Dijkstra's algorithm, a cornerstone of algorithmic problem-solving, to your toolkit. It's a powerful and efficient method for finding shortest paths, with direct applications in everything from network routing to GPS navigation.

Key Takeaways:

• Purpose: Dijkstra's algorithm finds the single-source shortest paths in a weighted graph with non-negative edge weights.
• Core Logic: It is a greedy algorithm that iteratively explores the unvisited node with the smallest known distance from the source.
• Key Data Structures: Its efficiency hinges on using a min-heap (priority queue) to quickly select the next node to visit. It also requires an array to store the current shortest distance estimates.
• The "Relaxation" Step: The core update rule is if (dist[u] + weight(u, v) < dist[v]), which updates the path to a neighbor v if a shorter route via u is found.
• Constraint: The algorithm only guarantees correctness for graphs with non-negative edge weights.

This lesson serves as a perfect bridge to our next module, "Greedy Decisions." Dijkstra's algorithm is a prime example of a greedy strategy that works. In our next lesson, we will step back and look at the general principles of greedy algorithms: how to identify when a greedy choice might be safe and how to construct arguments to validate (or refute) a greedy approach.