图论基础与最短路算法课堂笔记

📚 图论基础概念

1. 图的定义

图由**顶点(Vertex)和边(Edge)**组成，是描述事物之间关系的数学模型。

2. 图的分类

• 有向图 vs 无向图：边是否具有方向
• 稀疏图 vs 稠密图：边的数量多少
  • 稀疏图：边数 $m \approx n$（$n$ 为顶点数）
  • 稠密图：边数 $m \approx n^2$

3. 存图的本质

存图的核心是存储边的信息，包括边的起点、终点和边权（带权图）。

---

🗄️ 图的存储方式

1. 邻接矩阵

本质：二维数组 a[i][j] 表示顶点 i 到顶点 j 的距离

代码实现

const int N = 1010;
int a[N][N]; // 邻接矩阵

// 初始化
memset(a, 0x3f, sizeof(a)); // 初始化为无穷大
for (int i = 1; i <= n; i++) {
    a[i][i] = 0; // 自己到自己的距离为0
}

// 添加边：a到b，边权为c
a[a][b] = c;
// 无向图需要双向添加
a[b][a] = c;

特点

✅ 优点：实现简单，查询两点间距离时间复杂度 $O(1)$
❌ 缺点：空间复杂度 $O(n^2)$，存储稀疏图时浪费大量空间
✅ 适用场景：稠密图（边数接近 $n^2$）

2. 邻接表

本质：每个顶点对应一个链表，只存储存在的边

代码实现

无权图

const int N = 2010;
vector<int> e[N]; // e[u]存储顶点u的所有出边的终点

// 添加边：a到b
e[a].push_back(b);
// 无向图需要双向添加
e[b].push_back(a);

// 遍历顶点u的所有出边
for (auto v : e[u]) {
    // 处理边u->v
}

带权图

const int N = 2010;

struct Edge {
    int to;  // 边的终点
    int w;   // 边的权值
};

vector<Edge> e[N];

// 添加边：a到b，边权为c
e[a].push_back({b, c});
// 无向图需要双向添加
e[b].push_back({a, c});

// 遍历顶点u的所有出边（C++17及以上）
for (auto [to, w] : e[u]) {
    // 处理边u->to，权值为w
}

// 兼容旧版本C++
for (auto ed : e[u]) {
    int to = ed.to;
    int w = ed.w;
    // 处理边u->to，权值为w
}

特点

✅ 优点：空间复杂度 $O(n+m)$，存储稀疏图时非常高效
❌ 缺点：查询两点间是否有边时间复杂度 $O(degree(u))$
✅ 适用场景：稀疏图（边数接近 $n$）

---

🚀 Floyd算法（全源最短路）

1. 算法简介

• 类型：动态规划算法，也称"插点法"
• 功能：计算图中任意两点之间的最短路径
• 适用场景：小规模图（$n \leq 500$），支持负权边，但不支持负权环

2. 核心思想

状态表示：d[k][i][j] 表示从 i 到 j，且中间只经过编号不超过 k 的顶点的最短路径长度

状态计算：

• 路径不经过k点：d[k][i][j] = d[k-1][i][j]
• 路径经过k点：d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]

空间优化：由于计算第k层只需要第k-1层的数据，可以省去第一维，得到二维数组 d[i][j]

3. 代码实现

const int N = 510;
const int INF = 0x3f3f3f3f;
int d[N][N]; // d[i][j]表示i到j的最短距离
int n, m;    // n个顶点，m条边

void floyd() {
    // k必须放在最外层！
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    // 初始化
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c); // 处理重边
    }
    
    floyd();
    
    // 输出任意两点间的最短距离
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] > INF / 2) {
                cout << "INF "; // 不可达
            } else {
                cout << d[i][j] << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}

4. 关键注意事项

1. 循环顺序：k 必须放在最外层！如果把 k 放在内层，会导致错误
2. 初始化：
   • d[i][i] = 0（自己到自己的距离为0）
   • 无边时 d[i][j] = INF（无穷大）
   • 有边时 d[i][j] = 边权
3. 重边处理：取最小的边权
4. 不可达判断：使用 d[i][j] > INF / 2 而不是 d[i][j] == INF，避免溢出问题

5. 时间复杂度

• 三重循环：$O(n^3)$
• 空间复杂度：$O(n^2)$

---

🏃 Dijkstra算法（单源最短路）

1. 算法简介

• 类型：贪心算法
• 功能：计算从一个源点到其他所有顶点的最短路径
• 适用场景：边权为非负数的图，支持有向图和无向图

2. 核心思想

