Dijkstra's Algorithm for LeetCode: Shortest Path Guide

When a LeetCode problem says "find the shortest path" and the edges have weights, Dijkstra's algorithm is almost always the answer. It is the single most important algorithm to know for weighted graph problems in coding interviews, and it appears far more frequently than most candidates expect.

Unlike BFS, which only works when every edge has the same cost, Dijkstra's handles arbitrary non-negative edge weights. This makes it the go-to tool for problems involving travel costs, network latencies, minimum effort paths, and any scenario where different edges carry different prices. If you can recognize the pattern, you can apply the same template to a wide range of problems.

The core idea is elegant: maintain a priority queue of (distance, node) pairs, always process the closest unvisited node first, and update distances to its neighbors. This greedy approach guarantees that once you pop a node from the queue, you have found the shortest path to it. The rest is implementation detail — and that is exactly what this guide covers.

The decision between BFS and Dijkstra comes down to one question: are all edge weights equal? If yes, BFS finds the shortest path in O(V + E) time. If edges have different non-negative weights, you need Dijkstra's algorithm.

BFS works for unweighted shortest paths because processing nodes level by level guarantees that the first time you reach a node, you have taken the fewest edges to get there. But when edges have different costs, the fewest edges does not mean the lowest total cost. A path with three cheap edges might beat a path with one expensive edge.

Here is the decision framework you should use in interviews. If the problem says "minimum number of steps" or "fewest moves" with uniform cost, use BFS. If it says "minimum cost," "shortest distance," or "minimum effort" with varying weights, use Dijkstra. If negative weights are involved, neither works — you need Bellman-Ford.

Dijkstra's algorithm maintains a dist[] array where dist[node] represents the shortest known distance from the source to that node. Initially, dist[source] = 0 and all other distances are infinity. A min-heap (priority queue) stores (distance, node) pairs, starting with (0, source).

At each step, you pop the pair with the smallest distance from the heap. If this distance is greater than the currently known shortest distance to that node, skip it — this is the lazy deletion optimization that avoids the need to decrease-key. Otherwise, examine each neighbor: if the current distance plus the edge weight is less than the neighbor's known distance, update it and push the new pair onto the heap.

This process continues until the heap is empty or you have reached your target node. The greedy property of always processing the closest node first guarantees correctness for non-negative edge weights. Once a node is popped from the priority queue, its distance is finalized — no future path through other nodes can be shorter.

The time complexity is O((V + E) log V) when using a binary heap. The log V factor comes from heap insertions and extractions. For dense graphs, an O(V^2) implementation with a simple array can actually be faster, but the heap-based version is what you should use in interviews because it handles sparse graphs well and is more natural to implement.

Every Dijkstra problem follows the same skeleton. First, build an adjacency list from the input. Second, initialize a dist[] array with infinity values and set the source distance to 0. Third, push (0, source) onto a min-heap. Fourth, run the relaxation loop until the heap is empty.

The adjacency list maps each node to a list of (neighbor, weight) pairs. In Python, use a defaultdict of lists. In JavaScript or TypeScript, use a Map or plain object. The dist[] array can be a simple array for numbered nodes or a Map for arbitrary node identifiers.

The relaxation loop is the heart of Dijkstra. For each (distance, node) pair popped from the heap, check if distance > dist[node]. If so, skip it — you have already found a shorter path. Otherwise, for each neighbor of node, calculate new_dist = distance + weight. If new_dist < dist[neighbor], update dist[neighbor] = new_dist and push (new_dist, neighbor) onto the heap.

This template handles the vast majority of dijkstra leetcode problems. The only variations involve what you track in the state (adding constraints like remaining stops), how you define neighbors (grid cells instead of graph nodes), or what you return at the end (max distance, specific target distance, or a boolean).

Network Delay Time (LeetCode #743) is the purest dijkstra algorithm leetcode problem. You are given a weighted directed graph, a source node, and asked to find the time it takes for a signal to reach all nodes. The answer is simply: run Dijkstra from the source and return the maximum value in the dist[] array. If any node is unreachable, return -1. This is the ideal first problem to practice the template.

Cheapest Flights Within K Stops (LeetCode #787) adds a constraint: you must find the cheapest path using at most K intermediate stops. Standard Dijkstra does not track stops, so you modify the state to (cost, node, stops_remaining). Instead of a single dist[] array, you need to track the best cost for each (node, stops) combination. This is a common variation that tests whether you understand how to extend the basic algorithm.

Path With Minimum Effort (LeetCode #1631) applies Dijkstra to a grid. The cost of a path is the maximum absolute difference in heights between adjacent cells. You want to minimize this maximum difference. The key insight is that this is still a shortest path problem — the "distance" is the max effort so far, and you use Dijkstra with the state (effort, row, col) to find the path with minimum maximum effort.

Swim in Rising Water (LeetCode #778) is similar to #1631. You need to find the minimum time to swim from the top-left to the bottom-right of a grid, where the time determines the water level. Each cell has an elevation, and you can only enter a cell when the water level equals or exceeds its elevation. Dijkstra finds the path where the maximum elevation is minimized.

The most dangerous mistake is using Dijkstra with negative edge weights. Dijkstra assumes that once a node is finalized (popped from the heap), no shorter path exists. Negative edges violate this assumption because a longer path through a negative edge could end up shorter. If your problem has negative weights, switch to Bellman-Ford immediately.

The second common mistake is not implementing lazy deletion. Without it, you might process the same node multiple times at outdated distances, leading to incorrect results or TLE. Always check if the popped distance exceeds dist[node] before processing — this single line eliminates redundant work and is essential for correctness.

Another frequent error is confusing the state. In problems like Cheapest Flights Within K Stops, your dist[] key must include the constraint (node + stops remaining), not just the node. If you only track dist[node], you might prune a path that uses more stops but leads to a cheaper overall result. When modifying Dijkstra, think carefully about what constitutes a unique state.

Finally, watch out for integer overflow when initializing distances to infinity. In Python this is not an issue thanks to arbitrary precision, but in Java or C++ you should use Integer.MAX_VALUE or INT_MAX carefully. Adding a weight to MAX_VALUE overflows. Use a large constant like 1e9 or check before adding.

Start with Network Delay Time (LeetCode #743). It is the purest Dijkstra problem — no modifications, no extra constraints, just run the algorithm and return a result. Use this problem to get your template working perfectly and committed to memory. Once you can write it without referencing anything, move on.

Next, tackle Cheapest Flights Within K Stops (LeetCode #787). This forces you to modify the state tuple and understand when standard Dijkstra is not enough. It bridges the gap between template application and creative adaptation. After that, try Path With Minimum Effort (#1631) to see Dijkstra on grids, and Swim in Rising Water (#778) for another grid variation.

For each problem, practice explaining your approach out loud before coding. In interviews, the algorithm choice and justification matter as much as the implementation. Say why Dijkstra applies (weighted, non-negative, shortest path), mention the time complexity, and describe what your state represents. This builds the communication skills that separate strong candidates from those who can only code silently.

Use YeetCode flashcards to drill the pattern recognition layer. When you see a problem description, you should instantly know whether it is a Dijkstra problem, a BFS problem, or something else entirely. Spaced repetition builds this intuition faster than grinding problems sequentially, because it forces you to recall the decision framework — not just the implementation — at increasing intervals.