Dijkstra's Algorithm for Shortest Paths

Recommended resources

The freely available resources this lesson will direct you to.

Hello! In our last lesson, we built a solid implementation of Dijkstra's algorithm, focusing on its greedy logic and the crucial role of the min-heap for efficiency. You now have a robust template for finding the shortest paths from a single source in a standard, weighted graph.

Today, we'll expand on that foundation to see just how versatile this algorithm is. Our goal is to apply Dijkstra's algorithm to solve shortest path problems on both explicit and implicit graphs. We'll start with a classic interview problem on an "explicit" graph, where nodes and edges are given directly. Then, we'll tackle a more nuanced problem on an "implicit" grid-based graph, where you must derive the structure on the fly. This will train you to recognize the underlying pattern even when the problem doesn't look like a standard graph traversal at first glance.

Application 1: Explicit Graphs

An explicit graph is one where the structure (vertices and edges) is clearly defined in the problem input, typically as an edge list or adjacency matrix. Many LeetCode problems fall into this category. A canonical example is "Network Delay Time," where you need to find the time it takes for a signal to reach every node from a single source. This is a direct application of Dijkstra's algorithm.

Before looking at the specific problem, let's watch a concise review of the implementation pattern.

Implement Dijkstra's Algorithm

This NeetCodeIO video walks through implementing Dijkstra's algorithm from scratch for a typical interview problem. It reinforces the pattern we learned in the last lesson.

Watch from the beginning up to the final loop. Pay attention to these key steps: Building the adjacency list from the input edge list. Initializing the data structures: a shortest path dictionary (or array) and the min-heap with the source node. The main loop logic: popping, checking for visited nodes, and relaxing edges. Notice the "stale entry" check is done by seeing if the node is already in the shortest map.

Now, let's see this pattern applied to the "Network Delay Time" problem.

Dijkstra's Shortest Path Algorithm – Tech Interview Dot Org

This section of the article from Tech Interview Dot Org provides a full solution to the "Network Delay Time" problem (LeetCode 743).

Please read the section titled "Complete Example". Compare this code to the general template we've just reviewed. You'll notice it's almost identical. The main additions are: The graph is 1-indexed, so the distance map is initialized accordingly. After Dijkstra's runs, there's a final step to find the max() of all shortest path distances and check if any node is unreachable (inf).

As you can see, for explicit graphs, the process is straightforward:

Parse the input to build an adjacency list.
Apply the standard Dijkstra's implementation you learned.
Add any problem-specific logic to interpret the final distances map.

Application 2: Implicit Graphs (Grids)

The real power of Dijkstra's algorithm becomes apparent when applied to implicit graphs. These are graphs where the nodes and edges are not explicitly provided but are defined by a set of rules. A 2D grid is a perfect example.

Two examples of pathfinding on a grid. In Case I, cells are nodes and blocked cells are obstacles. In Case II, walls between cells define connectivity. In both cases, the graph is implicitly defined by the grid's rules.

In a grid:

Nodes are the cells, identified by their coordinates (row, col).
Edges connect adjacent cells (e.g., up, down, left, right).
Edge Weights are determined by the problem's constraints (e.g., the cost to move between cells).

You don't build an adjacency list upfront. Instead, you generate a node's neighbors on-the-fly as you explore. A fascinating real-world application of this is modeling tsunami propagation, where ocean depth data on a grid is used to calculate travel times.

Dijkstra's Algorithm - ACME Labs

This article from ACME Labs explains how bathymetric (ocean depth) data can be modeled as an implicit grid graph to predict tsunami travel times.

Focus on the conceptual explanation. Read these sections to understand how a grid becomes a graph: Tsunami Prediction: Introduces the problem. The TsunamiModel Class: Explains how each data point in the grid is a node. Modeling with a Grid: This is the key part. It describes how neighbors are defined (orthogonally adjacent cells) and how edge weights (travel time) are calculated based on the ocean depth values in the cells.

Modified Dijkstra's: Path with Minimum Effort

Let's tackle a concrete LeetCode problem that uses this idea: "Path with Minimum Effort" (LeetCode 1631). The goal is to find a path from the top-left to the bottom-right of a grid of heights, such that the maximum absolute difference in height between any two consecutive cells on the path is minimized.

This is a shortest path problem, but the "cost" isn't a sum. The "cost" of a path is its single largest edge weight. We can still use Dijkstra's, but we need to modify what we store in the heap and how we perform relaxation.

The state in our min-heap will be (effort, row, col), where effort is the maximum effort seen so far on the path to (row, col).

Watch this video for a clear, step-by-step walkthrough of the logic and implementation.

Path with Minimum Effort - Leetcode 1631 - Python

NeetCodeIO provides an excellent explanation of how to adapt Dijkstra's algorithm for the "Path with Minimum Effort" problem.

Please watch the entire video. Focus on these critical points: The logical walkthrough: Notice how the greedy choice is always the path with the current minimum effort. This is the core idea of using a min-heap. The min-heap initialization: The heap stores (effort, row, col). The starting state is (0, 0, 0). Generating neighbors: Instead of an adjacency list, a directions array is used to find adjacent cells, with checks for out-of-bounds. The modified relaxation step: This is the most important part. The new_diff for a neighbor is the max() of the current_diff and the effort of the new step. This ensures we are always tracking the maximum effort along the entire path.

The key insight is that because the min-heap always gives us the path with the overall minimum effort so far, the very first time we reach the destination cell, we are guaranteed to have found the optimal path. Any other path that reaches the destination later must have had a higher-effort step somewhere along the way.

Here is the implementation from the Tech Interview Dot Org article, which you can use as a reference. It mirrors the logic from the video.

Dijkstra's Shortest Path Algorithm – Tech Interview Dot Org

This resource provides a concise Python implementation for the "Path With Minimum Effort" problem.

Read the code block under the heading "Path With Minimum Effort". Compare it with the standard Dijkstra template. Identify the three key changes: The state in the heap is (effort, r, c). Neighbors are generated using a directions array. The relaxation step calculates new_effort using max(effort, abs(height_diff)).

Conclusion

In this lesson, we saw how the core Dijkstra's pattern—a greedy search guided by a min-heap—can be adapted to solve a variety of shortest path problems. The main distinction is whether the graph is explicit or implicit.

Key Takeaways:

Explicit Graphs: For problems with a given edge list (like "Network Delay Time"), the strategy is to first build an adjacency list and then apply the standard Dijkstra's algorithm.
Implicit Graphs: For problems on grids or other rule-based structures (like "Path with Minimum Effort"), the graph is not pre-built. Instead, neighbors and edge weights are calculated on-the-fly within the main loop.
Flexible "Cost": The "distance" or "cost" minimized by Dijkstra's does not have to be a simple sum. By changing the relaxation logic, it can represent other metrics, like the maximum edge weight on a path.
The Pattern: Regardless of the graph type, the core components remain: a min-heap to store (cost, node), a distances structure to track shortest paths, and a loop that greedily processes the node with the lowest cost.

In our next lesson, we will explore a different class of graph problems by looking at Minimum Spanning Tree (MST) algorithms. While Dijkstra's finds the shortest path between nodes, MST algorithms like Prim's and Kruskal's focus on finding the cheapest way to connect all nodes in a graph. Understanding this distinction is crucial for selecting the right tool for the job.