Dijkstra's Shortest Path Algorithm

On a graph with non-negative weights, find the shortest path from one vertex to every other vertex in $O(E \log V)$ using a priority queue.

Finding the shortest path from one vertex to all others in a weighted graph shows up constantly in practice: routing, navigation, network optimization. Dijkstra's algorithm is the canonical greedy algorithm that solves this efficiently on graphs with non-negative weights.

Definition

Dijkstra's algorithm finds the shortest path from a given start vertex to every other vertex, on a graph whose edges have no negative weights.

Input and output

Input: vertex set V, edge set E (weights $\geq 0$ ), start vertex s
Output: the shortest distance from the start vertex to every vertex

Time complexity: $O(E \log V)$ (with a priority queue)

The idea

Initialize: start vertex distance $= 0$ , all others $= \infty$
Repeat:
- Pop the vertex u with the smallest distance from the priority queue
- For each neighbor v of u, update if dist[u] + weight(u,v) < dist[v]
Terminate: when every vertex has been processed

Example: a walkthrough

Step	Vertex processed	dist array
initial	-	$[0, \infty, \infty, \infty, \infty]$
1	A	$[0, 2, 5, \infty, \infty]$
2	B	$[0, 2, 3, 5, \infty]$
3	C	[0, 2, 3, 5, 8]
4	D	[0, 2, 3, 5, 6]
5	E	[0, 2, 3, 5, 6]

Result: shortest distance from A to E = 6 (A→B→D→E)

Python implementation

The Python version uses a heapq-based priority queue to greedily select the vertex with the minimum distance.

python

import heapq
import sys
 
def dijkstra(start, graph, n):
    INF = sys.maxsize
    dist = [INF] * n
    dist[start] = 0
 
    pq = [(0, start)]  # (distance, node)
    visited = [False] * n
 
    while pq:
        current_dist, u = heapq.heappop(pq)
 
        if visited[u]:
            continue
        visited[u] = True
 
        for v, w in graph[u]:
            if current_dist + w < dist[v]:
                dist[v] = current_dist + w
                heapq.heappush(pq, (dist[v], v))
 
    return dist
 
 
# build the graph (adjacency list)
n = 5
graph = [[] for _ in range(n)]
edges = [
    (0, 1, 2), (0, 2, 5), (1, 2, 1),
    (1, 3, 3), (2, 3, 2), (2, 4, 5), (3, 4, 1)
]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))
 
distances = dijkstra(0, graph, n)
print(distances)  # [0, 2, 3, 5, 6]

Java implementation

The logic is identical to Python. The PriorityQueue comparator uses o[1] (the distance) so the closest vertex comes out first, and the visited array skips vertices that are already settled.

java

import java.util.*;
 
public class Dijkstra {
    public static int[] dijkstra(int start, List<List<int[]>> graph) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
 
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(o -> o[1])
        );
        pq.offer(new int[]{start, 0});
        boolean[] visited = new boolean[n];
 
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
 
            if (visited[u]) continue;
            visited[u] = true;
 
            for (int[] edge : graph.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }
}

Go implementation

Go uses the standard library container/heap, so PriorityQueue implements Len/Less/Swap and Push/Pop directly. Less makes it a min-heap on dist, and the rest of the relaxation logic matches Python and Java.

import (
    "container/heap"
    "math"
)
 
type Item struct {
    node, dist, idx int
}
 
type PriorityQueue []*Item
 
func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Item)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}
 
func Dijkstra(start int, graph [][]Edge) []int {
    dist := make([]int, len(graph))
    for i := range dist {
        dist[i] = math.MaxInt64
    }
    dist[start] = 0
 
    pq := &PriorityQueue{}
    heap.Push(pq, &Item{node: start, dist: 0})
    visited := make([]bool, len(graph))
 
    for pq.Len() > 0 {
        current := heap.Pop(pq).(*Item)
        u := current.node
 
        if visited[u] {
            continue
        }
        visited[u] = true
 
        for _, edge := range graph[u] {
            if dist[u]+edge.weight < dist[edge.node] {
                dist[edge.node] = dist[u] + edge.weight
                heap.Push(pq, &Item{node: edge.node, dist: dist[edge.node]})
            }
        }
    }
    return dist
}

Things to watch for

Item	Description
Negative weights	Dijkstra does not apply, use Bellman-Ford which allows negative edges
Visited check	Required to avoid redundant work
Path reconstruction	Store u in a parent array at the moment of relaxation

Applications

GPS and map routing
Network routing
Pathfinding in game AI
Shortest relationship analysis in social networks

Almost any cost minimization problem over non-negative weights maps onto it directly.

Summary

Dijkstra's algorithm finds shortest paths on graphs with non-negative weights. With a priority queue it runs in $O(E \log V)$ . Negative edge weights break its correctness, and Bellman-Ford is the alternative in that case. When the path itself is needed rather than just the distance, store the relaxing vertex in a parent array and walk it backwards. The core logic stays the same across languages: pop the closest vertex first and skip vertices already visited.