⚙️AlgorithmIntermediate

Dijkstra's Algorithm

Key Points

•
Dijkstra's algorithm finds shortest path distances from one source to all vertices when all edge weights are non-negative.
•
It is a greedy algorithm that repeatedly finalizes the unvisited vertex with the smallest tentative distance.
•
Using a binary heap (priority queue) on a sparse graph gives time complexity O(( $∣ V ∣$ + $∣ E ∣$ ) $lo g$ $∣ V ∣$ ).
•
On dense graphs without a heap, a simple array-based implementation runs in O(|V|^2 + |E|), which is effectively O(|V|^2).
•
Once a vertex is extracted from the priority queue, its recorded distance is the true shortest distance and never changes.
•
Dijkstra fails with negative-weight edges; use Bellman–Ford in that case.
•
Common pitfalls include integer overflow, forgetting to ignore outdated heap entries, and misusing the algorithm on graphs with negative edges.
•
You can reconstruct paths by storing parents during relaxation and backtracking from a target.

Prerequisites

→Graph representation (adjacency list and matrix) — Dijkstra iterates over neighbors; efficient storage of edges and weights is necessary.
→Heaps and priority queues — Selecting the minimum-distance frontier vertex efficiently requires a min-heap.
→Greedy algorithms — Understanding why choosing the locally best next vertex leads to a globally optimal solution is key.
→Time and space complexity — Choosing between heap-based and array-based implementations depends on asymptotic costs.
→Paths, distances, and relaxation — Dijkstra's core step is edge relaxation, which assumes non-negative weights.
→Handling negative edges (Bellman–Ford, 0–1 BFS) — Knowing alternatives prevents misuse of Dijkstra on invalid inputs.
→Integer ranges and overflow — Correctly handling large path sums requires 64-bit integers and safe INF.

Detailed Explanation

Tap terms for definitions

01Overview

Dijkstra's algorithm solves the single-source shortest path problem on weighted graphs with non-negative edge weights. Given a starting vertex s, it computes the minimum possible distance to every other vertex by progressively exploring the graph from near to far. The algorithm maintains a tentative distance for each vertex and a set of finalized (settled) vertices whose shortest distances are already known. At each step, it chooses the unsettled vertex with the smallest tentative distance, finalizes it, and relaxes its outgoing edges (i.e., it tries to improve neighbors' distances through it). The heart of the algorithm is a greedy choice: always expand the currently closest frontier vertex. The data structure typically used is a min-priority queue (binary heap) keyed by tentative distances. With an adjacency list representation and a binary heap, the running time is O((|V| + |E|) \log |V|), which is efficient for sparse graphs commonly found in competitive programming. On very dense graphs, a simpler O(|V|^2) implementation can be competitive or faster due to smaller constants and fewer heap operations. Dijkstra's correctness relies on the non-negativity of weights; negative edges break the greedy choice guarantee because a later negative edge could retroactively make a previously finalized distance too large. The algorithm is widely used in routing, navigation, network optimization, grid-based pathfinding with costs, and as a building block in many graph problems.

02Intuition & Analogies

Imagine planning a road trip from your home to all towns on a map, where each road segment has a non-negative travel time. You start with your home at 0 minutes and every other town as "infinite". Then you proceed like a spreading wave: always pick the as-of-now closest town that you can already reach and confirm its best time. Once you’ve confirmed that town, you look at the roads leaving it and see if any neighbor can be reached faster by going through this newly confirmed town—if so, you update that neighbor’s best known time. This is exactly like building out an efficient delivery route: finalize the next nearest stop, then use it as a stepping stone to improve your plan for later stops. Another way to view it: picture a balloon inflating from the source. The air front moves outward, and the first moment it touches a town is the earliest possible time you could arrive there via any path—because you always expand from the minimal-distance frontier. This relies on the fact that roads can’t have negative time; otherwise, some weird time-travel road could make you arrive earlier than when the balloon first touched, invalidating the greedy step. The relaxation step is like checking if a newly discovered shortcut through a confirmed town beats your currently penciled-in route for its neighbors. Priority queues help you efficiently choose which frontier town is next closest, much like always checking the cheapest option on top of a sorted to-do list. When you extract a town from that list, you can sign its time in pen: no later discovery can beat it, thanks to non-negative edges and the way the frontier grows.

