最短路
Dijkstra 算法
思路
Dijkstra 算法,采用贪心思想,在某一时刻如果 \(dis\) 数组中 \(dis_u\) 最小,那么就固定 \(u\),\(dis_u\) 一定是 \(1\rightarrow u\) 的最短路径,然后我们再通过 \(u\) 更新与 \(u\) 有边相连的 \(v\),如果 \(dis_v > dis_u + w\),那么 \(dis_v = dis_u + w\) 然后再找 \(dis\) 数组中最小的这样循环直到没有点可以被更新。
时间复杂度:\(O(m \log n)\)。
代码
P4779 【模板】单源最短路径(标准版)代码:
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 100010, M = 400010;
struct edge {
int to, next, w;
}e[M];
int head[N], idx;
void add(int u, int v, int w) {
idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
}
int dis[N];
bool vis[N];
void dijkstra(int s) {
priority_queue<PII, vector<PII>, greater<PII> > q;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
q.push({0, s});
dis[s] = 0;
while (q.size()) {
int t = q.top().second;
q.pop();
if (vis[t]) continue;
vis[t] = true;
for (int i = head[t]; i; i = e[i].next) {
int to = e[i].to;
if (dis[to] > dis[t] + e[i].w) {
dis[to] = dis[t] + e[i].w;
q.push({dis[to], to});
}
}
}
}
int n, m, s;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
cout << '\n';
return 0;
}
Bellman-Ford 算法
思路
Bellman-Ford 算法是通过对图松弛 \(n - 1\) 轮,第 \(i\) 轮可以保证从源点走出去 \(i\) 条边到达的点都已经更新完毕,因为任意两点之间的边数不超过 \(n - 1\),所以松弛 \(n - 1\) 轮即可。
如果第 \(n\) 轮还可以进行松弛,说明有负环。
代码
P3371 【模板】单源最短路径(弱化版)可以拿到 70 分。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 500010, INF = (1ll << 31) - 1;
struct edge {
int u, v, w;
} e[M];
int dis[N];
int n, m, s;
void bellmanford(int u) {
for (int i = 1; i <= n; i++) dis[i] = INF;
dis[u] = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
if (dis[e[j].v] > 1ll * dis[e[j].u] + e[j].w) {
dis[e[j].v] = dis[e[j].u] + e[j].w;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s;
int u, v, w;
for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
bellmanford(s);
for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
return 0;
}
SPFA 算法
思路
Bellman-Ford 算法的优化版本,即只有一个点被更新的时候才入队对其他点进行更新。
时间复杂度:\(O(nm)\)。
代码
P3371 【模板】单源最短路径(弱化版)代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 500010, INF = (1ll << 31) - 1;
struct edge {
int to, next, w;
} e[M];
int head[N], idx;
void add(int u, int v, int w) {
idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
}
int dis[N];
bool st[N];
queue<int> q;
int n, m, s;
void spfa(int u) {
q.push(u);
st[u] = true;
for (int i = 1; i <= n; i++) dis[i] = INF;
dis[u] = 0;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = head[t]; i; i = e[i].next) {
int to = e[i].to;
if (dis[to] > 1ll * dis[t] + e[i].w) {
dis[to] = dis[t] + e[i].w;
if (!st[to]) {
st[to] = true;
q.push(to);
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s;
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
add(u, v, w);
}
spfa(s);
for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
return 0;
}
最长路
SPFA 求最长路
思路
我们将 SPFA 求最短路的算法中的更新信息 if (dis[to] > dis[t] + e[i].w)
换成 if (dis[to] < dis[t] + e[i].w)
就可以了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1510, M = 50010;
struct edge {
int to, next, w;
} e[M];
int head[N], idx;
void add(int u, int v, int w) {
idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
}
int dis[N];
bool st[N];
queue<int> q;
void spfa(int u) {
q.push(u);
st[u] = true;
memset(dis, 0xcf, sizeof(dis));
dis[u] = 0;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = head[t]; i; i = e[i].next) {
int to = e[i].to;
if (dis[to] < dis[t] + e[i].w) {
dis[to] = dis[t] + e[i].w;
if (!st[to]) {
st[to] = true;
q.push(to);
}
}
}
}
}
int n, m;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
add(u, v, w);
}
spfa(1);
if (dis[n] == 0xcfcfcfcf) cout << "-1\n";
else cout << dis[n] << '\n';
return 0;
}
标签:图论,idx,int,短路,head,cin,st,模板,dis
From: https://www.cnblogs.com/Yuan-Jiawei/p/18315366