最短路算法（总结性，无Dij）

Floyd

利用中介点k进行操作

记f[x][y]为xy点之间的最短路径长度

其中f[x][y] = min(f[x][y], f[x][k] + f[k][y]);

即用k进行松弛操作

其中f[x][y]的取值

• 当xy有直接连边时：f[x][y]=w(x,y)

  当无直接连边时：f[x][y]=+∞

  当x=y时：f[x][y]=0

实现：

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

Bellman-Ford

松弛操作：

对于边u,v

松弛操作如下：

dis(v)=min(dis(v),dis(u,v))

这么做目的很明显，通过s→u的最短路+w(u,v)来更新s→v的最短路

实现：

#include <iostream>
#include <cstring>

using namespace std;
#define INF 0x7f7f7f7f

struct Edge{
    int u, v, w;
}edge[1000005];
int n, m, s, u, v, w, cnt,dis[10005];

void BellmanFord(){
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= cnt;j++){
            int u = edge[j].u, v = edge[j].v, w = edge[j].w;
            if(dis[u]==INF)
                continue;
            if(dis[v]>dis[u]+w)
                dis[v] = dis[u] + w;
        }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;
    while(m--){
        cin >> u >> v >> w;
        edge[++cnt].u = u;
        edge[cnt].v = v;
        edge[cnt].w = w;
    }
    BellmanFord();
    for (int i = 1; i <= n;i++)
        if (dis[i] == INF)
            cout << 2147483647 << ' ';
        else
            cout << dis[i] << ' ';
    return 0;
}

//判断负环的BellmanFord
struct Edge {
  int u, v, w;
};

vector<Edge> edge;

int dis[MAXN], u, v, w;
const int INF = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  bool flag = false;  // 判断一轮循环过程中是否发生松弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int j = 0; j < edge.size(); j++) {
      u = edge[j].u, v = edge[j].v, w = edge[j].w;
      if (dis[u] == INF) continue;
      // 无穷大与常数加减仍然为无穷大
      // 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        flag = true;
      }
    }
    // 没有可以松弛的边时就停止算法
    if (!flag) {
      break;
    }
  }
  // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
  return flag;
}

基于BellmanFord的SPFA

先给出标程：

#include <iostream>
#include <queue>
#include <cstring>

struct {
    int to, edgeWeight,next;
}edge[500005];
int head[10005], counter, distance[10005], s, n, m;

void addEdge(int u, int v,int edgeWeight) {
    edge[++counter].to = v;
    edge[counter].edgeWeight = edgeWeight;
    edge[counter].next = head[u];
    head[u] = counter;
}

void SPFA() {
    memset(distance, 0x7f, sizeof(distance));
    distance[s] = 0;
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u];i != 0;i = edge[i].next) {
            int v = edge[i].to, w = edge[i].edgeWeight;
            if (distance[v] > distance[u] + w) {
                distance[v] = distance[u] + w;
                q.push(v);
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> m >> s;
    while (m--) {
        int u, v, weight;
        std::cin >> u >> v >> weight;
        addEdge(u, v, weight);
    }
    SPFA();
    for (int i = 1;i <= n;i++)(distance[i] == 0x7f7f7f7f || distance[i] == 0) && i != s ? std::cout << "2147483647 " : std::cout << distance[i] << ' ';
    return 0;
}

同理dis(v)=min(dis(v),dis(u,v))

不过将可以被松弛的节点放到了q这个队列中，同时存图变为了链式前向星

容易被卡