03Formal Definition

Let G = (V, E) be a directed or undirected graph with a non-negative weight function w: E

\to

R_{\geq 0}

, a source vertex s

\in

V, and true shortest-path distances

δ

(s, v) for v

\in

V. Dijkstra's algorithm maintains an array d[v] of tentative distances, initialized as d[s] = 0 and d[v] =

\infty

for v

\neq =

s. We also maintain a set S of settled vertices, initially empty, and a min-priority queue keyed by d[v] for unsettled vertices. Repeatedly, the algorithm extracts u with minimal d[u] among unsettled vertices, inserts u into S, and for each outgoing edge (u, v)

\in

E performs relaxation: if d[v] > d[u] + w(u, v), then set d[v]

\leftarrow

d[u] + w(u, v) and optionally record parent[v]

\leftarrow

u for path reconstruction. The greedy-choice and cut properties imply correctness: when u is extracted (minimal d[u] among V

∖

S), then d[u] =

δ

(s, u). Because all edges are non-negative, any path to a still-unsettled vertex v must be at least d[u], and cannot later reduce d[u]. Consequently, once a vertex is settled, its tentative distance is final. Using an adjacency list and a binary heap priority queue ensures O((

∣ V ∣

∣ E ∣

)

lo g

∣ V ∣

) time and O(

∣ V ∣

∣ E ∣

) space. A dense-graph variant that linearly scans for the minimal unsettled vertex each iteration yields O(

∣ V ∣

^2 +

∣ E ∣

) time and O(

∣ V ∣

^2) space when using an adjacency matrix.

04When to Use

Use Dijkstra's algorithm whenever you need shortest paths from one source in a weighted graph with non-negative edges. Typical scenarios include road networks (minimizing travel time or distance), network routing (minimizing latency), grid maps in games (tile movement costs), and problems that require computing distances to enable further decisions (e.g., building Voronoi-like partitions from multiple sources by pushing them with initial distance 0). For sparse graphs with up to around 2e5–1e6 edges, a binary-heap implementation is standard in contests. For dense graphs (|E| ≈ |V|^2), the O(|V|^2) array-based version can outperform heap-based variants due to lower overhead and better cache behavior. Avoid Dijkstra if any edge can be negative. In that case, use Bellman–Ford (handles negative weights and detects negative cycles) or specialized algorithms for particular structures (e.g., 0–1 BFS for edge weights in {0,1}, which runs in O(|V| + |E|)). If you have many queries on a static graph, consider precomputation strategies like running Dijkstra from multiple landmarks, multi-source Dijkstra for nearest-facility queries, or even all-pairs algorithms on small graphs (Floyd–Warshall) depending on constraints.

⚠️Common Mistakes

• Using Dijkstra on graphs with negative edges. The algorithm’s greedy step becomes invalid; distances can be finalized too early. Switch to Bellman–Ford or reweight edges (Johnson’s algorithm) if needed. • Integer overflow. Path lengths can exceed 2^31−1. Use 64-bit integers (long long in C++) and a large but safe INF (e.g., 4e18) to avoid overflow on d[u] + w(u, v). • Forgetting to skip outdated heap entries. In the common "lazy" implementation, you may push multiple entries per vertex; always check if the popped distance matches the current d[u] and continue if it does not. • Poor graph representation. Using an adjacency matrix for sparse graphs wastes memory and time; use adjacency lists when |E| is near O(|V|). • Not initializing or resetting structures between runs. Distances, parents, and visited flags must be reinitialized for each new source. • Incorrect early exit. You may stop when the target t is extracted from the priority queue (not when first discovered), because only then is d[t] guaranteed final. • Mishandling unreachable vertices. Keep INF distances and handle them in outputs/path reconstruction. • Off-by-one and indexing errors. Be consistent about 0-based vs 1-based indexing in input and internal storage.

Key Formulas

Path Length

