# Dijkstra Shortest Path

Finding shortest paths from a source in a graph with non-negative edge weights by repeatedly expanding the closest unvisited node.

**Rests on:** Graph Traversal BFS and DFS

*Mathematical Foundations · Graph Theory*


## Why learn this

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.


## The intuition

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.


## An analogy

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.


## Definition

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.


## How it connects

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.


## The mathematics

This concept draws on a branch of mathematics called graph theory, which is the study of objects called graphs — not the kind you draw for a function, but a set of points (called vertices or nodes) and the lines connecting them (called edges). Dijkstra's algorithm uses only arithmetic: addition and comparison of numbers. There is no algebra, no calculus. The operation at the heart of it is the repeated comparison of sums. The algorithm works like this.

You have a starting node. You assign a tentative distance to every node: zero for the start, and a very large number (say, infinity) for every other node, because you do not yet know how far away they are. You also keep a set of nodes whose shortest distance you have 'settled' — you know for sure. Initially, that set is empty.

Then you repeat the following steps.

First, among all nodes that are not yet settled, pick the one with the smallest tentative distance. That node is guaranteed to have its final, shortest distance — this is the core claim, and it is true because all edges have non-negative weights. Then, for each neighbour of that node, calculate a new tentative distance: the settled node's distance plus the weight of the edge to the neighbour. If that new value is smaller than the neighbour's current tentative distance, you update it. Finally, mark the settled node as visited.

You keep going until the set of unvisited nodes is empty, or until you have settled the target node if you only want one path. The algorithm is just this loop, repeated, and it always produces the correct shortest distances because of the non-negativity guarantee.

Let G be a graph with vertices V, edges E, and a weight function w that assigns a non-negative number to each edge. Let s be the source vertex. The algorithm maintains a set S of settled vertices and a distance array d for each vertex v. Initially, d[s] = 0 and d[v] = infinity for all v not equal to s. While S is not equal to V: 1. Pick u in V minus S with minimum d[u]. 2. Add u to S. 3. For each neighbour v of u: if d[u] + w(u,v) < d[v], then set d[v] = d[u] + w(u,v). The final d[v] is the shortest distance from s to v.


## A worked example

```
We have a small graph with 5 nodes: A (the start), B, C, D, and E. The edges and their weights are: A-B: 4, A-C: 2, B-C: 1, B-D: 5, C-D: 8, C-E: 10, D-E: 2. We want the shortest distance from A to every other node.

Step 1: Initial tentative distances: A=0, B=inf, C=inf, D=inf, E=inf. Settled set = {}.   # We start with the source at distance 0 and all others at infinity, meaning we have not reached them yet.
Step 2: Pick smallest unvisited: A (dist 0). Update neighbours: B=0+4=4, C=0+2=2. Settle A.   # A is the only node with distance 0, so it is chosen. Its neighbours get tentative distances.
Step 3: Pick smallest unvisited: C (dist 2). Update neighbours: B: 2+1=3 (less than 4, update B to 3), D: 2+8=10, E: 2+10=12. Settle C.   # C has the smallest tentative distance (2), so we are certain its final distance is 2. We relax its edges, improving B's distance from 4 to 3.
Step 4: Pick smallest unvisited: B (dist 3). Update neighbours: D: 3+5=8 (less than 10, update D to 8). Settle B.   # B is now the closest unvisited node. Its edge to D gives a better distance than the previous 10, so we update D.
Step 5: Pick smallest unvisited: D (dist 8). Update neighbours: E: 8+2=10 (less than 12, update E to 10). Settle D.   # D's distance is final at 8. Via D, E can be reached at distance 10, better than the previous 12.
Step 6: Pick smallest unvisited: E (dist 10). No neighbours to update. Settle E.   # E's distance is final. There are no other unvisited nodes, so we stop.

Result: Shortest distances from A: B=3 (path A-C-B), C=2 (path A-C), D=8 (path A-C-B-D), E=10 (path A-C-B-D-E). The algorithm correctly found that the path A-C-B (weight 2+1=3) is shorter than the direct edge A-B (weight 4).
```


## From scratch, in Python

```python
import heapq

def dijkstra(graph, start):
    # graph is a dictionary: {node: [(neighbor, weight), ...]}
    # distances will hold the shortest distance to each node.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # priority queue: a list of (distance, node) pairs.
    pq = [(0, start)]

    while pq:
        current_dist, current_node = heapq.heappop(pq)

        # If we have already found a shorter way, skip this entry.
        if current_dist > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# Example usage
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8), ('E', 10)],
    'D': [('E', 2)],
    'E': []
}
print(dijkstra(graph, 'A'))  # Output: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}
```


## What the code does

The code uses several building blocks you have not met before. First, a **dictionary** — a way to store values by a name, like a phone book. For example, `{'A': [('B', 4)]}` means 'from node A, you can go to node B with weight 4'. You look up a value with `graph['A']`, which returns a **list** of tuples — an ordered collection of items. Here each item is a tuple `(neighbor, weight)`, which is a pair of two values. The `for neighbor, weight in graph[current_node]:` loop goes through each of these tuples one by one, giving you the two values. The `heapq` module is a **priority queue** — a data structure that always lets you pop the smallest item. In the code, `heapq.heappop(pq)` removes and returns the tuple with the smallest distance. The `heappush` adds a new tuple. The `float('inf')` is Python's representation of infinity, used for the initial distances. The main loop: pop the closest node, check if it is still relevant (if we already found a shorter path, skip), then for each neighbour, calculate the new distance and update if it is shorter. That is exactly the steps from the numerical example. The `distances` dictionary will hold the final shortest distances.


