Translation Notice
This article was machine-translated using DeepSeek-R1.
- Original Version: Authored in Chinese by myself
- Accuracy Advisory: Potential discrepancies may exist between translations
- Precedence: The Chinese text shall prevail in case of ambiguity
- Feedback: Technical suggestions regarding translation quality are welcomed
Introduction
Dijkstra’s algorithm solves the single-source shortest path problem with non-negative edge weights in $\mathcal O(m\log m)$ or $\mathcal O(m\log n)$ time. This article details the algorithm’s principles, implementations, and two common optimizations.
Additionally, Dijkstra’s algorithm should not be overused. For multi-source shortest paths, while Dijkstra’s complexity is $\mathcal O(nm\log m)$, it’s often simpler to use Floyd with $\mathcal O(n^3)$ time if feasible.
Without further ado, let’s dive into the algorithm’s workflow.
Workflow
Divide nodes into two sets: $S$ (nodes with determined shortest path lengths) and $T$ (nodes with undetermined lengths). Initially, all nodes belong to $T$.
Let $d_v$ denote the distance from node $v$ to the source, and $s$ be the source. Initialize $d_s=0$ and $d=+\infin$ for all other nodes.
Repeat these steps until $T$ is empty:
- Select the node $v$ with the smallest $d$ from $T$ and move it to $S$.
- For each neighbor $u$ of $v$, perform relaxation:
dis[u] = min(dis[u], dis[v] + G[v][u]).
The simplest implementation follows below.
Implementations
Sample code is applicable to CF20C/Luogu. Input/output formats align with this problem. Constraints: $n,m\le 10^5,w_i\le 10^6$.
To output the shortest path, define an array $\mathrm{par}$ where $\mathrm{par}[i]$ represents the predecessor of node $i$ in the shortest path. Initialize $\mathrm{par}[s]=-1$.
When updating dis[u] = dis[v] + G[v][u], also set par[u] = v. Finally, backtrack from the destination using par.
Unoptimized Implementation
This brute-force approach strictly follows the algorithm with $\mathcal O(n^2)$ complexity, which fails the test case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 100005
using namespace std;
vector<pair<int, int>> G[maxn];
long long dis[maxn];
int par[maxn];
bool vis[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
G[--u].emplace_back(--v, c);
G[v].emplace_back(u, c);
}
// Dijkstra algorithm steps
// Initialization
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
dis[0] = 0LL, par[0] = -1; // Distance of the starting point is 0
while(true)
{
int v = n; // Virtual node with +INF distance
for(int i=0; i<n; i++)
if(!vis[i] && dis[i] < dis[v])
v = i;
if(v >= n - 1) break; // Exit if no valid node found
vis[v] = true; // Mark as visited
for(auto [u, d]: G[v])
if(dis[v] + d < dis[u]) // Check for a better path?
{
dis[u] = dis[v] + d; // Update distance
par[u] = v; // Update path
}
}
if(dis[n - 1] == dis[n]) // No solution (disconnected graph)
{
puts("-1");
return 0;
}
vector<int> path; // Store reversed path
int v = n - 1; // Backtrack from destination
while(v != -1)
{
path.push_back(v); // Add to path
v = par[v]; // Backtrack
}
for(int i=path.size()-1; i>=0; i--)
printf("%d ", path[i] + 1); // Output
return 0;
}
|
Test Result:
Priority Queue Optimization
Priority queues (binary heaps) support:
- Extracting min/max elements in $\mathcal O(\log n)$
- Inserting elements in $\mathcal O(\log n)$
This achieves $\mathcal O(m\log m)$ complexity:
- Initialize with $(s,0)$ in the queue.
- While queue not empty:
- Extract $(v,d)$. If $d \ne \mathrm{dis}[v]$, skip.
- Otherwise, relax edges and enqueue updated nodes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <cstdio>
#include <queue>
#define maxn 100005
#define INF 9223372036854775807LL
using namespace std;
using LL = long long;
using pli = pair<LL, int>;
vector<pair<int, int>> G[maxn];
LL dis[maxn];
int par[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
G[--u].emplace_back(--v, c);
G[v].emplace_back(u, c);
}
for(int i=1; i<n; i++) dis[i] = INF;
par[0] = -1;
priority_queue<pli, vector<pli>, greater<pli>> q;
q.emplace(0LL, 0);
while(!q.empty())
{
auto [d, v] = q.top(); q.pop();
if(dis[v] == d)
for(auto [u, w]: G[v])
if(d + w < dis[u])
par[u] = v,
q.emplace(dis[u] = d + w, u);
}
if(dis[n - 1] == INF) { puts("-1"); return 0; }
vector<int> path;
int v = n - 1;
while(v != -1)
{
path.push_back(v);
v = par[v];
}
for(int i=path.size()-1; i>=0; i--)
printf("%d ", ++path[i]);
return 0;
}
|
AC, runtime: $93\text{ms}$
Set Optimization
Sets allow deletion of arbitrary elements in $\mathcal O(\log n)$. By removing obsolete entries, the set size never exceeds $N$, yielding $\mathcal O(m\log n)$ complexity. Generally less used but provided below:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <cstdio>
#include <vector>
#include <set>
#define maxn 100005
#define INF 9223372036854775807LL
using namespace std;
using LL = long long;
using pli = pair<LL, int>;
vector<pair<int, int>> G[maxn];
LL dis[maxn];
int par[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
G[--u].emplace_back(--v, c);
G[v].emplace_back(u, c);
}
for(int i=1; i<n; i++) dis[i] = INF;
par[0] = -1;
set<pli> s;
s.emplace(0LL, 0);
while(!s.empty())
{
auto it = s.begin(); s.erase(it);
auto [d, v] = *it;
for(auto [u, w]: G[v])
if(d + w < dis[u])
{
par[u] = v;
if(dis[u] != INF)
s.erase(pli(dis[u], u));
s.emplace(dis[u] = d + w, u);
}
}
if(dis[n - 1] == INF) { puts("-1"); return 0; }
vector<int> path;
int v = n - 1;
while(v != -1)
{
path.push_back(v);
v = par[v];
}
for(int i=path.size()-1; i>=0; i--)
printf("%d ", ++path[i]);
return 0;
}
|
AC, runtime: $78\text{ms}$
Conclusion
Dijkstra’s implementations summarized:
- Brute-force ($\mathcal O(n^2)$, TLE ;()
- Priority queue ($\mathcal O(m\log m)$, $93\text{ms}$ :|)
- Set ($\mathcal O(m\log n)$, $78\text{ms}$ :))