w (P) = i = 1 \sum k w (e_{i})

Explanation: The weight of a path P with edges $e_{1}$ , $e_{2}$ , ..., $e_{k}$ is the sum of its edge weights. Shortest paths minimize this sum among all possible paths between two vertices.

Relaxation Rule

d [v] \leftarrow min {d [v], d [u] + w (u, v)}

Explanation: When exploring edge (u, v), we try to improve the tentative distance to v using u. If going through u yields a smaller distance, we update d[v].

Binary Heap Time Complexity

T (∣ V ∣, ∣ E ∣) = O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)

Explanation: Using an adjacency list and a binary heap priority queue, each extract-min and decrease-key (push of improved key) costs O(log |V|). Summed over all operations, the total running time is O((|V| + |E|) log |V|).

Array-Based Time Complexity

T (∣ V ∣, ∣ E ∣) = O (∣ V ∣^{2} + ∣ E ∣) = O (∣ V ∣^{2})

Explanation: If we linearly scan to find the next minimal unsettled vertex, each of |V| iterations costs O(|V|). With adjacency matrix relaxation, total time is O(|V|^2), suitable for dense graphs.

Finalization Property

d [u] = δ (s, u) when u is extracted

Explanation: When the vertex u with minimal tentative distance is popped from the priority queue, its distance equals the true shortest-path distance from s to u. This is the key correctness guarantee.

Triangle Inequality on Graphs

δ (s, v) \leq δ (s, u) + w (u, v) for all edges (u, v) \in E

Explanation: The true shortest-path distance to v cannot exceed the distance to u plus the edge weight from u to v. This underlies the relaxation step.

Target Early Exit Condition

Early exit: if target t is extracted, then d [t] = δ (s, t)

Explanation: You may safely stop the algorithm early once the target is popped from the priority queue, because its tentative distance is final at that moment.

Settled Set

S_{k} = {v \in V ∣ v has been extracted after k iterations}

Explanation: The set of settled vertices grows monotonically. For any v in $S_{k}$ , we have d[v] = $δ$ (s, v); for any v not in $S_{k}$ , d[v] $\geq$ $min_{x \in S_{k}}$ d[x].

Complexity Analysis

Let n =

∣ V ∣

and m =

∣ E ∣

. With an adjacency list and a binary heap (C++ priorit

y_{q} u e u e

with greater comparator), each vertex is inserted once initially and potentially reinserted whenever its tentative distance improves. In the common lazy variant, each relaxation that improves d[v] performs a push operation costing O(log n). There are at most m such improvements overall, so pushes account for O(m log n). Each extract-min (pop) also costs O(log n) and occurs at most O(m + n) times in the lazy approach, but effective bounds reduce to O((m + n) log n). Thus, the standard time complexity is O((n + m) log n), which is near-linear on sparse graphs where

m = O (n

). Space complexity is O(n + m): O(m) for the adjacency list and O(n) for distance, parent, and visited/settled state. The priority queue may hold up to O(m) entries in the lazy variant, but practical memory remains manageable within typical constraints. For dense graphs (m ≈

n^{2}

), the overhead of O(log n) heap operations can dominate. An array-based implementation that linearly scans for the next minimal unsettled vertex each iteration runs in O(

n^{2}

+ m), which simplifies to O(

n^{2}

), and often performs well due to better cache locality and constant factors. Its space is O(

n^{2}

) if using an adjacency matrix or O(n + m) with adjacency lists but still O(

n^{2}

) time due to the scan. Special cases: if all edge weights are 0 or 1, 0–1 BFS with a deque achieves O(n + m) time. If negative edges exist, Dijkstra is incorrect; Bellman–Ford runs in O(nm) and detects negative cycles. Advanced heaps (e.g., Fibonacci heaps) can theoretically reduce decrease-key cost, achieving O(m + n log n), but are uncommon in practice due to large constants and complexity.

Code Examples

