Dijkstra's Algorithm

Dijkstra's algorithm is a recipe for finding the cheapest route from a starting point to every other point in a network, where each hop between points has a cost — like distance, time, or energy. Picture a subway map where each segment between stations is labelled with how many minutes it takes. Dijkstra's algorithm works out the fastest total trip from your home station to any destination, not by guessing, but by patiently spreading outward from the start the way water floods a valley: it always commits next to the nearest place it has not yet settled, so the first time it settles a station, it already knows that is the quickest possible way to get there.

Here is the trick that makes it reliable. The algorithm keeps a running best-known cost to reach every point, starting at zero for the home point and 'unknown' everywhere else. It repeatedly picks the unsettled point with the smallest known cost, marks it final, and then looks at its neighbours: if going through this point gives a cheaper way to reach a neighbour than any found before, it writes down that lower cost. Because it always settles the cheapest-so-far point next, and the costs can never be negative, no later discovery can ever beat a point it has already locked in. When it finishes, the shortest path to the goal can be traced back step by step.

In robot path planning, the 'points' are squares in a grid map or nodes in a graph of possible places the robot can stand, and the 'costs' are how hard or risky it is to travel between them. Dijkstra guarantees the genuinely shortest or lowest-cost path, which is its great strength. Its weakness is that it explores in every direction equally, with no sense of where the goal lies, so it can waste effort searching far from the target — the very problem that the A* search algorithm fixes by adding a hint about which way to head.