Dijkstra's Algorithm: Finding the Shortest Path

1. The Core Idea: A Greedy Approach

Dijkstra's algorithm is a greedy algorithm. At each step, it makes a locally optimal choice: it always visits the "closest" unvisited node from the source. This greedy strategy works because all edge weights are non-negative, guaranteeing that once we finalize the shortest path to a node, we'll never find a shorter one later.

The algorithm maintains a set of tentative distances from the source to every other node. Initially, the source's distance is 0, and all others are infinity. The core operation is called relaxation:

1. Select the unvisited node u with the smallest known distance from the source.
2. For each neighbor v of u, check if the path through u is shorter than the currently known path to v.
3. If distance(source, u) + weight(u, v) < distance(source, v), we update distance(source, v).

To see this process in action, let's watch a classic conceptual explanation.

As the video explains, a straightforward implementation of this logic involves scanning all nodes at each step to find the one with the minimum distance. This leads to a time complexity of $O(V^2)$, where $V$ is the number of vertices. For your interviews, you'll be expected to know a more efficient approach.

2. An Efficient Implementation with a Priority Queue

To optimize the process of finding the unvisited node with the minimum distance, we can use a priority queue (or a min-heap). Your experience with Python's heapq module will be useful here.

Here's how the data structures work together:

• A distance array (or dictionary), dist, stores the shortest distance from the source to every other node found so far. It's initialized to infinity for all nodes except the source (which is 0).
• A priority queue, pq, stores (distance, node) tuples. It allows us to fetch the node with the smallest current distance in $O(\log V)$ time, which is much better than the $O(V)$ scan of the naive approach.

This video from "take U forward" demonstrates this efficient, heap-based implementation, which is the standard for modern applications and interviews.

With this optimized approach, the time complexity improves significantly to $O(E\log V)$, where $E$ is the number of edges. This is because we process each edge once, and each push/pop operation on the heap takes $O(\log V)$ time.

3. Python Implementation Template

Now, let's translate this logic into a clean Python template, which is exactly what you'd want to have ready for an interview. The following reading provides an excellent, reusable code snippet and a step-by-step breakdown.

Here is the core logic from the article, which you should aim to understand deeply:

import heapq

def dijkstra_adj_list(n, graph, start):
    # 1. Initialize distances and the priority queue
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)

    while pq:
        # 2. Get the node with the smallest distance
        d, u = heapq.heappop(pq)

        # 3. Skip if we've already found a shorter path to u
        if d > dist[u]:
            continue

        # 4. Relax all neighbors of u
        for v, w in graph[u]: # v = neighbor, w = weight
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist

The line if d > dist[u]: continue is a crucial optimization. Since a priority queue can contain multiple entries for the same node with different (outdated) distances, this check ensures we only process a node using its shortest path found so far.

4. A Critical Limitation: Negative Weights

Dijkstra's greedy approach relies on a key assumption: adding an edge never makes a path shorter (since weights are non-negative). If a graph has a negative edge weight, this assumption breaks. The algorithm might prematurely finalize a path to a node, only to later discover a "cheaper" path that uses a negative edge.

For graphs with negative weights, other algorithms like the Bellman-Ford algorithm must be used. We won't cover Bellman-Ford in this lesson, but it's important to know when Dijkstra's is not the right tool for the job.

5. Reconstructing the Shortest Path

Dijkstra's algorithm gives you the length of the shortest path, but often you need the path itself. This is a common follow-up question in interviews. You can find the path by storing the "predecessor" of each node—the node that came just before it on the shortest path.

You can modify the algorithm to do this:

1. Create a predecessors dictionary, initialized to None.
2. Inside the relaxation step, when you update dist[v], also update predecessors[v] = u.
3. After the algorithm finishes, you can backtrack from the target node to the source using the predecessors dictionary to reconstruct the path.

Conclusion

You have now mastered one of the most important algorithms for your interview toolkit. Dijkstra's algorithm is the definitive method for finding the shortest path in graphs with non-negative weights, a problem that appears in many forms.

Key Takeaways:

• Dijkstra's Algorithm finds the single-source shortest path in a weighted graph with non-negative edge weights.
• It is a greedy algorithm that iteratively finalizes the shortest path to the closest nodes.
• The efficient interview-standard implementation uses a priority queue (min-heap) to achieve a time complexity of $O(E\log V)$.
• The core steps are: initialize distances, loop while the priority queue is not empty, pop the minimum distance node, and relax its neighbors.
• Limitation: Dijkstra's fails if the graph contains negative edge weights.
• The actual path can be reconstructed by storing predecessors during the relaxation step.

Preview of the Next Lesson:

Now that we have covered the fundamental graph traversal and shortest path algorithms (BFS, DFS, and Dijkstra's), we will move on to identifying more advanced graph properties. In the next lesson, you will learn how to detect cycles in both undirected and directed graphs using DFS. This is a crucial skill for a wide range of problems, from checking for deadlocks in systems to validating dependency graphs (like course prerequisites).