What is Dijkstra’s Algorithm: A Complete Guide to Shortest Path

Every time you ask your GPS for the fastest route to a destination, a shortest-path algorithm runs in the background. Every time a network router decides how to forward a data packet, a shortest-path computation determines the route. Every time a logistics system plans the most efficient delivery sequence, a graph algorithm finds the answer.

In most of these systems, the algorithm at work is Dijkstra’s.

Dijkstra’s algorithm, developed by Dutch computer scientist Edsger W. Dijkstra in 1956, is the most widely used and studied algorithm for finding the shortest path between nodes in a weighted graph. It is elegant, efficient, and provably optimal, guaranteed to find the minimum-cost path from a source node to every other reachable node in the graph, provided all edge weights are non-negative.

This article explains Dijkstra’s algorithm from first principles: what problem it solves, how it works step by step, why it is correct, what data structures it uses, and where it is applied in practice.

TL;DR

• Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights.
• It uses a greedy approach: always expand the unvisited node with the smallest known distance from the source.
• A priority queue (min-heap) stores candidate nodes ordered by current tentative distance, enabling efficient node selection.
• Edge relaxation updates a neighbour’s distance when a shorter path through the current node is discovered.
• Dijkstra’s algorithm is used in GPS navigation, network routing, game pathfinding, and logistics optimization.

The Problem Dijkstra’s Algorithm Solves

The shortest path problem is one of the most fundamental problems in computer science and operations research. Given a weighted graph, a collection of nodes connected by edges, each edge carrying a numeric weight representing cost, distance, or time, the problem asks: what is the minimum-cost path from a given source node to one or all other nodes?

Why Brute Force Fails

A naive approach enumerate all possible paths from the source and selects the shortest is computationally intractable for any reasonably sized graph. The number of possible paths grows exponentially with the number of nodes. A road network with a million intersections has an astronomical number of possible routes between any two points.

Dijkstra’s algorithm avoids this by exploiting the structure of the problem: the shortest path to any node consists of the shortest path to some predecessor node, plus the edge connecting them. This principle of optimal substructure allows the algorithm to build shortest paths incrementally, extending already-proven optimal paths rather than reconsidering all possibilities.

Graph Terminology

Before examining the algorithm, a brief review of the relevant graph terms:

• Node (vertex): A point in the graph representing a location, state, or entity.
• Edge: A connection between two nodes. Edges can be directed (one-way) or undirected (two-way).
• Weight: A numeric value associated with each edge representing cost, distance, time, or any non-negative quantity.
• Path: A sequence of nodes connected by edges from a source to a destination.
• Shortest path: The path between two nodes with the minimum total edge weight.

How Dijkstra’s Algorithm Works: Step by Step

Dijkstra’s algorithm operates on a weighted graph and a designated source node. It maintains three key data structures throughout its execution and follows a systematic expansion procedure until all reachable nodes have been processed.

Data Structures

•      Distance table (dist[]): Records the current shortest known distance from the source to each node. Initialized to 0 for the source and infinity (∞) for all other nodes.

•      Priority queue (min-heap): A data structure that always returns the node with the smallest tentative distance. Enables efficient selection of the next node to process.

•      Visited set: Tracks which nodes have been fully processed (their shortest path has been finalized). Once a node is added to the visited set, its distance entry in the distance table is guaranteed to be optimal and will not change.

Initialisation

Before the algorithm begins:

1.    Set dist[source] = 0.

2.    Set dist[v] = ∞ for all other nodes v.

3.    Add the source node to the priority queue with priority 0.

The Main Loop

The algorithm repeatedly executes the following cycle until the priority queue is empty:

4.    Extract minimum: Remove the node u with the smallest tentative distance from the priority queue.

5.    Skip if visited: If you have already been processed (is in the visited set), skip it and continue to the next iteration. This handles stale entries in the priority queue.

6.    Mark as visited: Add u to the visited set. The distance dist[u] is now finalized and optimal.

