Dijkstra's Algorithm on LeetCode — Problems, Patterns, and Implementation

Dijkstra's algorithm solves the single-source shortest-path problem on weighted graphs with non-negative edge weights. It runs in O((V+E) log V) time with a min-heap and is the workhorse behind dozens of LeetCode problems.

The key insight: always process the unvisited node with the currently known smallest distance first. This greedy choice is correct because with non-negative weights, the shortest known path to a node cannot be improved by going through a longer detour.

On LeetCode, Dijkstra problems are almost never labeled as 'Dijkstra' — they appear as 'minimum cost', 'shortest time', 'network delay', requiring pattern recognition. Once you see a weighted graph with a single source and a 'find minimum' goal, Dijkstra is almost always the right tool.

Dijkstra appears disguised in many forms: Network Delay Time (#743), Cheapest Flights Within K Stops (#787), Path With Minimum Effort (#1631), Swim in Rising Water (#778), Find the City With the Smallest Number of Neighbors (#1334). They are all the same algorithm.

The canonical Dijkstra implementation on LeetCode uses Python's heapq module. The 5-step pattern is: (1) initialize distances to infinity, set source to 0; (2) push (distance=0, source) onto the min-heap; (3) pop the minimum-distance node; (4) skip if already visited; (5) relax all neighbors and push better paths.

Here is the template in Python: dist = {node: float("inf") for node in graph}. dist[src] = 0. heap = [(0, src)]. visited = set(). While heap: d, u = heapq.heappop(heap). If u in visited: continue. visited.add(u). For each neighbor v with edge weight w: if dist[u] + w < dist[v]: dist[v] = dist[u] + w. heapq.heappush(heap, (dist[v], v)).

The visited set is the critical optimization that prevents reprocessing. When a node is popped from the heap, it already has its final shortest distance — any future pops for the same node will be with equal or larger distances and can be safely skipped.

The heap may contain multiple entries for the same node from different relaxation attempts. The visited check handles this: the first time a node is popped it has the shortest distance, and all subsequent pops are stale and discarded. This is why the visited set works correctly even when the heap has duplicates.

Dijkstra's algorithm runs in O((V+E) log V) time using a min-heap — 100x faster than Bellman-Ford's O(VE) for typical interview graph sizes, but fails when edge weights are negative.

Three signal words reliably indicate Dijkstra: "minimum cost path", "shortest time", and "cheapest route". When you see these combined with a weighted graph and a single source, reach for Dijkstra immediately.

Feature checklist for a Dijkstra problem: (1) weighted edges — each connection has a cost or time; (2) single source — you start at one specific node; (3) no negative weights — all edge weights are zero or positive; (4) optimize over all paths — find the minimum total cost to reach each node or a specific target.

Grid problems are a common disguise. When a grid has cells with varying costs or heights, treat each cell as a graph node with 4-directional neighbors. Path With Minimum Effort and Swim in Rising Water both fall into this category — they look like BFS grid problems but require Dijkstra because movement costs are non-uniform.

State-space Dijkstra is another variant. Cheapest Flights Within K Stops adds a hops dimension to the state. Instead of (distance, node), the heap stores (distance, node, hops_remaining). This is still Dijkstra — just on a larger state graph where the same physical node can be visited multiple times with different hop counts.

Network Delay Time (#743): Given n nodes and weighted directed edges (travel times), find the minimum time for all nodes to receive a signal from node k. This is textbook Dijkstra — run from source k and return the maximum distance across all nodes. If any node is unreachable, return -1. Time complexity: O((V+E) log V).

Cheapest Flights Within K Stops (#787): Find the cheapest price from src to dst with at most K stops. Standard Dijkstra greedily finalizes nodes by minimum cost, but the K-stop constraint means a cheaper-cost path might use too many hops. Use Bellman-Ford with K+1 relaxation rounds, or Dijkstra with state (cost, node, stops_used) where the visited set keys on (node, stops_used).

Path With Minimum Effort (#1631): In a 2D grid, find a path from top-left to bottom-right minimizing the maximum absolute difference between adjacent cells on the path. Model as Dijkstra where dist[r][c] is the minimum possible maximum effort to reach cell (r,c). Edge weight between adjacent cells is abs(height[r1][c1] - height[r2][c2]).

Swim in Rising Water (#778): Find the minimum time T such that a path from (0,0) to (n-1,n-1) exists where every cell has elevation at most T. Use Dijkstra where the cost to reach a cell is max(cost_to_previous_cell, grid[r][c]). The heap tuple is (max_elevation_so_far, row, col).

Find the City With Smallest Number of Neighbors (#1334): Find the city with the fewest other cities reachable within a distance threshold. Run Dijkstra from each city and count reachable cities within the threshold. For n up to 100, Floyd-Warshall is simpler; for larger n, prefer Dijkstra from each source in O(n * (V+E) log V).

Dijkstra with state extends the node identity to include extra state variables. For Cheapest Flights K Stops, the state is (cost, node, stops_used). Two entries for the same physical node with different stops_used are different states. This prevents the visited set from incorrectly blocking paths that are cheaper overall but use fewer hops.

Dijkstra on grids replaces the adjacency list with 4-directional neighbor expansion. The heap entry is (cost, row, col). Edge weights between cells can be fixed (BFS if weight=1), variable (standard Dijkstra), or max-based (Swim in Rising Water pattern). The visited set becomes a 2D boolean grid.

Bidirectional Dijkstra runs forward from source and backward from destination simultaneously, stopping when the two search frontiers meet. It reduces search space from O(b^d) to O(b^(d/2)). It is used in production routing systems but rarely appears in LeetCode problems — know it exists for system design and follow-up interview questions.

Modified cost functions: sometimes Dijkstra combines with other constraints. For example, minimizing fuel cost with refueling at nodes, or finding paths where cost is the product of edge weights rather than the sum. The key question is always: what does "distance" mean in this problem? The answer defines the heap tuple and the relaxation condition.

Dijkstra is the right choice when: all edge weights are non-negative, you need single-source shortest paths, and performance matters. At O((V+E) log V) it handles graphs with hundreds of thousands of nodes efficiently.

Bellman-Ford is the right choice when: edge weights can be negative, you need to detect negative cycles, or the problem specifies a fixed number of relaxation rounds (like K stops in Cheapest Flights). It runs in O(VE) — acceptable for small graphs (n <= 100) but too slow for large ones.

The classic interview follow-up is: 'What if some edge weights are negative?' Your answer: Dijkstra fails with negative weights because a shorter path through a negative edge can invalidate a previously finalized shortest distance. Switch to Bellman-Ford, which handles negatives by relaxing all edges V-1 times and can detect negative-weight cycles on the V-th pass.

SPFA (Shortest Path Faster Algorithm) is a queue-optimized Bellman-Ford that processes only nodes whose distances changed. Average case is much faster than O(VE), but worst case is still O(VE). It appears in competitive programming but is not commonly required in interviews.

Summary: for 99% of LeetCode shortest-path problems, non-negative weights are guaranteed and Dijkstra is correct. Bellman-Ford is the fallback when negatives appear. Floyd-Warshall handles all-pairs shortest paths on dense graphs in O(V^3) and is practical for n <= 100.

Dijkstra's algorithm is one of the highest-ROI patterns for LeetCode interviews. It appears in 10+ problems under different names — Network Delay Time, Cheapest Flights, Path With Minimum Effort, Swim in Rising Water, Find the City, and more. They are all the same 5-step min-heap pattern.

The key skill is recognition. When you see weighted graph + single source + minimize total cost, your instinct should immediately go to Dijkstra. When you see extra constraints like K stops, layer state into the heap tuple. When you see a grid with non-uniform movement costs, treat it as a graph.

Practice the 5-step template until it is automatic: (1) init distances to infinity, (2) push source with distance 0, (3) pop minimum, (4) skip visited, (5) relax neighbors. You should produce a working Dijkstra in under 3 minutes from memory during an interview.

Use YeetCode's spaced repetition flashcards to drill Dijkstra problems systematically. The platform surfaces the problems you are weakest on and spaces repetitions for maximum retention. After 5-7 focused sessions with Network Delay, Cheapest Flights, and Path With Minimum Effort, the pattern becomes automatic — you stop thinking about implementation and start thinking about the problem.