Dijkstra with priority_queue (adjacency list) + path reconstruction + early exit

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge {
5     int to;
6     long long w;
7 };
8 
9 const long long INF = (long long)4e18; // large INF to avoid overflow on additions
10 
11 // Runs Dijkstra from source s. If target t >= 0, exits early once t is finalized.
12 // Returns pair of (dist, parent) arrays.
13 pair<vector<long long>, vector<int>> dijkstra(int n, const vector<vector<Edge>>& g, int s, int t = -1) {
14     vector<long long> dist(n, INF);
15     vector<int> parent(n, -1);
16     vector<char> settled(n, 0);
17 
18     using P = pair<long long,int>; // {distance, vertex}
19     priority_queue<P, vector<P>, greater<P>> pq; // min-heap
20 
21     dist[s] = 0;
22     pq.push({0, s});
23 
24     while (!pq.empty()) {
25         auto [d, u] = pq.top(); pq.pop();
26         if (d != dist[u]) continue;      // outdated entry (lazy deletion)
27         settled[u] = 1;                  // u's shortest distance is finalized
28         if (u == t) break;               // early exit if target finalized
29         for (const auto& e : g[u]) {
30             int v = e.to;
31             long long w = e.w;
32             // Non-negative weights required for correctness
33             if (dist[v] > dist[u] + w) {
34                 dist[v] = dist[u] + w;
35                 parent[v] = u;
36                 pq.push({dist[v], v});
37             }
38         }
39     }
40     return {dist, parent};
41 }
42 
43 // Utility to reconstruct path from s to t using parent array
44 vector<int> reconstruct_path(int s, int t, const vector<int>& parent) {
45     vector<int> path;
46     if (t < 0) return path;
47     for (int v = t; v != -1; v = parent[v]) path.push_back(v);
48     reverse(path.begin(), path.end());
49     if (path.empty() || path.front() != s) path.clear(); // unreachable
50     return path;
51 }
52 
53 int main() {
54     ios::sync_with_stdio(false);
55     cin.tie(nullptr);
56 
57     // Example graph (undirected) from CLRS classic figure
58     int n = 6;
59     vector<vector<Edge>> g(n);
60     auto add_undirected = [&](int u, int v, long long w){
61         g[u].push_back({v, w});
62         g[v].push_back({u, w});
63     };
64     add_undirected(0, 1, 7);
65     add_undirected(0, 2, 9);
66     add_undirected(0, 5, 14);
67     add_undirected(1, 2, 10);
68     add_undirected(1, 3, 15);
69     add_undirected(2, 3, 11);
70     add_undirected(2, 5, 2);
71     add_undirected(3, 4, 6);
72     add_undirected(4, 5, 9);
73 
74     int s = 0, t = 4; // source and target
75     auto [dist, parent] = dijkstra(n, g, s, t); // early exit at t
76 
77     cout << "Distances from " << s << ":\n";
78     for (int i = 0; i < n; ++i) {
79         if (dist[i] >= INF/2) cout << i << ": INF\n";
80         else cout << i << ": " << dist[i] << "\n";
81     }
82 
83     auto path = reconstruct_path(s, t, parent);
84     cout << "\nPath from " << s << " to " << t << ": ";
85     if (path.empty()) cout << "unreachable\n";
86     else {
87         for (int i = 0; i < (int)path.size(); ++i) {
88             if (i) cout << " ";
89             cout << path[i];
90         }
91         cout << "\nTotal cost: " << dist[t] << "\n";
92     }
93     return 0;
94 }
95

This is the classic adjacency-list Dijkstra using a min-heap. It uses a lazy strategy: we may push multiple entries per vertex, but we ignore any popped entry whose distance does not match the current best. parent[] records predecessors for path reconstruction. An optional early exit stops the algorithm as soon as the target vertex is finalized, which is safe because the popped distance is guaranteed to be the shortest.

Time: O((|V| + |E|) log |V|)Space: O(|V| + |E|)

