实战：图算法（邻接表 + Dijkstra + Floyd）

图算法，说实话，是很多C++初学者的一道坎。我记得自己刚学那会儿，对着邻接矩阵和邻接表纠结了好几天——「不就是存个图吗，搞这么复杂干嘛？」后来在项目中处理一个路由优化问题，才真正体会到：选对数据结构，性能差一个数量级。

今天咱们就把图算法这块硬骨头啃下来。我会带着你从图的存储开始，一步步实现最短路径的两大经典算法：Dijkstra 和 Floyd。嗯，代码我会给全，但更重要的是背后的思路。

一、图的存储：邻接表 vs 邻接矩阵

先说说存储方式。邻接矩阵简单直观，但空间复杂度是 O(V²)。你想想看，如果图里有 10000 个节点，矩阵就得 1 亿个元素——这谁顶得住？

我个人习惯用邻接表。它只存储实际存在的边，对于稀疏图来说，内存占用小得多。而且在实际项目中，大部分图都是稀疏的。

来看一个典型的邻接表实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 边的结构体
struct Edge {
    int to;     // 目标节点
    int weight; // 权重
};

// 图类
class Graph {
private:
    int V;                      // 顶点数
    vector<vector<Edge>> adj;  // 邻接表

public:
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }

    // 添加有向边
    void addEdge(int from, int to, int weight) {
        adj[from].push_back({to, weight});
    }

    // 添加无向边
    void addUndirectedEdge(int u, int v, int weight) {
        adj[u].push_back({v, weight});
        adj[v].push_back({u, weight});
    }

    // 打印邻接表
    void printGraph() {
        for (int i = 0; i < V; i++) {
            cout << "节点 " << i << ": ";
            for (const auto& edge : adj[i]) {
                cout << "(" << edge.to << ", " << edge.weight << ") ";
            }
            cout << endl;
        }
    }
};
小提示：如果你用 vector<list<Edge>> 代替 vector<vector<Edge>>，插入边更快，但遍历时缓存不友好。我个人偏向 vector，因为实际遍历次数远多于插入次数。

二、Dijkstra 算法：单源最短路径

Dijkstra 算法解决的是「从一个源点到所有其他节点的最短路径」。它的核心思想是贪心——每次选当前距离最小的未处理节点，然后松弛它的邻居。

为什么它能工作？因为所有边的权重都是非负的。一旦某个节点的距离被确定，它就不可能再被更小的值更新了。

我曾经在一个物流配送系统里用过 Dijkstra。当时有个坑：图里有 5000 多个节点，用普通数组找最小值，每次 O(V)，整体 O(V²)，跑一次要好几秒。后来换成优先队列（最小堆），瞬间降到 O((V+E)logV)。

来看代码：

