Dijkstra's Shortest Paths

← Back to Algorithm Catalog

Overview
When to Use
Include
Signatures
Parameters
Visitor Events
Supported Graph Properties
Examples
Mandates
Preconditions
Effects
Throws
Complexity
See Also

Overview

Dijkstra's algorithm finds single-source or multi-source shortest paths in a graph with non-negative edge weights. It uses a binary-heap priority queue to greedily expand the nearest unvisited vertex until all reachable vertices have been settled.

The graph must satisfy adjacency_list<G> — both index-based (contiguous integer-indexed) and map-based (sparse vertex ID) graphs are supported.

The library provides two families of overloads:

dijkstra_shortest_paths — computes both distances and predecessor maps, enabling path reconstruction.
dijkstra_shortest_distances — computes distances only, using a lightweight null-predecessor optimization internally.

All overloads accept single or multiple source vertices, an optional weight function, an optional visitor, and optional comparator/combiner functors.

Initialization: Call init_shortest_paths(distances) or init_shortest_paths(distances, predecessors) before invoking the algorithm. This sets all distances to infinity and each vertex's predecessor to itself.

When to Use

Shortest paths with non-negative weights — the classic use case. Road networks, weighted graphs, cost-optimized routing.
Unweighted shortest paths — omit the weight function (the default returns 1 for every edge), giving BFS-equivalent hop-count distances with the same result as BFS but at O((V+E) log V) instead of O(V+E).
Multi-source nearest-facility queries — pass multiple sources to find the closest source for every vertex in one pass.

Not suitable when:

Edge weights may be negative → use Bellman-Ford.
You only need traversal order without distances → use BFS or DFS.

Include

#include <graph/algorithm/dijkstra_shortest_paths.hpp>

Signatures

// Multi-source, distances + predecessors
constexpr void dijkstra_shortest_paths(G&& g, const Sources& sources,
    DistanceFn&& distance, PredecessorFn&& predecessor,
    WF&& weight = /* default returns 1 */,
    Visitor&& visitor = empty_visitor(),
    Compare&& compare = less<>{},
    Combine&& combine = plus<>{},
    const Alloc& alloc = Alloc());

// Single-source, distances + predecessors
constexpr void dijkstra_shortest_paths(G&& g, const vertex_id_t<G>& source,
    DistanceFn&& distance, PredecessorFn&& predecessor,
    WF&& weight = /* default returns 1 */,
    Visitor&& visitor = empty_visitor(),
    Compare&& compare = less<>{},
    Combine&& combine = plus<>{},
    const Alloc& alloc = Alloc());

// Multi-source, distances only
constexpr void dijkstra_shortest_distances(G&& g, const Sources& sources,
    DistanceFn&& distance,
    WF&& weight = /* default returns 1 */,
    Visitor&& visitor = empty_visitor(),
    Compare&& compare = less<>{},
    Combine&& combine = plus<>{},
    const Alloc& alloc = Alloc());

// Single-source, distances only
constexpr void dijkstra_shortest_distances(G&& g, const vertex_id_t<G>& source,
    DistanceFn&& distance,
    WF&& weight = /* default returns 1 */,
    Visitor&& visitor = empty_visitor(),
    Compare&& compare = less<>{},
    Combine&& combine = plus<>{},
    const Alloc& alloc = Alloc());

Parameters

Parameter	Description
`g`	Graph satisfying `adjacency_list`
`source` / `sources`	Source vertex ID or range of source vertex IDs
`distance`	Callable `(const G&, vertex_id_t<G>) -> Distance&` returning a mutable reference to the per-vertex distance. For containers: wrap with `container_value_fn(dist)`. Must satisfy `distance_fn_for<DistanceFn, G>`.
`predecessor`	Callable `(const G&, vertex_id_t<G>) -> Predecessor&` returning a mutable reference to the per-vertex predecessor. For containers: wrap with `container_value_fn(pred)`. Must satisfy `predecessor_fn_for<PredecessorFn, G>`. Use `_null_predecessor` when path reconstruction is not needed.
`weight`	Callable `WF(g, uv)` returning edge weight. Must satisfy `basic_edge_weight_function`. Default: returns `1` for every edge (unweighted).
`visitor`	Optional visitor struct with callback methods (see below). Default: `empty_visitor{}`.
`compare`	Comparison function for distance values. Default: `std::less<>{}`.
`combine`	Combine function for distance + weight. Default: `std::plus<>{}`.
`alloc`	Allocator for internal priority queue storage. Default: `std::allocator<std::byte>{}`.

Visitor Events

Dijkstra's algorithm supports an optional visitor with the following callbacks. Each vertex event also has an _id variant that receives vertex_id_t<G> instead of a vertex reference (e.g., on_discover_vertex_id(g, uid)). You only need to define the events you care about — missing methods are silently skipped.