Dijkstra for dense graphs using O(|V|^2) array scan (adjacency matrix)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 const long long INF = (long long)4e18;
5 
6 int main() {
7     ios::sync_with_stdio(false);
8     cin.tie(nullptr);
9 
10     // Example: adjacency matrix for a dense directed graph
11     int n = 5;
12     vector<vector<long long>> w(n, vector<long long>(n, INF));
13     for (int i = 0; i < n; ++i) w[i][i] = 0;
14 
15     auto add_edge = [&](int u, int v, long long c){ w[u][v] = min(w[u][v], c); };
16     // Populate a fairly dense graph
17     add_edge(0,1,3); add_edge(0,2,1); add_edge(0,3,9); add_edge(0,4,8);
18     add_edge(1,2,4); add_edge(1,3,2); add_edge(1,4,7);
19     add_edge(2,1,6); add_edge(2,3,3); add_edge(2,4,5);
20     add_edge(3,1,1); add_edge(3,2,2); add_edge(3,4,2);
21     add_edge(4,1,9); add_edge(4,2,3); add_edge(4,3,4);
22 
23     int s = 0; // source
24     vector<long long> dist(n, INF);
25     vector<char> used(n, 0);
26 
27     dist[s] = 0;
28     for (int iter = 0; iter < n; ++iter) {
29         int u = -1;
30         long long best = INF;
31         // Find the unsettled vertex with minimal tentative distance
32         for (int v = 0; v < n; ++v) {
33             if (!used[v] && dist[v] < best) {
34                 best = dist[v];
35                 u = v;
36             }
37         }
38         if (u == -1) break; // remaining vertices are unreachable
39         used[u] = 1;
40         // Relax all neighbors via adjacency matrix
41         for (int v = 0; v < n; ++v) {
42             if (w[u][v] >= INF/2) continue; // no edge
43             if (dist[v] > dist[u] + w[u][v]) {
44                 dist[v] = dist[u] + w[u][v];
45             }
46         }
47     }
48 
49     cout << "Distances from " << s << ":\n";
50     for (int i = 0; i < n; ++i) {
51         if (dist[i] >= INF/2) cout << i << ": INF\n";
52         else cout << i << ": " << dist[i] << "\n";
53     }
54     return 0;
55 }
56

This implementation avoids a heap and linearly scans for the next vertex to settle in O(|V|) time per iteration. With an adjacency matrix, relaxing a chosen vertex also takes O(|V|), making the total O(|V|^2). This is often competitive for dense graphs or when |V| is small.

Time: O(|V|^2)Space: O(|V|^2)

Dijkstra on a weighted grid (min-cost path from top-left to bottom-right)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Node { long long d; int r, c; };
5 struct Cmp { bool operator()(const Node& a, const Node& b) const { return a.d > b.d; } };
6 
7 const long long INF = (long long)4e18;
8 
9 int main() {
10     ios::sync_with_stdio(false);
11     cin.tie(nullptr);
12 
13     // Example grid of costs: cost to enter a cell (including start)
14     vector<vector<int>> cost = {
15         {1, 3, 1, 9, 2},
16         {2, 8, 2, 1, 3},
17         {3, 4, 1, 7, 1},
18         {9, 1, 5, 2, 4},
19         {2, 2, 2, 1, 1}
20     };
21     int n = (int)cost.size();
22     int m = (int)cost[0].size();
23 
24     vector<vector<long long>> dist(n, vector<long long>(m, INF));
25     priority_queue<Node, vector<Node>, Cmp> pq;
26 
27     auto inside = [&](int r, int c){ return r>=0 && r<n && c>=0 && c<m; };
28     const int dr[4] = {1,-1,0,0};
29     const int dc[4] = {0,0,1,-1};
30 
31     dist[0][0] = cost[0][0];
32     pq.push({dist[0][0], 0, 0});
33 
34     while (!pq.empty()) {
35         auto cur = pq.top(); pq.pop();
36         if (cur.d != dist[cur.r][cur.c]) continue; // outdated
37         if (cur.r == n-1 && cur.c == m-1) break;   // early exit at target
38         for (int k = 0; k < 4; ++k) {
39             int nr = cur.r + dr[k], nc = cur.c + dc[k];
40             if (!inside(nr, nc)) continue;
41             long long w = cost[nr][nc]; // moving cost to enter neighbor cell
42             if (dist[nr][nc] > dist[cur.r][cur.c] + w) {
43                 dist[nr][nc] = dist[cur.r][cur.c] + w;
44                 pq.push({dist[nr][nc], nr, nc});
45             }
46         }
47     }
48 
49     cout << "Minimum path cost: " << dist[n-1][m-1] << "\n";
50     return 0;
51 }
52

Treat each cell as a vertex. There is an edge of weight equal to the cost of entering the neighbor cell. The algorithm computes the minimal cost to reach the bottom-right cell, using early exit once the target is popped from the heap.

Time: O(n m log(n m)) for an n by m gridSpace: O(n m)

Multi-source Dijkstra (nearest facility distance)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge { int to; long long w; };
5 const long long INF = (long long)4e18;
6 
7 vector<long long> multi_source_dijkstra(int n, const vector<vector<Edge>>& g, const vector<int>& sources) {
8     vector<long long> dist(n, INF);
9     using P = pair<long long,int>;
10     priority_queue<P, vector<P>, greater<P>> pq;
11 
12     // Initialize all sources with distance 0
13     for (int s : sources) {
14         dist[s] = 0;
15         pq.push({0, s});
16     }
17 
18     while (!pq.empty()) {
19         auto [d, u] = pq.top(); pq.pop();
20         if (d != dist[u]) continue; // skip outdated
21         for (const auto& e : g[u]) {
22             int v = e.to; long long w = e.w;
23             if (dist[v] > dist[u] + w) {
24                 dist[v] = dist[u] + w;
25                 pq.push({dist[v], v});
26             }
27         }
28     }
29     return dist;
30 }
31 
32 int main() {
33     ios::sync_with_stdio(false);
34     cin.tie(nullptr);
35 
36     int n = 7;
37     vector<vector<Edge>> g(n);
38     auto add_undirected = [&](int u, int v, long long w){ g[u].push_back({v,w}); g[v].push_back({u,w}); };
39 
40     add_undirected(0,1,4); add_undirected(1,2,3); add_undirected(2,3,5);
41     add_undirected(3,4,2); add_undirected(4,5,6); add_undirected(5,6,1);
42     add_undirected(1,4,4); add_undirected(2,5,2);
43 
44     vector<int> sources = {0, 6}; // facilities at nodes 0 and 6
45     auto dist = multi_source_dijkstra(n, g, sources);
46 
47     cout << "Distance to nearest facility (0 or 6):\n";
48     for (int i = 0; i < n; ++i) cout << i << ": " << dist[i] << "\n";
49     return 0;
50 }
51

By pushing multiple starting vertices with initial distance 0, Dijkstra computes, for every node, the distance to its closest source. This is a standard trick for nearest-hub or multi-base problems.

