C++图论专题：最短路径四大算法对比

const int INF = 0x3f3f3f3f;
int g[V][V];   // 邻接矩阵，不直接相连的设为 INF
int dist[V];
bool vis[V];

void dijkstra(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[s] = 0;
    for (int i = 0; i < V; ++i) {
        int u = -1, minD = INF;
        for (int j = 0; j < V; ++j)
            if (!vis[j] && dist[j] < minD) {
                minD = dist[j];
                u = j;
            }
        if (u == -1) break;
        vis[u] = true;
        for (int v = 0; v < V; ++v)
            if (!vis[v] && g[u][v] != INF && dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
}

using PII = pair<int, int>; // (距离, 节点)
vector<vector<PII>> adj;    // 邻接表
priority_queue<PII, vector<PII>, greater<PII>> pq;

void dijkstra(int s) {
    vector<int> dist(V, INF);
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;   // 跳过旧版本
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

struct Edge { int u, v, w; };
vector<Edge> edges;
int dist[V];

bool bellmanFord(int s) {
    fill(dist, dist + V, INF);
    dist[s] = 0;
    // 进行 V-1 轮松弛
    for (int i = 1; i <= V - 1; ++i) {
        bool updated = false;
        for (auto &e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break;  // 提前结束
    }
    // 第 V 轮检查负环：如果能继续松弛，则存在负环
    for (auto &e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
            return false;   // 存在负环
    }
    return true;            // 无负环，dist 存储最短距离
}

vector<vector<PII>> adj;
int dist[V], cnt[V];      // cnt 记录入队次数，用于检测负环
bool inq[V];              // 是否已在队列中

bool spfa(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(inq, 0, sizeof inq);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    cnt[v]++;
                    if (cnt[v] >= V)   // 一个节点入队超过 V 次，说明有负环
                        return false;
                }
            }
        }
    }
    return true;
}

int d[V][V];   // 初始为邻接矩阵，d[i][i]=0，不直接相连为 INF

void floyd() {
    for (int k = 0; k < V; ++k)
        for (int i = 0; i < V; ++i)
            for (int j = 0; j < V; ++j)
                if (d[i][k] != INF && d[k][j] != INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
}