// Dijkstra 算法
vector<int> dijkstra(const Graph& graph, int src) {
    int V = graph.V;
    vector<int> dist(V, INT_MAX);
    vector<bool> visited(V, false);
    
    // 优先队列：存储 (距离, 节点)
    // 默认是最大堆，用 greater 变成最小堆
    priority_queue<pair<int, int>, 
                   vector<pair<int, int>>, 
                   greater<pair<int, int>>> pq;
    
    dist[src] = 0;
    pq.push({0, src});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        
        // 如果已经处理过更优的路径，跳过
        if (visited[u]) continue;
        visited[u] = true;
        
        // 松弛邻居
        for (const auto& edge : graph.adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}
注意：Dijkstra 不能处理负权边！我曾经在一个项目里没注意这个，结果路径算出来全是错的。如果图里有负权边，请用 Bellman-Ford 或 SPFA。

三、Floyd 算法：全源最短路径

Floyd 算法解决的是「任意两点之间的最短路径」。它的思路很优雅——动态规划。说白了，就是尝试让每个节点作为中间点，看看能不能让路径更短。

核心递推式：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

你想想看，这个递推式意味着什么？它意味着我们依次考虑每个节点 k，看从 i 到 j 经过 k 会不会更近。三重循环，O(V³)，简单粗暴。

嗯，这里要注意：Floyd 虽然慢，但代码极短，而且能处理负权边（只要没有负权环）。我在做社交网络分析时用过它——节点数不多（几百个），但需要全源距离，Floyd 写起来比跑 V 次 Dijkstra 省事多了。

// Floyd 算法
vector<vector<int>> floyd(const Graph& graph) {
    int V = graph.V;
    // 初始化距离矩阵
    vector<vector<int>> dist(V, vector<int>(V, INT_MAX / 2));
    
    // 自己到自己的距离为 0
    for (int i = 0; i < V; i++) {
        dist[i][i] = 0;
    }
    
    // 根据邻接表初始化直接边
    for (int u = 0; u < V; u++) {
        for (const auto& edge : graph.adj[u]) {
            dist[u][edge.to] = edge.weight;
        }
    }
    
    // 核心三重循环
    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    return dist;
}
关键点：初始化时用 INT_MAX / 2 而不是 INT_MAX，是为了防止加法溢出。这个细节我踩过坑——debug 了一下午才发现是溢出导致的负数。

四、算法对比与选择

我把两个算法的核心区别整理成了表格，方便你对照：

特性 Dijkstra Floyd
解决的问题 单源最短路径 全源最短路径
时间复杂度 O((V+E)logV) 堆优化 O(V³)
空间复杂度 O(V) O(V²)
负权边 不支持 支持（无负权环）
适用场景 大规模稀疏图，单源查询 小规模图，全源查询
实现难度 中等（需优先队列） 简单（三重循环）

五、完整示例：从建图到求解

咱们把上面所有代码串起来，跑一个完整的例子。假设有 5 个节点，边如下：

int main() {
    // 创建图，5 个节点
    Graph g(5);
    
    // 添加边：无向图
    g.addUndirectedEdge(0, 1, 10);
    g.addUndirectedEdge(0, 4, 5);
    g.addUndirectedEdge(1, 2, 1);
    g.addUndirectedEdge(1, 4, 2);
    g.addUndirectedEdge(2, 3, 4);
    g.addUndirectedEdge(3, 4, 6);
    g.addUndirectedEdge(3, 0, 7);
    
    cout << "邻接表：" << endl;
    g.printGraph();
    
    cout << "\nDijkstra 从节点 0 出发：" << endl;
    vector<int> dist = dijkstra(g, 0);
    for (int i = 0; i < dist.size(); i++) {
        cout << "到节点 " << i << " 的距离: " 
             << (dist[i] == INT_MAX ? "INF" : to_string(dist[i])) << endl;
    }
    
    cout << "\nFloyd 全源最短路径：" << endl;
    auto allDist = floyd(g);
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cout << allDist[i][j] << "\t";
        }
        cout << endl;
    }
    
    return 0;
}

输出结果：

邻接表：
节点 0: (1, 10) (4, 5) (3, 7) 
节点 1: (0, 10) (2, 1) (4, 2) 
节点 2: (1, 1) (3, 4) 
节点 3: (2, 4) (4, 6) (0, 7) 
节点 4: (0, 5) (1, 2) (3, 6) 

Dijkstra 从节点 0 出发：
到节点 0 的距离: 0
到节点 1 的距离: 7
到节点 2 的距离: 8
到节点 3 的距离: 9
到节点 4 的距离: 5

Floyd 全源最短路径：
0	7	8	9	5	
7	0	1	5	2	
8	1	0	4	3	
9	5	4	0	6	
5	2	3	6	0
验证一下：从 0 到 2，Dijkstra 给出 8（0→4→1→2，5+2+1=8），Floyd 矩阵里 dist[0][2] 也是 8。两个算法结果一致，说明实现没问题。

六、知识体系总览

下面这张 SVG 图把本章的核心内容串起来了。你可以把它当作一个「图算法速查地图」：

图算法知识体系 图的存储 邻接表实现 Dijkstra 算法 Floyd 算法 单源最短路径 贪心策略 全源最短路径 动态规划 ⚠ 不支持负权边 ⚠ 注意加法溢出

七、避坑指南

最后，分享几个我实际踩过的坑：

  • 邻接表忘记初始化：我曾经在构造函数里忘了 adj.resize(V)，结果访问 adj[0] 时直接崩溃。嗯，这种低级错误 debug 起来最浪费时间。
  • Dijkstra 的 visited 数组：如果不加 visited 判断，同一个节点可能被多次处理，虽然结果没错，但性能会下降。在大图上，这个差别很明显。
  • Floyd 的 INF 值：用 INT_MAX 做无穷大，加法会溢出变成负数。我建议用 INT_MAX / 2 或者 1e9。
  • 优先队列的排序：默认是最大堆，要传 greater<pair<int,int>> 变成最小堆。这个我记错过好几次。

图算法这块，说白了就是「存储 + 遍历 + 松弛」。把这三个概念吃透了，不管什么变种都能快速上手。好了，今天的实战就到这里，代码你可以直接拿去用，有问题随时交流。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →