Shortest path

Dijkstra

不含负权边的有向或无向图的单源最短路。Greedy.

为何负权边不可：Dijkstra是贪心算法，而负权边会导致贪心算法失败，因为可能要绕远路。
```
a---3---b
|       |
4___c__-2
```
时间复杂度分析：

\begin{matrix} T (n) = O (E) * d k_{Q} + O (V) * e m_{Q} \end{matrix}

$d k_{Q}$ means Decrease Key, we need to sort all edges once in the whole algo.

$e m_{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) l o g V) \approx O (E l o g V)$

If considering we keep old edges in the heap, the operation may at worst be $O (l o g E)$ . So $O ((E + V) l o g E)$ is also right.

Bellman-Ford

含负权边的有向图的单源最短路。Dynamic Programming.

可以判断负环。

时间复杂度分析： $O (E V)$

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;
  }
}