## Common misconceptions

**Dijkstra can handle negative edge weights** — My graph has some edges with negative cost, but Dijkstra will still find the shortest path because it is a famous algorithm.

Dijkstra's correctness relies on the assumption that once a node is settled, its distance is final. With negative edges, a later path might decrease a settled distance, breaking the algorithm. In the numerical example, if edge C-B had weight -5, then after settling B at 3, you could go C to B at -3, which is less than 3. You would need to revisit B, but Dijkstra never does. In fact: Dijkstra only guarantees correctness for graphs with non-negative edge weights. For negative weights, use Bellman-Ford, which can handle them (though it is slower).

**Dijkstra finds the path to every node in one go** — The algorithm gives the shortest path to every node, and that includes the path itself, not just the distance.

Dijkstra as described computes distances, not the actual routes. You need to add a 'previous node' array to reconstruct the path. In fact: You can easily augment the algorithm to store the previous node for each node, and then backtrack from the target to the source to get the full path.

**The priority queue is optional** — Dijkstra can just scan all unvisited nodes each time to find the closest one. It is the same thing.

Scanning all unvisited nodes each iteration makes it O(V²) overall, which is fine for small graphs, but not for millions of nodes. A priority queue reduces this to about O(E log V), which is the difference between minutes and milliseconds on large road networks. In fact: The priority queue is the core data structure that makes Dijkstra efficient. It is not just an optimisation; it is the defining feature of the modern algorithm.

**Dijkstra is a greedy algorithm and does not always give the optimal solution** — Greedy algorithms make locally optimal choices and often fail, so Dijkstra must too sometimes.

Dijkstra is a greedy algorithm, but because edge weights are non-negative, the greedy choice of the closest unvisited node is provably always correct. This is a special case where greedy works. In fact: Dijkstra is a greedy algorithm that is guaranteed to give the optimal solution for non-negative edge weights. The proof relies on the fact that any alternative path to a settled node must have cost at least as high as the one found.

**Dijkstra works on undirected graphs, not directed** — I only learned Dijkstra on roads, which are two-way. If my graph has directed one-way edges, the algorithm is invalid.

Dijkstra works perfectly on directed graphs. The only difference is that when you relax the edges, you only consider edges going out of the settled node. It works on undirected graphs as a special case (each undirected edge is two directed edges). In fact: Dijkstra is defined on directed graphs. It handles undirected graphs as a special case.


## In short

Dijkstra's algorithm finds the shortest path from a start node to all others in a graph with non-negative edge weights. It works by repeatedly selecting the unvisited node with the smallest tentative distance, updating its neighbours, and marking it settled. The key to its efficiency is a priority queue, which makes the repeated minimum extraction fast. It fails if any edge weight is negative — that is where Bellman-Ford comes in. A* extends it with a heuristic to target a specific destination. This algorithm is the building block for routing, navigation, and many graph-based AI systems.


## Where this is used

Dijkstra's algorithm might seem like a simple graph problem, but it is everywhere in AI and software engineering. In **large language models** (LLMs) it does not appear directly — the weights of a neural network are not edge weights in a graph, and the transformer architecture does not compute shortest paths. However, when an LLM is used to generate a plan, or when it is connected to a **retrieval system**, Dijkstra might be used to plan a route, or to find the most relevant sequence of documents. More directly, in **agentic systems** that plan and call tools, the agent often has to decide an order of actions or a path through a task graph. If the agent needs to find the cheapest sequence of tool calls, or the shortest path through a planning graph, Dijkstra (or A*) is a natural fit. In **robotics and navigation**, which is part of applied AI, Dijkstra is the default for finding the shortest path on a map or a grid. In **network routing**, it is used to find the fastest data path between computers. In **RAG** (retrieval-augmented generation), the retrieval part might use a nearest-neighbour search over embeddings — that is a different kind of search (vector similarity), not graph shortest path, but you might build a knowledge graph where the edges have costs, and then you need Dijkstra to answer questions like 'what is the shortest relation chain between two entities?'. For **small models on devices** (TinyML), Dijkstra is used in applications like indoor navigation for robots, or for planning paths in small maps. A developer might use a library like `networkx` in Python, which has a `shortest_path` function that uses Dijkstra under the hood. They write `nx.shortest_path(graph, source, target, weight='weight')` and it returns the path. What breaks when done badly: if you use negative edge weights, Dijkstra gives wrong answers; if you forget to mark nodes as visited, it can loop forever; and if you use a naive implementation (like a simple list instead of a priority queue), the algorithm becomes too slow on large graphs — that is the main point of the priority queue. In an agentic system, if you mistakenly apply Dijkstra to a graph with negative costs (like a reward that can go negative), you will get a path that is not actually optimal.


---

Read this on the web: https://basavapurushottam.com/learn-ai/dijkstra-shortest-path