7.    Relax neighbours: For each unvisited neighbour v of u with edge weight w(u, v): if dist[u] + w(u, v) < dist[v], update dist[v] = dist[u] + w(u, v) and add v to the priority queue with the new distance as priority.

Edge Relaxation: The Core Operation

Edge relaxation is the fundamental operation that drives Dijkstra’s algorithm. When processing node u, for each of its neighbours v, the algorithm checks whether the path to v through u is shorter than the current best-known path to v:

If dist[u] + w(u, v) < dist[v], the path through u to v is cheaper. The distance is updated: dist[v] = dist[u] + w(u, v), and v is added to the priority queue with the new, smaller distance as its priority.

This relaxation step propagates improvements through the graph — each time a shorter path to a node is found, the shorter path is used to potentially improve the distances to its neighbours.

A Worked Example of Dijkstra’s Algorithm

Let us trace through a concrete example to see how Dijkstra’s algorithm finds shortest paths.

The Graph

Consider a graph with 5 nodes: A, B, C, D, E. The edges and their weights are:

•      A → B: weight 4

•      A → C: weight 2

•      C → B: weight 1

•      B → D: weight 5

•      C → D: weight 8

•      D → E: weight 2

•      B → E: weight 6

Source node: A.

Step-by-Step Trace

Initial state: dist = {A:0, B:∞, C:∞, D:∞, E:∞}. Priority queue: [(0, A)].

8.    Process A (distance 0): Neighbours B (via A, cost 0+4=4) and C (via A, cost 0+2=2). Update dist[B]=4, dist[C]=2. Queue: [(2,C),(4,B)].

9.    Process C (distance 2): Neighbours B (via C, cost 2+1=3 < 4) and D (via C, cost 2+8=10). Update dist[B]=3, dist[D]=10. Queue: [(3,B),(4,B*),(10,D)].

10. Process B (distance 3): Neighbours D (via B, cost 3+5=8 < 10) and E (via B, cost 3+6=9). Update dist[D]=8, dist[E]=9. Queue: [(4,B*),(8,D),(9,E),(10,D*)].

11. Process B again (distance 4): Skip already visited.

12. Process D (distance 8): Neighbour E (via D, cost 8+2=10 > 9). No update. Queue: [(9,E),(10,D*),(10,E*)].

13. Process E (distance 9): No unvisited neighbours. Algorithm complete.

Final Shortest Distances from A

•      A → A: 0

•      A → C: 2 (path: A → C)

•      A → B: 3 (path: A → C → B)

•      A → D: 8 (path: A → C → B → D)

•      A → E: 9 (path: A → C → B → E)

Note that the direct path A → B (cost 4) was beaten by the two-hop path A → C → B (cost 3). This illustrates a crucial point: the shortest path is not always the one with the fewest edges.

Why Dijkstra’s Algorithm Is Correct

Dijkstra’s algorithm is greedy at each step; it makes the locally optimal choice (expand the closest unvisited node) without reconsidering previous decisions. Why is this greedy choice globally optimal?

The Greedy Invariant

The key insight is the greedy invariant: when a node u is selected for expansion (removed from the priority queue), the distance dist[u] is guaranteed to be the true shortest distance from the source to u.

Proof by contradiction: Suppose there exists a shorter path to u that has not yet been discovered. This path must pass through some unvisited node v at some point. But since all edge weights are non-negative, the cost of this path is at least dist[v] ≥ dist[u] (because u was selected before v, meaning dist[u] ≤ dist[v]). Therefore, no shorter path through unvisited nodes can exist. The greedy choice is provably optimal.

Why Non-Negative Weights Are Essential

The correctness proof depends critically on all edge weights being non-negative. If negative weights are allowed, a later-discovered path through a negative-weight edge could make a previously settled node’s distance incorrect.

For graphs with negative edge weights, the Bellman-Ford algorithm is the appropriate choice — it handles negative weights (though not negative cycles) at the cost of higher computational complexity: O(V × E) versus Dijkstra’s O((V + E) log V).

Time Complexity and Implementation

