Graph Theory: Shortest Paths with Dijkstra & A* Search

In 1956, twenty-six-year-old Dutch computer scientist Edsger W. Dijkstra was out shopping with his fiancée in Amsterdam. Pausing at a café terrace, he wondered: What is the fastest, cleanest way to calculate the shortest driving route between two cities on a map of the Netherlands?

Without pen or paper, in less than twenty minutes of mental concentration, Dijkstra designed the algorithm that would become the foundation of modern digital transit: Dijkstra’s Shortest Path Algorithm.

Today, from satellite GPS navigation and Amazon warehouse robots to fiber optic packet routing and game AI pathfinding, finding the optimal path through a weighted network remains one of the most vital algorithmic problems in computer science.

1. Dijkstra’s Algorithm: Uniform Radial Search

Dijkstra’s algorithm operates on a simple, greedy principle: maintain a set of tentative distances $d[v]$ for every vertex, initialized to $\infty$ (with $d[\text{start}] = 0$).

At each step:

1. Extract the unvisited vertex $u$ with the minimum tentative distance from a Priority Queue.
2. For each neighbor $v$ of $u$, perform relaxation: \(\text{if } d[u] + w(u, v) < d[v] \implies d[v] = d[u] + w(u, v)\)
3. Mark $u$ as visited. Repeat until the target vertex is reached.

 Algorithm Complexity (Binary Heap):
 Time:   O((|V| + |E|) log |V|)
 Space:  O(|V|)

The Blindspot of Dijkstra

Dijkstra’s algorithm is completely unbiased. Because it has no concept of where the target lies in physical space, it expands outwards uniformly in all directions like an expanding circle of water ripples. If the target is due East, Dijkstra will waste thousands of operations exploring uselessly to the North, South, and West before stumbling upon the destination!

2. A* Search: Directed Heuristic Intelligence

In 1968, Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute were developing Shakey the Robot—the world’s first mobile, intelligent robot. Shakey needed to navigate obstacle-strewn rooms in real-time, but Dijkstra was too slow.

They augmented Dijkstra by adding a heuristic function $h(n)$, giving birth to A* Search:

Where:

• $g(n)$ is the exact, known cost incurred so far from the start node to node $n$.
• $h(n)$ is the estimated heuristic distance from node $n$ to the destination target.
• $f(n)$ is the total estimated cost of the cheapest solution passing through $n$.

           [ Start ]
              |
              |   g(n): Exact cost traveled so far
              v
           [ Node n ]
              :
              :   h(n): Estimated straight-line heuristic distance
              v
           [ Goal ]

On a 2D grid, we frequently use the Manhattan Distance ($L_1$ norm) or Euclidean Distance ($L_2$ norm):

Because $h(n)$ pulls the priority queue toward the goal, A* focuses its search into a directed beam, cutting the number of explored nodes by up to 80% while guaranteeing the exact same shortest path!

3. Comparing Algorithm Performance