图的最短路径算法

图表示

// 邻接表（推荐 — 稀疏图 O(V+E) 空间）
vector<vector<int>> adj;  // adj[u] = {v1, v2, ...}

// 带权图
vector<vector<pair<int, int>>> adj;  // adj[u] = {{v1, w1}, {v2, w2}}

// 邻接矩阵 — 稠密图
vector<vector<int>> matrix(V, vector<int>(V, INF));

BFS — 无权图最短路径

// 从 src 到所有节点的最短距离
vector<int> bfsShortestPath(int V, const vector<vector<int>> &adj, int src) {
    vector<int> dist(V, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}
// 时间 O(V+E)，空间 O(V)
// ⚠️ 仅适用于无权图（每条边权重为 1）

Dijkstra — 非负权图

// 优先队列优化版
vector<int> dijkstra(int V, const vector<vector<pair<int,int>>> &adj, int src) {
    vector<int> dist(V, INT_MAX);
    using P = pair<int, int>;  // {距离, 节点}
    priority_queue<P, vector<P>, greater<P>> pq;

    dist[src] = 0;
    pq.push({0, src});

    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});
            }
        }
    }
    return dist;
}
// 时间 O((V+E) log V)，空间 O(V)

为什么不能处理负权边

A ──(2)──→ B ──(-3)──→ C
│                        │
└──────────(1)───────────┘

Dijkstra: A→C = 1（直达） → 标记 C 完成
实际最短: A→B→C = -1（但 C 已被"锁定"）
Dijkstra 的贪心假设被负权打破。

Bellman-Ford — 可处理负权

// 检测负环：第 V 轮还能松弛 → 存在负环
vector<int> bellmanFord(int V, const vector<tuple<int,int,int>> &edges, int src) {
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;
    for (int i = 0; i < V - 1; ++i) {          // 松弛 V-1 轮
        bool changed = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break;  // 早停优化
    }
    // 第 V 轮检测负环
    for (auto [u, v, w] : edges)
        if (dist[u] != INT_MAX && dist[u] + w < dist[v])
            return {};  // 存在负环
    return dist;
}
// 时间 O(VE)，空间 O(V)

Floyd-Warshall — 全源最短

void floydWarshall(vector<vector<int>> &dist) {
    int V = dist.size();
    for (int k = 0; k < V; ++k)
        for (int i = 0; i < V; ++i)
            for (int j = 0; j < V; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
// 时间 O(V³)，空间 O(V²) — 适用于 V ≤ 500
// 可处理负权，但不可有负环

A* — 启发式搜索

// 从 start 到 goal，使用启发函数 h(n) 预估剩余距离
int aStar(const vector<vector<pair<int,int>>> &adj, int start, int goal,
          function<int(int)> heuristic) {
    using P = pair<int, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<int> gScore(V, INF);
    gScore[start] = 0;
    pq.push({heuristic(start), start});

    while (!pq.empty()) {
        auto [f, u] = pq.top(); pq.pop();
        if (u == goal) return gScore[u];
        for (auto [v, w] : adj[u]) {
            int tentG = gScore[u] + w;
            if (tentG < gScore[v]) {
                gScore[v] = tentG;
                pq.push({tentG + heuristic(v), v});  // f = g + h
            }
        }
    }
    return -1;
}
// Dijkstra 是 A* 的特例（h(n) = 0）
// h(n) ≤ 真实剩余距离 → 保证最优

选型速查

算法	时间	适用场景
BFS	O(V+E)	无权图 / 等权
Dijkstra	O((V+E) log V)	非负权单源
Bellman-Ford	O(VE)	负权 + 负环检测
Floyd-Warshall	O(V³)	全源、小图、传递闭包
A*	启发式	有距离预估的场景