The time complexity of Dijkstra’s algorithm depends on the data structure used for the priority queue. The priority queue determines how efficiently the algorithm selects the closest unvisited node and updates node distances.

With a Simple Array (Naive Implementation)

The simplest implementation stores all nodes in an unsorted array. Finding the minimum-distance unvisited node requires scanning the entire array O(V) per extraction. With V extractions and E edge relaxations:

• Total time complexity: O(V² + E) = O(V²) for dense graphs where E ≈ V².
• Suitable for: Dense graphs where E is close to V², and the O(V²) bound is acceptable. Simple to implement.

With a Binary Min-Heap (Standard Implementation)

Using a binary min-heap (Python’s heapq module) as the priority queue reduces the cost of minimum extraction to O(log V). Edge relaxations add new entries to the heap in O(log V) time:

• Total time complexity: O((V + E) log V).
• Suitable for: Sparse graphs where E = O(V log V) or smaller. The standard implementation for most practical applications, including GPS navigation and network routing.

With a Fibonacci Heap (Optimal Implementation)

A Fibonacci heap achieves amortized O(1) for key decrease operations and O(log V) for minimum extraction:

• Total time complexity: O(E + V log V), theoretically optimal for Dijkstra’s algorithm.
• Suitable for: Very large, sparse graphs where the theoretical improvement is significant. Rarely used in practice due to high constant factors and implementation complexity.

Dijkstra’s Algorithm vs. Related Algorithms

Dijkstra’s algorithm is part of a family of shortest-path algorithms. Understanding how it relates to its alternatives clarifies when to use each.

Dijkstra vs. Bellman-Ford

Bellman-Ford solves the same single-source shortest path problem but handles negative edge weights (though not negative cycles, which have no well-defined shortest path). Its approach is fundamentally different: it relaxes all edges V-1 times, guaranteeing correctness even with negative weights. The trade-off is efficiency O(V × E) versus Dijkstra’s O((V+E) log V). Use Bellman-Ford when negative weights are present; use Dijkstra’s when all weights are non-negative.

Dijkstra vs. A* Search

A* extends Dijkstra’s algorithm with a heuristic function h(n) that estimates the remaining cost to reach the goal from any node. Instead of expanding nodes in order of distance from the source (Dijkstra’s f(n) = g(n)), A* expands nodes in order of estimated total cost (f(n) = g(n) + h(n)). With an admissible heuristic, A* explores fewer nodes than Dijkstra’s and finds the same optimal path, making it preferred for single-source, single-destination pathfinding (e.g., GPS navigation). Dijkstra’s is preferred when the shortest paths to all nodes are needed.

Dijkstra vs. Floyd-Warshall

Floyd-Warshall solves the all-pairs shortest path problem, finding shortest paths between every pair of nodes in the graph. Running Dijkstra’s from every node produces the same result for non-negative graphs, but Floyd-Warshall handles negative weights (without negative cycles) and has a simpler O(V³) implementation. For all-pairs shortest paths on dense graphs with non-negative weights, the choice depends on graph density and implementation constraints.

Real-World Applications of Dijkstra’s Algorithm

Dijkstra’s algorithm is not a theoretical curiosity; it is deployed at scale in systems used by billions of people every day.

GPS Navigation and Mapping

GPS navigation applications Google Maps, Apple Maps, Waze, and in-vehicle navigation systems use Dijkstra’s algorithm and its variants (particularly A*) to compute optimal routes between locations. The road network is modelled as a weighted directed graph: intersections are nodes, road segments are edges, and weights represent travel time or distance. For real-time applications, bidirectional Dijkstra (running two simultaneous searches from source and destination) and contraction hierarchies (preprocessing the graph to accelerate queries) are used to make route computation fast enough for interactive use.

Network Routing Protocols

The Open Shortest Path First (OSPF) protocol, one of the most widely used Internet routing protocols,s uses Dijkstra’s algorithm to compute shortest paths through network topologies. Each router maintains a map of the network, runs Dijkstra’s to find the shortest path to every other router, and builds its forwarding table accordingly. Dijkstra’s algorithm runs continuously in internet routers worldwide, making routing decisions for billions of packets per second. 

