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

如果你总是写不对最短路（SPFA Dijkstra） ╥﹏╥...

news 2025/10/11 11:43:49

我有一个朋友总是因为最短路写不对而卡题……

SPFA

思路：

先把原点初始距离设好、入队并标记（即vis：是否在队列中），然后每次取队首节点并取消标记，将其邻接边松弛，若松弛成功则判断是否有负环（cnt >= 0），若暂时未发现负环则标记该节点并将其入队，直到发现负环或队列为空。

模板：

ver 1: 有重边，则用cnt记录入队次数而非松弛次数

点击查看代码

struct eg {int v, w;
};int dis[NM];
bool vis[NM];
int cnt[NM];bool spfa(vector<eg> g[], int s) {queue<int> q;memset(dis, 0x3f, (n+1)*sizeof(int));memset(cnt, 0, (n+1)*sizeof(int));memset(vis, 0, (n+1)*sizeof(bool));q.push(s);dis[s] = 0;vis[s] = true;cnt[s] ++;while (!q.empty()) {int u = q.front();q.pop();vis[u] = false;for (auto i : g[u]){int v = i.v, w = i.w;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (!vis[v]) {cnt[v]++;if (cnt[v] >= n) return false;vis[v] = true;q.push(v);}}}}return true;}

ver 2：与之相反，无重边则记录松弛次数：

点击查看代码

struct eg {int v, w;
};
vector<eg> g[NM];
int dis[NM], cnt[NM];
bool vis[NM];int n;
queue<int> q;
bool spfa(int s) {memset(dis, 0x3f, (n+1) * sizeof(int));q.push(s);vis[s] = true;dis[s] = 0;while (!q.empty()) {int u = q.front();q.pop();vis[u] = false;for (auto e : g[u]){int v = e.v, w = e.w;if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;cnt[v] = cnt[u] + 1;if (cnt[v] >= n) return false;if (!vis[v]) {vis[v] = true;q.push(v);}}}}return true;
}

注意：

视情况而定cnt的意义，具体见上
memset不要忘记
vis标记分别在原点入队、每一个点出队、入队时进行，不要少了
注意边权的数据类型

Dijkstra

思路：

先将原点初始距离设好，！！不要标记为确定最短路的集合（vis:是否已确定最短路）！！，加入优先队列（dis不为INF的待确定最短路的点集合）中。对于优先队列中的每一个点，取出dis最小的并判断它是否属于确定最短路的集合，若是则重新循环，若不是则标记为已经确定最短路，遍历该点的邻接边并松弛，若松弛成功则将链接的点加入优先队列中。

模板：

点击查看代码

struct ed {int v, w;
};struct nd {int dis, u;bool operator>(const nd& a) const { return dis > a.dis; }
};vector<ed> e[NM];
int dis[NM], vis[NM];
priority_queue<nd, vector<nd>, greater<nd>> q;void dij(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int));memset(vis, 0, (n + 1) * sizeof(int));dis[s] = 0;q.push({0, s});while (!q.empty()) {int u = q.top().u;q.pop();if (vis[u]) continue;vis[u] = 1;for (auto ed : e[u]) {int v = ed.v, w = ed.w;if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;q.push({dis[v], v});}}}
}