1. 将所有顶点分为两个集合：已确定最短距离的集合和未确定最短距离的集合
2. 初始时，源点的最短距离为0，其他顶点为无穷大
3. 每次从未确定集合中选择距离最小的顶点，加入已确定集合
4. 用该顶点更新其所有邻接点的最短距离（松弛操作）
5. 重复步骤3-4，直到所有顶点都被加入已确定集合

3. 代码实现（朴素版）

const int N = 510;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, w;
};

vector<Edge> e[N];
int d[N];   // d[u]表示源点到u的最短距离
bool vis[N];// vis[u]标记u是否已确定最短距离
int n, m, s;// n个顶点，m条边，s为源点

void dijkstra(int s) {
    // 初始化
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[s] = 0;
    
    // 枚举n-1次（每次确定一个顶点的最短距离）
    for (int i = 1; i < n; i++) {
        // 找到未确定集合中距离最小的顶点u
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < d[u]) {
                u = j;
            }
        }
        
        vis[u] = true; // 标记u已确定
        
        // 用u更新其所有邻接点
        for (auto ed : e[u]) {
            int v = ed.to;
            int w = ed.w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c});
        // 无向图需要添加反向边
        // e[b].push_back({a, c});
    }
    
    dijkstra(s);
    
    // 输出源点到所有顶点的最短距离
    for (int i = 1; i <= n; i++) {
        if (d[i] > INF / 2) {
            cout << "INF "; // 不可达
        } else {
            cout << d[i] << " ";
        }
    }
    
    return 0;
}

4. 关键注意事项

1. 边权限制：不能处理负权边！如果图中有负权边，Dijkstra算法会得到错误结果
2. 初始化：
   • d[s] = 0（源点到自己的距离为0）
   • 其他顶点 d[i] = INF
   • vis 数组初始化为 false
3. 不可达判断：同样使用 d[i] > INF / 2

5. 时间复杂度

• 找最小距离顶点：$O(n^2)$
• 松弛操作：$O(m)$
• 总时间复杂度：$O(n^2 + m) = O(n^2)$
• 适用场景：$n \leq 10^3$ 的稠密图

---

📍 路径记录与输出

1. Floyd算法路径记录

const int N = 510;
int d[N][N];
int path[N][N]; // path[i][j]表示i到j的最短路径上i的下一个顶点

void floyd() {
    // 初始化path数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            path[i][j] = j; // 初始时i到j的下一个顶点是j
        }
    }
    
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = path[i][k]; // 更新路径
                }
            }
        }
    }
}

// 输出从a到b的最短路径
void print_path(int a, int b) {
    cout << a;
    while (a != b) {
        a = path[a][b];
        cout << " -> " << a;
    }
    cout << endl;
}

2. Dijkstra算法路径记录

const int N = 510;
vector<Edge> e[N];
int d[N];
bool vis[N];
int pre[N]; // pre[u]表示u在最短路径上的前驱顶点

void dijkstra(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    d[s] = 0;
    
    for (int i = 1; i < n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < d[u]) {
                u = j;
            }
        }
        
        vis[u] = true;
        
        for (auto ed : e[u]) {
            int v = ed.to;
            int w = ed.w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pre[v] = u; // 记录前驱
            }
        }
    }
}

// 递归输出从s到u的最短路径
void print_path(int u) {
    if (pre[u] == -1) {
        cout << u;
        return;
    }
    print_path(pre[u]);
    cout << " -> " << u;
}

---

📊 算法对比

算法	类型	功能	时间复杂度	空间复杂度	支持负权	适用场景
Floyd	动态规划	全源最短路	$O(n^3)$	$O(n^2)$	✅ 支持负权边 ❌ 不支持负权环	小规模图 ($n \leq 500$)
朴素Dijkstra	贪心	单源最短路	$O(n^2)$	$O(n+m)$	❌ 不支持负权边	稠密图 ($n \leq 10^3$)
堆优化Dijkstra			$O(m \log m)$			稀疏图 ($n \leq 10^6$)

---

💡 重要提示

1. 循环顺序：Floyd算法中 k 必须放在最外层，这是最容易出错的地方
2. 无穷大选择：使用 0x3f3f3f3f 作为无穷大，它的两倍不会超过int范围
3. 不可达判断：使用 d[i][j] > INF / 2 而不是 d[i][j] == INF
4. 重边处理：邻接矩阵取最小边权，邻接表可以保留所有边（算法会自动选择最短的）
5. 负权边：Dijkstra算法不能处理负权边，有负权边时使用Floyd或Bellman-Ford算法