Time: O((|V| + |E|) log |V|)Space: O(|V| + |E|)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Edge {
5	int to;
6	long long w;
7	};
8
9	const long long INF = (long long)4e18; // large INF to avoid overflow on additions
10
11	// Runs Dijkstra from source s. If target t >= 0, exits early once t is finalized.
12	// Returns pair of (dist, parent) arrays.
13	pair<vector<long long>, vector<int>> dijkstra(int n, const vector<vector<Edge>>& g, int s, int t = -1) {
14	vector<long long> dist(n, INF);
15	vector<int> parent(n, -1);
16	vector<char> settled(n, 0);
17
18	using P = pair<long long,int>; // {distance, vertex}
19	priority_queue<P, vector<P>, greater<P>> pq; // min-heap
20
21	dist[s] = 0;
22	pq.push({0, s});
23
24	while (!pq.empty()) {
25	auto [d, u] = pq.top(); pq.pop();
26	if (d != dist[u]) continue; // outdated entry (lazy deletion)
27	settled[u] = 1; // u's shortest distance is finalized
28	if (u == t) break; // early exit if target finalized
29	for (const auto& e : g[u]) {
30	int v = e.to;
31	long long w = e.w;
32	// Non-negative weights required for correctness
33	if (dist[v] > dist[u] + w) {
34	dist[v] = dist[u] + w;
35	parent[v] = u;
36	pq.push({dist[v], v});
37	}
38	}
39	}
40	return {dist, parent};
41	}
42
43	// Utility to reconstruct path from s to t using parent array
44	vector<int> reconstruct_path(int s, int t, const vector<int>& parent) {
45	vector<int> path;
46	if (t < 0) return path;
47	for (int v = t; v != -1; v = parent[v]) path.push_back(v);
48	reverse(path.begin(), path.end());
49	if (path.empty() \|\| path.front() != s) path.clear(); // unreachable
50	return path;
51	}
52
53	int main() {
54	ios::sync_with_stdio(false);
55	cin.tie(nullptr);
56
57	// Example graph (undirected) from CLRS classic figure
58	int n = 6;
59	vector<vector<Edge>> g(n);
60	auto add_undirected = [&](int u, int v, long long w){
61	g[u].push_back({v, w});
62	g[v].push_back({u, w});
63	};
64	add_undirected(0, 1, 7);
65	add_undirected(0, 2, 9);
66	add_undirected(0, 5, 14);
67	add_undirected(1, 2, 10);
68	add_undirected(1, 3, 15);
69	add_undirected(2, 3, 11);
70	add_undirected(2, 5, 2);
71	add_undirected(3, 4, 6);
72	add_undirected(4, 5, 9);
73
74	int s = 0, t = 4; // source and target
75	auto [dist, parent] = dijkstra(n, g, s, t); // early exit at t
76
77	cout << "Distances from " << s << ":\n";
78	for (int i = 0; i < n; ++i) {
79	if (dist[i] >= INF/2) cout << i << ": INF\n";
80	else cout << i << ": " << dist[i] << "\n";
81	}
82
83	auto path = reconstruct_path(s, t, parent);
84	cout << "\nPath from " << s << " to " << t << ": ";
85	if (path.empty()) cout << "unreachable\n";
86	else {
87	for (int i = 0; i < (int)path.size(); ++i) {
88	if (i) cout << " ";
89	cout << path[i];
90	}
91	cout << "\nTotal cost: " << dist[t] << "\n";
92	}
93	return 0;
94	}
95

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	const long long INF = (long long)4e18;
5
6	int main() {
7	ios::sync_with_stdio(false);
8	cin.tie(nullptr);
9
10	// Example: adjacency matrix for a dense directed graph
11	int n = 5;
12	vector<vector<long long>> w(n, vector<long long>(n, INF));
13	for (int i = 0; i < n; ++i) w[i][i] = 0;
14
15	auto add_edge = [&](int u, int v, long long c){ w[u][v] = min(w[u][v], c); };
16	// Populate a fairly dense graph
17	add_edge(0,1,3); add_edge(0,2,1); add_edge(0,3,9); add_edge(0,4,8);
18	add_edge(1,2,4); add_edge(1,3,2); add_edge(1,4,7);
19	add_edge(2,1,6); add_edge(2,3,3); add_edge(2,4,5);
20	add_edge(3,1,1); add_edge(3,2,2); add_edge(3,4,2);
21	add_edge(4,1,9); add_edge(4,2,3); add_edge(4,3,4);
22
23	int s = 0; // source
24	vector<long long> dist(n, INF);
25	vector<char> used(n, 0);
26
27	dist[s] = 0;
28	for (int iter = 0; iter < n; ++iter) {
29	int u = -1;
30	long long best = INF;
31	// Find the unsettled vertex with minimal tentative distance
32	for (int v = 0; v < n; ++v) {
33	if (!used[v] && dist[v] < best) {
34	best = dist[v];
35	u = v;
36	}
37	}
38	if (u == -1) break; // remaining vertices are unreachable
39	used[u] = 1;
40	// Relax all neighbors via adjacency matrix
41	for (int v = 0; v < n; ++v) {
42	if (w[u][v] >= INF/2) continue; // no edge
43	if (dist[v] > dist[u] + w[u][v]) {
44	dist[v] = dist[u] + w[u][v];
45	}
46	}
47	}
48
49	cout << "Distances from " << s << ":\n";
50	for (int i = 0; i < n; ++i) {
51	if (dist[i] >= INF/2) cout << i << ": INF\n";
52	else cout << i << ": " << dist[i] << "\n";
53	}
54	return 0;
55	}
56

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Node { long long d; int r, c; };
5	struct Cmp { bool operator()(const Node& a, const Node& b) const { return a.d > b.d; } };
6
7	const long long INF = (long long)4e18;
8
9	int main() {
10	ios::sync_with_stdio(false);
11	cin.tie(nullptr);
12
13	// Example grid of costs: cost to enter a cell (including start)
14	vector<vector<int>> cost = {
15	{1, 3, 1, 9, 2},
16	{2, 8, 2, 1, 3},
17	{3, 4, 1, 7, 1},
18	{9, 1, 5, 2, 4},
19	{2, 2, 2, 1, 1}
20	};
21	int n = (int)cost.size();
22	int m = (int)cost[0].size();
23
24	vector<vector<long long>> dist(n, vector<long long>(m, INF));
25	priority_queue<Node, vector<Node>, Cmp> pq;
26
27	auto inside = [&](int r, int c){ return r>=0 && r<n && c>=0 && c<m; };
28	const int dr[4] = {1,-1,0,0};
29	const int dc[4] = {0,0,1,-1};
30
31	dist[0][0] = cost[0][0];
32	pq.push({dist[0][0], 0, 0});
33
34	while (!pq.empty()) {
35	auto cur = pq.top(); pq.pop();
36	if (cur.d != dist[cur.r][cur.c]) continue; // outdated
37	if (cur.r == n-1 && cur.c == m-1) break; // early exit at target
38	for (int k = 0; k < 4; ++k) {
39	int nr = cur.r + dr[k], nc = cur.c + dc[k];
40	if (!inside(nr, nc)) continue;
41	long long w = cost[nr][nc]; // moving cost to enter neighbor cell
42	if (dist[nr][nc] > dist[cur.r][cur.c] + w) {
43	dist[nr][nc] = dist[cur.r][cur.c] + w;
44	pq.push({dist[nr][nc], nr, nc});
45	}
46	}
47	}
48
49	cout << "Minimum path cost: " << dist[n-1][m-1] << "\n";
50	return 0;
51	}
52

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Edge { int to; long long w; };
5	const long long INF = (long long)4e18;
6
7	vector<long long> multi_source_dijkstra(int n, const vector<vector<Edge>>& g, const vector<int>& sources) {
8	vector<long long> dist(n, INF);
9	using P = pair<long long,int>;
10	priority_queue<P, vector<P>, greater<P>> pq;
11
12	// Initialize all sources with distance 0
13	for (int s : sources) {
14	dist[s] = 0;
15	pq.push({0, s});
16	}
17
18	while (!pq.empty()) {
19	auto [d, u] = pq.top(); pq.pop();
20	if (d != dist[u]) continue; // skip outdated
21	for (const auto& e : g[u]) {
22	int v = e.to; long long w = e.w;
23	if (dist[v] > dist[u] + w) {
24	dist[v] = dist[u] + w;
25	pq.push({dist[v], v});
26	}
27	}
28	}
29	return dist;
30	}
31
32	int main() {
33	ios::sync_with_stdio(false);
34	cin.tie(nullptr);
35
36	int n = 7;
37	vector<vector<Edge>> g(n);
38	auto add_undirected = [&](int u, int v, long long w){ g[u].push_back({v,w}); g[v].push_back({u,w}); };
39
40	add_undirected(0,1,4); add_undirected(1,2,3); add_undirected(2,3,5);
41	add_undirected(3,4,2); add_undirected(4,5,6); add_undirected(5,6,1);
42	add_undirected(1,4,4); add_undirected(2,5,2);
43
44	vector<int> sources = {0, 6}; // facilities at nodes 0 and 6
45	auto dist = multi_source_dijkstra(n, g, sources);
46
47	cout << "Distance to nearest facility (0 or 6):\n";
48	for (int i = 0; i < n; ++i) cout << i << ": " << dist[i] << "\n";
49	return 0;
50	}
51