Shortest path
-
Dijkstra
不含负权边的有向或无向图的单源最短路。Greedy.
为何负权边不可：Dijkstra是贪心算法，而负权边会导致贪心算法失败，因为可能要绕远路。
a---3---b | | 4___c__-2时间复杂度分析：
\[
\displaylines{
T(n) = O(E)*dk_Q + O(V)*em_Q
}
\]
\(dk_Q\) means Decrease Key, we need to sort all edges once in the whole algo.
\(em_Q\) means Extract Min, for each vertex, we calculate the next shortest edge once.
| min heap | brute | |
|---|---|---|
| dk | logV (insert in heap) | 1 (no sorting) |
| em | logV (pop heap) | V^2 (one by one) |
So a min heap Dijkstra's time complexity is \(O((E+V)logV) \approx O(ElogV)\)
If considering we keep old edges in the heap, the operation may at worst be \(O(logE)\). So \(O((E+V)logE)\) is also right.
-
Bellman-Ford
含负权边的有向图的单源最短路。Dynamic Programming.
可以判断负环。
时间复杂度分析：\(O(EV)\)
-
SPFA
队列优化的BF算法，可以判断负环。
期望时间复杂度\(O(E)\)。
-
Floyd
\(O(V^3)\)
全局，动规，支持负权。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int maxv = 30005;
const int maxe = 150005;
const int maxw = 0x7fffffff;
int N, M;
struct edge {
int f, t, w;
edge() {}
edge(int u, int v, int w) :f(u), t(v), w(w) {}
};
vector<edge> edges;
vector<int> G[maxv];
// directed
void insert_edge(int a, int b, int c) {
edges.push_back(edge(a, b, c));
int s = edges.size() - 1;
G[a].push_back(s);
}
int dist[maxv], vis[maxv];
bool cmp(int a, int b) {
return dist[a] > dist[b];
}
void dijkstra(int s) {
for (int i = 1; i <= N; i++) {
dist[i] = maxw;
vis[i] = 0;
}
dist[s] = 0;
priority_queue<int, vector<int>, bool(*)(int, int)> que(cmp);
que.push(s);
while (!que.empty()) {
int u = que.top(); que.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int e = G[u][i];
int v = edges[e].t;
if (vis[v]) continue;
if (dist[v] > dist[u] + edges[e].w) {
dist[v] = dist[u] + edges[e].w;
que.push(v);
}
}
}
}
bool bellmanford(int s) {
for (int i = 1; i <= N; i++) dist[i] = maxw;
dist[s] = 0;
// run (N - 1) times
for (int k = 1; k < N; k++) {
// loop all edges
for (int i = 0; i < edges.size(); i++) {
int u = edges[i].f;
int v = edges[i].t;
if (dist[v] > dist[u] + edges[i].w)
dist[v] = dist[u] + edges[i].w;
}
}
// run 1 more time to detect negative loop.
for (int i = 0; i < edges.size(); i++) {
int u = edges[i].f;
int v = edges[i].t;
if (dist[v] > dist[u] + edges[i].w)
return true; // if the dist can still be updated, there must be a negative loop.
}
return false;
}
bool spfa(int s) {
for (int i = 1; i <= N; i++) dist[i] = maxw, vis[i] = 0; // vis is used as cnt
dist[s] = 0;
queue<int> q; // stack is also OK.
q.push(s);
while (!q.empty()) {
int p = q.front(); q.pop();
for (int i = 0; i < G[p].size(); i++) {
edge& e = edges[G[p][i]];
if (dist[e.t] > dist[e.f] + e.w) {
dist[e.t] = dist[e.f] + e.w;
q.push(e.t);
if (vis[e.t]++ >= N) return true; // if a point is enqueued for N times, there must be a negative loop.
}
}
}
return false;
}
int main() {
cin >> N >> M;
int a, b, c;
for (int i = 0; i < M; i++) {
cin >> a >> b >> c;
insert_edge(a, b, c);
}
dijkstra(1);
//bellmanford(1);
//s
cout << dist[N] << endl;
}
Examples
-
Currency Exchange
最长路+正环判断，设置源点为持有货币V，其他点初始化0，普通的按照规则计算路径即可。注意判断正环并不需要传播回源点，因为BF只额外传播一轮，源点有可能没有被更新到，但是只要有正环，多轮之后一定可以传回源点。
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> using namespace std; const int maxv = 105; const int maxe = 1005; struct edge { int f, t; double w, c; edge() {} edge(int u, int v, double w, double c) :f(u), t(v), w(w),c(c) {} }; vector<edge> edges; vector<int> G[maxv]; // directed void insert_edge(int a, int b, double w, double c) { edges.push_back(edge(a, b, w, c)); int s = edges.size() - 1; G[a].push_back(s); } int N, M, S; double V; int a, b; double c, d, e, f; double dist[maxv]; bool bellmanford(int s, double v) { memset(dist, 0, sizeof(dist)); dist[s] = v; for (int k = 1; k < N; k++) { bool flag = false; for (int u = 1; u <= N; u++) { for (int i = 0; i < G[u].size(); i++) { int e = G[u][i]; int v = edges[e].t; if (dist[v] < (dist[u] - edges[e].c) * edges[e].w) { dist[v] = (dist[u] - edges[e].c) * edges[e].w; flag = true; } } } if (!flag) break; // optim } for (int u = 1; u <= N; u++) { for (int i = 0; i < G[u].size(); i++) { int e = G[u][i]; int v = edges[e].t; if (dist[v] < (dist[u] - edges[e].c)*edges[e].w) return true; } } return false; } int main() { cin >> N >> M >> S >> V; for (int i = 0; i < M; i++) { cin >> a >> b >> c >> d >> e >> f; insert_edge(a, b, c, d); insert_edge(b, a, e, f); } cout << (bellmanford(S, V)?"YES":"NO") << endl; }
-
Warmholes
spfa version.
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> #include <stack> #include <vector> #include <algorithm> #define P pair<int,int> using namespace std; const int maxn = 505; const int inf = 0x3f3f3f3f; int N, M, W; struct edge { int f, t, w; edge() {} edge(int f, int t, int w) :f(f), t(t), w(w) {} }; vector<edge> G[maxn]; int dist[maxn], times[maxn]; bool spfa(int s) { fill(dist, dist + N + 1, inf); fill(times, times + N + 1, 0); dist[s] = 0; queue<int> q; // stack is also OK. q.push(s); while (!q.empty()) { int p = q.front(); q.pop(); for (int i = 0; i < G[p].size(); i++) { edge& e = G[p][i]; if (dist[e.t] > dist[e.f] + e.w) { dist[e.t] = dist[e.f] + e.w; q.push(e.t); if (times[e.t]++ >= N) return true; } } } return false; } int T, x, y, w; int main() { scanf("%d", &T); while (T--) { scanf("%d%d%d", &N, &M, &W); for (int i = 1; i <= N; i++) G[i].clear(); for (int i = 0; i < M; i++) { scanf("%d%d%d", &x, &y, &w); G[x].push_back(edge(x, y, w)); G[y].push_back(edge(y, x, w)); } for (int i = 0; i < W; i++) { scanf("%d%d%d", &x, &y, &w); G[x].push_back(edge(x, y, -w)); } cout << (spfa(1) ? "YES" : "NO") << endl; } }