Event	Called when
`on_initialize_vertex(g, u)`	Before traversal starts, for each vertex
`on_discover_vertex(g, u)`	Vertex first reached (inserted into priority queue)
`on_examine_vertex(g, u)`	Vertex popped from priority queue for processing
`on_examine_edge(g, uv)`	Outgoing edge examined for relaxation
`on_edge_relaxed(g, uv)`	Edge improved a shorter path
`on_edge_not_relaxed(g, uv)`	Edge did not improve the current best path
`on_finish_vertex(g, u)`	All adjacent edges of vertex explored

Supported Graph Properties

Directedness:

✅ Undirected graphs
✅ Directed graphs

Edge Properties:

✅ Non-negative edge weights (required)
❌ Negative edge weights — use Bellman-Ford
✅ Multi-edges (each edge considered for relaxation)
✅ Self-loops (relaxation no-op since distance cannot improve)

Graph Structure:

✅ Connected graphs
✅ Disconnected graphs (unreachable vertices retain infinity distance)
✅ Empty graphs (no-op)

Property Function Requirements:

Required: adjacency_list<G>
distance must satisfy distance_fn_for<DistanceFn, G>
predecessor must satisfy predecessor_fn_for<PredecessorFn, G>
weight must satisfy basic_edge_weight_function
Use container_value_fn(vec) to adapt a std::vector or similar container

Examples

Example 1: Single-Source Shortest Paths

The most common usage — find shortest paths from one vertex to all others in a weighted directed graph.

#include <graph/algorithm/dijkstra_shortest_paths.hpp>
#include <graph/container/dynamic_graph.hpp>
#include <vector>

// Create a weighted directed graph (CLRS example)
//        10       1
//   0 ------→ 1 ----→ 3
//   |  \       ↑      ↑
//   5   2     3|     9|
//   ↓    ↘    |      |
//   2 ------→ 4      |
//   2 ------→ 3 ←----+
using Graph = container::dynamic_graph<double, void, void, unsigned, false,
    container::vov_graph_traits<double>>;

Graph g({{0, 1, 10.0}, {0, 2, 5.0}, {0, 4, 2.0},
         {1, 3, 1.0},
         {2, 1, 3.0}, {2, 3, 9.0}, {2, 4, 2.0},
         {3, 4, 7.0},
         {4, 1, 6.0}, {4, 3, 4.0}});

std::vector<double>   dist(num_vertices(g));
std::vector<unsigned> pred(num_vertices(g));

// Initialize distances to infinity, predecessors to self
init_shortest_paths(dist, pred);

dijkstra_shortest_paths(g, 0u, container_value_fn(dist), container_value_fn(pred),
    [](const auto& g, const auto& uv) { return edge_value(g, uv); });

// dist[0] = 0, dist[1] = 8, dist[2] = 5, dist[3] = 6, dist[4] = 2
// pred[0] = 0, pred[1] = 2, pred[2] = 0, pred[3] = 4, pred[4] = 0

Example 2: Distances Only (No Predecessors)

When you only need distances and don't need to reconstruct paths, use dijkstra_shortest_distances — it skips predecessor tracking entirely.

std::vector<double> dist(num_vertices(g));
init_shortest_paths(dist);  // one-argument form: distances only

dijkstra_shortest_distances(g, 0u, container_value_fn(dist),
    [](const auto& g, const auto& uv) { return edge_value(g, uv); });

// dist[v] = shortest distance from source 0 to v
// Unreachable vertices remain at infinite_distance<double>()

Example 3: Multi-Source Shortest Paths

Run Dijkstra from multiple source vertices simultaneously — useful for finding the nearest facility, multi-root BFS-like queries, etc.

std::vector<double>   dist(num_vertices(g));
std::vector<unsigned> pred(num_vertices(g));

init_shortest_paths(dist, pred);

// Sources can be any range: vector, array, initializer_list
std::array sources{0u, 2u};
dijkstra_shortest_paths(g, sources, container_value_fn(dist), container_value_fn(pred),
    [](const auto& g, const auto& uv) { return edge_value(g, uv); });

// dist[v] = shortest distance from the nearest source to v
// pred[v] traces back to whichever source was closest

Example 4: Path Reconstruction

After running dijkstra_shortest_paths, reconstruct the shortest path from source to any target by walking the predecessor array backwards.

// After running dijkstra_shortest_paths(g, source, container_value_fn(dist), container_value_fn(pred), weight) ...

unsigned target = 3;
unsigned source = 0;

if (dist[target] == infinite_distance<double>()) {
    // target is unreachable from source
} else {
    // Build path in reverse
    std::vector<unsigned> path;
    for (unsigned v = target; v != source; v = pred[v]) {
        path.push_back(v);
    }
    path.push_back(source);
    std::ranges::reverse(path);
    // path = {0, 4, 3} with total distance dist[3] = 6.0
}

