Dijkstra Shortest Path

Imagine you are planning a trip and need to find the fastest way to drive from your home to a friend's house, or the cheapest way to ship a package across several cities. Dijkstra’s algorithm is the logic that makes this possible. It answers the question: "What is the best route among all possible routes?" This is worth learning because it solves a problem you encounter in daily life—getting from point A to point B efficiently—and it teaches you how computers make smart choices instead of checking every single possibility blindly.

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.

Dijkstra's algorithm is a step-by-step method for finding the path with the lowest total cost between two points in a network, where every connection has a positive cost, by always moving to the nearest unvisited point next. It works by keeping track of the shortest known distance to each point and expanding outward from the start to the closest unknown point.

This sits beside Breadth-First Search, which also finds paths but assumes every step costs exactly the same, like moving through a grid where you can only move up, down, left, or right. Dijkstra is needed when steps have different costs, like driving on roads of different lengths.