Game Development and Pathfinding

Video games use Dijkstra’s algorithm (and its heuristic-guided variant A*) to navigate characters, units, and enemies through game worlds. Strategy games, RPGs, and simulations require characters to find optimal paths around obstacles in real time, often for hundreds of units simultaneously. The game world is discretized into a grid or navigation mesh, and Dijkstra’s (or A*) finds the shortest path through the traversable nodes.

Logistics and Supply Chain Optimization

Logistics companies use shortest-path algorithms to plan delivery routes, optimize warehouse picking paths, route freight through distribution networks, and minimize fuel consumption across vehicle fleets. The problem maps directly to Dijkstra’s framework: warehouses and delivery stops are nodes, road connections are edges, and edge weights represent distance, time, or cost. While real logistics problems involve additional constraints (vehicle capacity, time windows), shortest-path computation is a fundamental sub-problem in every logistics optimization system.

If you want practical experience working with activation functions, neural networks, and deep learning models, HCL GUVI’s AI and ML programs can help you understand how concepts like sigmoid, backpropagation, and gradient descent are implemented using frameworks such as TensorFlow and PyTorch through hands-on projects. 

Conclusion

Dijkstra’s algorithm is one of the most important and beautiful algorithms in computer science. Conceived in 20 minutes in 1956 and refined in the decades since, it remains the definitive solution to the single-source shortest path problem on graphs with non-negative edge weights and the foundation on which more sophisticated algorithms like A* are built.

Its power comes from the elegant interplay of the greedy invariant, edge relaxation, and priority queue selection: by always expanding the closest unvisited node and updating neighbours only when shorter paths are found, it builds shortest path trees efficiently and provably correctly. The binary heap implementation achieves O((V+E) log V) practical for real-world graphs with millions of nodes.

From GPS navigation to internet routing, from game pathfinding to logistics planning, Dijkstra’s algorithm runs silently behind some of the most important computational systems in existence. Understanding how it works, why it is correct, when to use it, and how to implement it is foundational knowledge for any computer scientist, software engineer, or AI practitioner who works with graphs, networks, or optimization.

FAQs

1. Why does Dijkstra’s algorithm require non-negative edge weights?

The correctness of Dijkstra’s greedy strategy depends on the fact that adding more edges to a path cannot decrease its total cost. With negative weights, a longer path might be cheaper, invalidating the guarantee that the first time a node is processed, its shortest path has been found. Bellman-Ford handles negative weights correctly.

2. What is the difference between Dijkstra’s algorithm and BFS?

BFS finds the shortest path in terms of the number of edges (unweighted shortest path). Dijkstra’s algorithm finds the shortest path in terms of total edge weight (weighted shortest path). BFS uses a simple queue; Dijkstra’s uses a priority queue ordered by cumulative distance. For unweighted graphs, BFS and Dijkstra’s produce the same result, but BFS is faster.

3. Can Dijkstra’s algorithm find the shortest path between two specific nodes?

Yes. The standard algorithm finds the shortest paths from a source to all reachable nodes. For a single source-destination query, the algorithm can stop as soon as the destination node is extracted from the priority queue; at that point, its shortest path is finalized. A* is typically preferred for single-pair queries because it uses a heuristic to focus the search toward the destination.

4. What data structure makes Dijkstra’s algorithm most efficient?

A binary min-heap (priority queue) gives the standard practical complexity of O((V+E) log V). A Fibonacci heap achieves the theoretically optimal O(E + V log V) but has high implementation complexity. For most practical applications, Python’s heapq module (binary heap) provides the best balance of efficiency and simplicity.

5. What is the difference between Dijkstra’s algorithm and A*?

Dijkstra’s algorithm expands nodes in order of distance from the source, finding shortest paths to all nodes. A* adds a heuristic estimate of the distance to the goal, prioritizing nodes that appear closer to the destination. With an admissible heuristic, A* explores fewer nodes than Dijkstra’s for single-pair queries while finding the same optimal path.