Dijkstra Shortest Path

This is the algorithm behind GPS navigation, network routing, and many AI planning systems. If you go on to study Graph Neural Networks or Knowledge Graphs, or if you ever build an agent that plans a route through a set of tasks, Dijkstra's algorithm is the foundation. It also gives you your first real taste of efficiency — how a smart choice of data structure can turn a slow search into a fast one. For an AI practitioner, understanding Dijkstra teaches you how 'shortest path' problems are solved, and it introduces the idea of a priority queue, which shows up again in other algorithms and in how some AI systems schedule their work.

Suppose you are in a city you have never visited, and you need to find the shortest driving distance from your hotel to a restaurant. You do not have a map with distances, but you can ask people on the street how far it is from one intersection to the next. You know the hotel's address. You also know the restaurant's address. How would you find the shortest path? You might start by asking how far it is from the hotel to each of the roads that connect to it. Then you go to the nearest of those intersections, and you ask how far it is to its neighbours. You keep track of how far you have travelled to reach each intersection so far. If you reach an intersection by a route that is longer than one you already found, you ignore it. You keep doing this, always going to the closest intersection you have not yet fully explored, until you reach the restaurant. That is Dijkstra's algorithm. It does not look at every possible route; it methodically expands from the start, one step at a time, always taking the closest unexplored point. The clever part is that it never needs to revisit a decision it has already made. Once it has settled on the shortest distance to a place, it is done with that place, because any longer route to the same place is pointless. So it works by keeping a running list of the best-known distances to every place it has seen, and it always works on the place with the smallest current distance.

Think of a flood of water spreading from the source. When you throw a stone into a still pond, the ripples spread out in concentric circles — the wave reaches all points at the same distance at the same time. Now imagine the pond is not flat but has channels of different widths, or even small walls that slow the water down. In that case, the water does not advance in a perfect circle. It flows faster through wide channels and slower through narrow ones. The water reaches a point when it has found the path that offers the least resistance, not the shortest straight line. Dijkstra's algorithm is like watching the water flow, but instead of water, it keeps a number — the total distance travelled so far. At any moment, it knows the minimum distance to every point it has reached, and it always expands the point with the smallest distance next. That is exactly what water does: it surges forward along the path of least total resistance. Where the analogy breaks down: water spreads continuously in all directions, while the algorithm only considers the discrete points (intersections) where distances are known. Also, water does not 'remember' which path it took; the algorithm can reconstruct the actual path at the end. And water cannot handle negative slopes — if going downhill shortens the distance, the water would keep moving forever. Dijkstra similarly cannot handle negative edge weights, because it would break the assumption that once you settle a distance, you are done.

Dijkstra's algorithm is a method for finding the shortest path from a starting node to every other node in a graph where every edge has a non-negative weight (like distance, time, or cost), by repeatedly selecting the unvisited node with the smallest known distance, updating the distances of its neighbours, and marking it visited.

You already have notes on Graph Traversal BFS and DFS. BFS finds shortest paths in unweighted graphs — a graph where each edge costs the same, like 1. Dijkstra is the generalisation: it handles graphs where edges have different weights (like roads with different lengths). The key idea of a 'frontier' — a set of nodes at the edge of the explored region — is shared, but where BFS expands level by level (all nodes at distance 1, then all at distance 2), Dijkstra expands in order of increasing distance, which may not line up with neat levels. This connects to your notes on Heaps and Priority Queues, because the priority queue is what makes the repeated 'find the closest unvisited node' step fast. It also connects to the idea of Loop Invariants and Proof by Induction — the correctness of Dijkstra is often proved by induction on the number of nodes marked visited. And it is a stepping stone to A*, which adds a heuristic to guide the search toward a specific target.