当前位置：首页 > news >正文

题解：P4779 【模板】单源最短路径（标准版）

news 2025/10/7 10:40:29

题目传送门

算法分析

本题要求计算单源最短路径，并且边权非负，适合使用Dijkstra 算法。Dijkstra 算法是一种贪心算法，用于计算带权有向图或无向图中单个源节点到所有其他节点的最短路径。

为什么选择 Dijkstra 算法？

Dijkstra 算法要求所有边权非负。在本题中，题目明确说明边权 \(0 ≤ wi ≤ 10^9\)，完全符合 Dijkstra 的应用条件。若存在负权边，Dijkstra 可能会得到错误结果，此时需使用 Bellman-Ford 或 SPFA 算法。
朴素实现：\(O (n²)\)，适用于节点数较少的稠密图。
优先队列优化：\(O ((m+n) logn)\)，其中m为边数，n为节点数。本题数据范围为\(1 ≤ n ≤ 10^5\) 和 \(1 ≤ m ≤ 2×10^5\)，使用优先队列优化后的 Dijkstra 可以高效处理。
Dijkstra 算法是确定性算法，对于相同的输入，结果唯一且可预测。相比之下，某些近似算法或启发式算法（如 A*）可能需要额外信息（如启发函数），而 Dijkstra 仅依赖图的结构和边权。
本题要求计算从起点s到所有其他节点的最短路径，Dijkstra 算法正是为此场景设计。若仅需计算特定终点的最短路径，可在找到终点后提前终止算法。

本题为何不选择其他算法？

Floyd-Warshall 算法：时间复杂度 \(O (n³)\)，适用于多源最短路径，但本题仅需求单源路径，使用该算法会导致超时。
Bellman-Ford/SPFA 算法：适用于含负权边的图，时间复杂度较高\(（O (mn)）\)，在本题的非负权图中效率低于 Dijkstra。

注意事项

由于边权非负，Dijkstra 算法可以正确处理本题。
使用优先队列时，由于 C++ 的优先队列默认是最大堆，因此存储距离的负值来模拟最小堆。
初始化距离数组时，使用 \(2147483647\) 表示无穷大，避免溢出。

算法思路

初始化所有节点的距离为无穷大，起点的距离为\(0\)。
使用优先队列（最小堆）来维护待处理的节点，优先处理距离最小的节点。
每次从优先队列中取出距离最小的节点，遍历其所有邻接边，更新邻接节点的距离。
重复步骤3，直到优先队列为空。

代码实现

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
#define MP(x, y) make_pair(x, y)
#define Pair pair<int, int> 
using namespace std;
const int MAXN = 1e6 + 10, INF = 2147483646, B = 19;// 快速读入函数
inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = 1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int N, M, S;// 边的结构体
struct Edge {int u, v, w, nxt;
};
Edge E[MAXN];
int head[MAXN], num = 1;// 添加边
void AddEdge(int x, int y, int z) {E[num] = (Edge) {x, y, z, head[x]};head[x] = num++;
}int dis[MAXN], vis[MAXN];
priority_queue<Pair> q; // Dijkstra算法实现
void Dij() {// 初始化距离数组for(int i = 1; i <= N; i++) dis[i] = 2147483647;dis[S] = 0; q.push(MP(0, S));while(!q.empty()) {int p = q.top().second; q.pop();if(vis[p]) continue; vis[p] = 1;// 遍历当前节点的所有邻接边for(int i = head[p]; i != -1; i = E[i].nxt) {int to = E[i].v;// 松弛操作if(dis[to] > dis[p] + E[i].w) dis[to] = dis[p] + E[i].w,q.push(MP(-dis[to], to));}}// 输出结果for(int i = 1; i <= N; i++)printf("%d ", dis[i]);
}int main() {// 初始化头数组memset(head, -1, sizeof(head));// 读入数据N = read(); M = read(); S = read();for(int i = 1; i <= M; i++) {int x = read(), y = read(), z = read();AddEdge(x, y, z);}// 执行Dijkstra算法Dij();return 0;
}