This article breaks down the Luogu P3371 single-source shortest path template problem, focusing on graph construction, relaxation, and stale-state filtering in heap-optimized Dijkstra. It addresses common pain points such as confusing shortest path logic, error-prone code, and unclear complexity. Keywords: Dijkstra, single-source shortest path, priority queue.
Technical specification snapshot
| Parameter | Details |
|---|---|
| Problem | Luogu P3371 [Template] Single-Source Shortest Path (Simplified) |
| Core algorithm | Heap-optimized Dijkstra |
| Implementation language | C++ |
| Graph storage | Adjacency list |
| Core data structures | priority_queue, vector, pair |
| Applicable graph type | Directed graphs with non-negative edge weights |
| Time complexity | O((n+m) log n) |
| Original source platform | Blog Garden / Luogu solution |
| Star count | Not provided |
| Core dependencies | bits/stdc++.h, STL |
The essence of this problem is computing single-source shortest paths on a non-negative weighted graph.
P3371 is one of the most classic shortest path template problems: given a source node s, output the shortest distance from s to every node. Because all edge weights are non-negative, Dijkstra is the standard solution. When the input size grows, you typically combine it with a priority queue for heap optimization.
The value of the original material lies in identifying three core components: the dis array stores the current shortest known distances, the adjacency list stores edges, and the priority queue quickly extracts the node with the smallest current distance. Together, these three pieces form the minimum working loop of a correct implementation.
You can understand Dijkstra as a process of confirming optimal answers step by step.
The algorithm starts from the source node, sets dis[s] to , and initializes all other distances to infinity. Each time, it extracts the node u with the smallest distance among the unprocessed candidates, then tries to use u to update the shortest distances of its adjacent nodes v. This step is called relaxation.
If dis[u] + w < dis[v], then the path from u to v is shorter than the currently known one. You should update dis[v] immediately and push the new state into the heap. Repeat this process until the heap becomes empty, and the shortest path computation is complete.
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w; // Found a shorter path, update the shortest distance
q.push({dis[v], v}); // Push the new distance into the min-heap for future expansion
}This code performs the core relaxation step of the shortest path algorithm.
An adjacency list is more suitable than an adjacency matrix for sparse graph problems like this.
The original article specifically highlights the difference between adjacency lists and adjacency matrices, and that distinction matters here. P3371 is fundamentally a better fit for an adjacency list because you only traverse edges that actually exist. This saves space and improves traversal efficiency.
In an adjacency list, graph[u] stores all outgoing edges from node u. Each edge is usually represented as {v, w}, where v is the destination node and w is the edge weight. This design aligns naturally with Dijkstra’s expansion pattern of traversing all outgoing edges from the current node.
vector<vector<pair<int, int>>> graph(n + 1);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w}); // Store a directed edge from u to v with weight w
}This code builds a directed weighted graph using an adjacency list.
The key to heap optimization is not modifying elements inside the heap, but allowing duplicate states.
For many beginners, the most confusing part is not Dijkstra itself, but why the priority queue can contain multiple distance records for the same node. The reason is simple: STL’s priority_queue does not support in-place updates of existing elements.
So when you discover a shorter path, the correct approach is not to update the old entry, but to insert a new one directly. The old record does not disappear immediately. When it gets popped later, you skip it using stale-state filtering.
int d = q.top().first;
int u = q.top().second;
q.pop();
if (d > dis[u]) continue; // This state is stale, so skip it directlyThis code filters out invalid heap states and prevents repeated expansion of incorrect paths.
The original code contains an inconsistent explanation of field meaning, so you should correct that interpretation.
One part of the original explanation says graph[u].push_back({w,v}), while the actual code uses graph[u].push_back({v, w}). The implementation is the source of truth: edge.first is the destination node, and edge.second is the edge weight.
If you reverse that meaning, later traversal will treat node IDs as edge weights and edge weights as node IDs, which breaks the program logic completely. The graph construction format and the unpacking logic during traversal must remain strictly consistent.
A safer style is to name variables explicitly and reduce the ambiguity of pair semantics.
for (auto &edge : graph[u]) {
int v = edge.first; // Destination node
int w = edge.second; // Edge weight
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}This code traverses all outgoing edges of node u and tries to update the distances of adjacent nodes.
The images are mainly for author or page presentation and do not carry algorithm details.
AI Visual Insight: This image is an author avatar and does not contain technical information such as algorithm flow, code structure, graph models, or performance metrics. It does not directly help with understanding the Dijkstra implementation.
AI Visual Insight: This image appears to be site advertising or promotional visual material. It does not show the single-source shortest path problem, graph structure, heap optimization process, or complexity analysis, so you can ignore it during technical reading.
AI Visual Insight: This animated image is used as a page-sharing prompt. It does not involve algorithm execution state, input-output examples, or code logic, so it adds no technical value to the solution itself.
This C++ implementation is enough to pass the template problem, but two engineering details are still worth improving.
First, the original code uses #define int long long, but sets INF to INT_MAX. That is not semantically consistent. A safer approach is to use long long explicitly and pair it with a much larger infinity value such as 4e18.
Second, when a node is unreachable, the template problem often requires outputting 2147483647. That is a problem-specific convention, not a universal rule of shortest path algorithms. Be careful when reusing this code elsewhere.
const long long INF = 4e18;
vector<long long> dis(n + 1, INF); // Use long long consistently for distances to avoid overflow riskThis code improves consistency and safety in the distance array and infinity definition.
What developers really need to master in this problem is the algorithm invariant.
You should always keep three facts clear: dis[x] represents the currently known shortest distance, the heap top state is not always valid, and Dijkstra only works directly on graphs with non-negative edge weights. If you keep these three constraints in mind, your implementation is much less likely to go wrong.
From a learning perspective, this problem is also a key transition point from BFS shortest path to weighted shortest path. Unweighted graphs rely on level-order expansion, while weighted graphs rely on expanding the currently shortest state first. That essential difference is exactly why the priority queue matters.
FAQ
Why not use BFS for this problem?
BFS only applies to graphs where all edge weights are equal or can be treated as unweighted. In P3371, edge weights vary, so you must expand nodes according to the smallest current accumulated cost. That is why Dijkstra is the correct choice.
Why can the same node appear multiple times in the priority queue?
Because STL’s priority queue cannot update an old distance in place. Every time you find a shorter path, you insert a new state directly. The old state remains in the heap and gets skipped later with if (d > dis[u]) continue; when popped.
When can Dijkstra not be used?
If the graph contains negative-weight edges, Dijkstra’s greedy assumption breaks, and the result may be incorrect. In that case, consider algorithms such as Bellman-Ford, SPFA, or Johnson.
AI Readability Summary: Using Luogu P3371 as the example, this article reconstructs the standard heap-optimized Dijkstra solution by explaining the core workflow, adjacency list graph construction, stale-state filtering technique, and practical C++ implementation details. It helps developers quickly master the standard approach to single-source shortest path.