Shortest Paths: Dijkstra

Learn source-to-all shortest paths in non-negative weighted graphs with Dijkstra's algorithm in C++

The shortest path problem asks for the minimum total edge weight needed to travel from a source vertex to other vertices. This page focuses on single-source shortest paths in weighted graphs with non-negative edge weights.

Why BFS is not enough

BFS minimizes the number of edges. In a weighted graph, fewer edges may cost more.

BFS would see 0 -> 1 as one edge, but the cheaper path is 0 -> 2 -> 1 with cost 2.

Dijkstra's idea

Dijkstra's algorithm repeatedly chooses the unprocessed vertex with the smallest known distance, then relaxes its outgoing edges.

Dijkstra(adj, src):
    dist[*] = infinity
    dist[src] = 0
    push (0, src) into min-heap
    while heap not empty:
        (d, u) = pop smallest distance
        if d is stale, skip it
        for each edge u -> v with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                push (dist[v], v)

The greedy choice is safe only when edge weights are non-negative. Once the smallest distance leaves the heap, no future non-negative edge can make it smaller.

Priority queues can contain stale entries

C++ priority_queue has no decrease-key operation. The common competitive-programming pattern is to push a new pair when a distance improves, then skip a popped pair if it no longer matches dist[u].

Full C++ implementation

Use an adjacency list where each edge is (neighbor, weight). The min-heap stores (distance, vertex).

With a binary heap, the time complexity is O((V + E) log V). The adjacency list contributes the V + E scan; heap pushes and pops cost log V.

Relaxation in isolation

Relaxation means: if going through u improves v, update dist[v].

Reconstructing the path

Maintain a parent array whenever a relaxation improves a vertex. To reconstruct a target path, walk parent pointers backward and reverse the result.

When Dijkstra fails

Dijkstra fails with negative edges because a vertex that looked finalized may later become cheaper through a negative edge.

Negative weights need a different algorithm

If negative weights are possible, use Bellman-Ford for single-source shortest paths. If a negative cycle is reachable from the source, no finite shortest path exists for affected vertices.

Bellman-Ford relaxes every edge repeatedly:

BellmanFord(edges, n, src):
    dist[*] = infinity
    dist[src] = 0
    repeat n - 1 times:
        for each edge (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    one more pass can detect negative cycles

Floyd-Warshall for all pairs

Floyd-Warshall computes shortest paths between every pair of vertices in O(V³) time. It is often useful for dense graphs and supports negative edges as long as there are no negative cycles.

for k in 0..n-1:
    for i in 0..n-1:
        for j in 0..n-1:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Challenge: Shortest distance from source

Implement dijkstra for a directed weighted graph with non-negative edge weights. Return INT_MAX for unreachable vertices.

Challenge: Network delay time

Implement networkDelayTime. Nodes are numbered from 1 to n. Return the maximum shortest distance from k, or -1 if any node is unreachable.

Check your understanding

QuestionSelect one

Why does Dijkstra's algorithm require non-negative edge weights?

It uses recursion, which cannot handle negative numbers

A finalized smallest distance could later be improved by a negative edge

Priority queues cannot store negative values

Weighted graphs are always acyclic

QuestionSelect one

What is the usual time complexity of Dijkstra with an adjacency list and binary heap?

O(V²E)

O(log V)

O((V + E) log V)

O(1)

QuestionSelect one

Why do we use a min-heap for Dijkstra instead of a max-heap?

To process the largest vertex id first

To always expand the currently smallest known distance

To make all edges positive

To store the graph itself

Graph Traversal: BFS and DFS

Learn breadth-first search, depth-first search, components, cycle detection, topological sort, and grid traversal in C++

Union-Find (Disjoint Set Union)

Learn DSU find and unite operations, path compression, union by rank, connected components, cycle detection, and Kruskal's MST in C++

Shortest Paths: Dijkstra

On this page