Example 5: Unweighted Graph (Default Weight)

When no weight function is provided, the default returns 1 for every edge. This gives BFS-equivalent hop-count distances (though at higher time complexity than BFS itself).

#include <graph/algorithm/dijkstra_shortest_paths.hpp>
#include <graph/container/dynamic_graph.hpp>

using Graph = container::dynamic_graph<void, void, void, uint32_t, false,
    container::vov_graph_traits<void>>;

Graph g({{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}});

std::vector<double>   dist(num_vertices(g));
std::vector<uint32_t> pred(num_vertices(g));
init_shortest_paths(dist, pred);

// No weight function — default returns 1 per edge
dijkstra_shortest_paths(g, 0u, container_value_fn(dist), container_value_fn(pred));

// dist[0] = 0, dist[1] = 1, dist[2] = 1, dist[3] = 2, dist[4] = 3
// These are hop counts — same as BFS distances

Example 6: Custom Visitor

Use a visitor to observe algorithm progress — useful for logging, debugging, early analysis, or computing derived metrics during traversal.

struct RelaxationTracker {
    int relaxed = 0;
    int not_relaxed = 0;
    int vertices_settled = 0;

    // Track how many edges improve a path
    void on_edge_relaxed(const auto& g, const auto& uv) {
        ++relaxed;
    }
    void on_edge_not_relaxed(const auto& g, const auto& uv) {
        ++not_relaxed;
    }
    // Count settled vertices (popped from priority queue)
    void on_examine_vertex(const auto& g, const auto& u) {
        ++vertices_settled;
    }
};

std::vector<double>   dist(num_vertices(g));
std::vector<unsigned> pred(num_vertices(g));
init_shortest_paths(dist, pred);

RelaxationTracker tracker;
dijkstra_shortest_paths(g, 0u, container_value_fn(dist), container_value_fn(pred),
    [](const auto& g, const auto& uv) { return edge_value(g, uv); },
    tracker);

// tracker.relaxed = number of successful edge relaxations
// tracker.vertices_settled = number of vertices processed

You can also use _id variants to receive vertex IDs directly:

struct IdVisitor {
    void on_discover_vertex_id(const auto& g, auto uid) {
        std::cout << "Discovered vertex " << uid << "\n";
    }
    void on_edge_relaxed(const auto& g, const auto& uv) {
        std::cout << source_id(g, uv) << " → " << target_id(g, uv) << " relaxed\n";
    }
};

Mandates

G must satisfy adjacency_list<G>
DistanceFn must satisfy distance_fn_for<DistanceFn, G>
PredecessorFn must satisfy predecessor_fn_for<PredecessorFn, G> (or use _null_predecessor)
WF must satisfy basic_edge_weight_function
Visitor callbacks (if present) must accept appropriate graph and vertex/edge parameters

Preconditions

All edge weights must be non-negative. For signed weight types, a negative weight throws std::out_of_range at runtime.
distance(g, uid) must be valid for all vertex IDs in g
Call init_shortest_paths(distances, predecessors) on the underlying containers before invoking the algorithm
All source vertex IDs must be valid vertex IDs in g

Effects

Writes shortest-path distances via distance(g, v) for all reachable vertices
Writes predecessor vertex IDs via predecessor(g, v) for path reconstruction (dijkstra_shortest_paths only)
Does not modify the graph g
Invokes visitor callbacks in Dijkstra traversal order

Throws

std::out_of_range if a source vertex ID is invalid, if distances or predecessors is undersized, or if a negative edge weight is encountered (signed weight types only)
std::bad_alloc if internal allocations fail
Exception guarantee: Basic. Graph g remains unchanged; output may be partial.

Complexity

Metric	Value
Time	O((V + E) log V)
Space	O(V) auxiliary (priority queue + color map)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Dijkstra's Shortest Paths

Table of Contents

Overview

When to Use

Include

Signatures

Parameters

Visitor Events

Supported Graph Properties

Examples

Example 1: Single-Source Shortest Paths

Example 2: Distances Only (No Predecessors)

Example 3: Multi-Source Shortest Paths

Example 4: Path Reconstruction

Example 5: Unweighted Graph (Default Weight)

Example 6: Custom Visitor

Mandates

Preconditions

Effects

Throws

Complexity

See Also

FilesExpand file tree

dijkstra.md

Latest commit

History

dijkstra.md

File metadata and controls

Dijkstra's Shortest Paths

Table of Contents

Overview

When to Use

Include

Signatures

Parameters

Visitor Events

Supported Graph Properties

Examples

Example 1: Single-Source Shortest Paths

Example 2: Distances Only (No Predecessors)

Example 3: Multi-Source Shortest Paths

Example 4: Path Reconstruction

Example 5: Unweighted Graph (Default Weight)

Example 6: Custom Visitor

Mandates

Preconditions

Effects

Throws

Complexity

See Also