核心概念区分

在开始之前，我们先明确两个概念的区别：

• 最短路 (Shortest Path)：关注的是一个点（源点）到另一个点（或所有其他点）的路径总权重最小。它是一条“路径”。
• 最小生成树 (Minimum Spanning Tree, MST)：关注的是如何用最少的总权重连接图中的所有点，形成一棵树。它是一个覆盖所有顶点的“子图”。

---

Part 1: 最短路算法 (Shortest Path Algorithms)

最短路问题主要分为两种：

1. 单源最短路 (Single-Source Shortest Path)：计算从一个指定的源点 s 到图中所有其他顶点的最短路径。
2. 所有顶点对最短路 (All-Pairs Shortest Path)：计算图中每一对顶点 (u, v) 之间的最短路径。

1. Dijkstra 算法

Dijkstra 算法是解决单源最短路问题的经典算法，但它有一个重要的前提：图中不能有负权边。

• 核心思想：
  Dijkstra 算法采用迭代的方式，维护一个已找到最短路径的顶点集合 S。

  1. 初始时，S 中只有源点 s。
  2. 每次迭代，从尚未确定最短路径的顶点（V-S 集合）中，选择一个距离源点 s 最近的顶点 u。
  3. 将 u 加入 S 集合。
  4. 然后，通过顶点 u 来更新 u 的所有邻居 v 的距离。这个过程称为“松弛”（Relaxation）：如果从 s 经过 u 到达 v 的路径比当前已知的 s 到 v 的路径更短，则更新 s 到 v 的距离。
  5. 重复这个过程，直到所有顶点都加入 S。

• 贪心策略分析：
  是，Dijkstra 是一个典型的贪心算法。
  它的贪心策略在于：每一步都选择当前看来距离源点最近的未访问顶点。它相信这个局部最优选择（当前最近）就是全局最优选择（这个点的最终最短路径已经确定）。这个贪心策略的正确性依赖于“边的权重非负”这一前提。因为没有负权边，一旦一个点被选为“最近”，就不可能再通过其他未访问的点绕一下，从而找到一条更短的路径了。

• C++ 代码实现 (使用优先队列优化)
  这是最常见的实现方式，也叫堆优化版的 Dijkstra。时间复杂度为 $O(E\log V)$。

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const int INF = std::numeric_limits<int>::max();

// 图的边结构
struct Edge {
    int to;
    int weight;
};

// 优先队列中存储的节点状态
struct State {
    int u;
    int dist;

    // 自定义比较函数，使其成为最小堆
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

void dijkstra(int start, int n, const std::vector<std::vector<Edge>>& adj) {
    std::vector<int> dist(n + 1, INF);
    std::vector<bool> visited(n + 1, false);
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

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

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        int u = current.u;

        // 如果已经处理过，则跳过
        if (visited[u]) {
            continue;
        }
        visited[u] = true;

        // 松弛操作
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({v, dist[v]});
            }
        }
    }

    // 打印结果
    std::cout << "Dijkstra: Shortest distances from source " << start << ":\n";
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            std::cout << "Node " << i << ": Infinity\n";
        } else {
            std::cout << "Node " << i << ": " << dist[i] << "\n";
        }
    }
}

int main() {
    int n = 5, m = 7, start = 1;
    std::vector<std::vector<Edge>> adj(n + 1);
    // 添加边: from, to, weight
    adj[1].push_back({2, 10});
    adj[1].push_back({4, 5});
    adj[2].push_back({3, 1});
    adj[2].push_back({4, 2});
    adj[3].push_back({5, 4});
    adj[4].push_back({3, 9});
    adj[4].push_back({5, 2});

    dijkstra(start, n, adj);
    return 0;
}

2. Bellman-Ford 算法

Bellman-Ford 算法也是解决单源最短路问题，但它的优势在于可以处理带负权边的图，并且能够检测出负权环。

• 核心思想：
  算法基于动态规划的思想。它对图中的所有边进行 V-1 轮松弛操作。

  1. 初始化源点 s 的距离为 0，其他所有点为无穷大。
  2. 进行 V-1 轮迭代。在每一轮中，遍历图中的所有边 (u, v)，并进行松弛操作：如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v]。
  3. V-1 轮后，如果图中不存在负权环，那么所有顶点的最短路径就已经计算出来了。
  4. 为了检测负权环，再进行第 V 轮松弛。如果在这一轮中，仍然有边的距离可以被更新，说明图中存在一个从源点可达的负权环。

• 贪心策略分析：
  否，Bellman-Ford 不是贪心算法。
  它没有在每一步做出局部最优的选择。相反，它是一种非常“暴力”或者说“系统性”的方法。它通过 V-1 次迭代，系统地计算出所有最多经过1条边、2条边、…、直到 V-1 条边的最短路径。它的思想更接近于动态规划，dp[k][v] 表示从源点出发最多经过 k 条边到达 v 的最短路径。

• C++ 代码实现
  时间复杂度为 $O(V\cdot E)$。

#include <iostream>
#include <vector>
#include <limits>

const int INF = std::numeric_limits<int>::max();

struct Edge {
    int from;
    int to;
    int weight;
};

void bellman_ford(int start, int n, int m, const std::vector<Edge>& edges) {
    std::vector<int> dist(n + 1, INF);
    dist[start] = 0;

    // V-1 轮松弛
    for (int i = 0; i < n - 1; ++i) {
        for (const auto& edge : edges) {
            if (dist[edge.from] != INF && dist[edge.from] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[edge.from] + edge.weight;
            }
        }
    }

    // 检测负权环
    bool has_negative_cycle = false;
    for (const auto& edge : edges) {
        if (dist[edge.from] != INF && dist[edge.from] + edge.weight < dist[edge.to]) {
            has_negative_cycle = true;
            break;
        }
    }

    if (has_negative_cycle) {
        std::cout << "Bellman-Ford: Graph contains a negative-weight cycle.\n";
    } else {
        std::cout << "Bellman-Ford: Shortest distances from source " << start << ":\n";
        for (int i = 1; i <= n; ++i) {
            if (dist[i] == INF) {
                std::cout << "Node " << i << ": Infinity\n";
            } else {
                std::cout << "Node " << i << ": " << dist[i] << "\n";
            }
        }
    }
}

int main() {
    int n = 5, m = 8, start = 1;
    std::vector<Edge> edges = {
        {1, 2, 6}, {1, 3, 7}, {2, 4, 5}, {2, 5, -4},
        {3, 2, 8}, {3, 4, -3}, {4, 5, 9}, {5, 2, 2}
    };
    
    // 示例负权环
    // std::vector<Edge> edges_with_cycle = {
    //     {1, 2, 1}, {2, 3, 1}, {3, 1, -3}
    // };

    bellman_ford(start, n, m, edges);
    return 0;
}

3. SPFA 算法 (Shortest Path Faster Algorithm)

SPFA 是 Bellman-Ford 算法的队列优化版本，在很多情况下（特别是稀疏图）比 Bellman-Ford 更快。它同样可以处理负权边和检测负权环。

• 核心思想：
  Bellman-Ford 每一轮都盲目地松弛所有边。SPFA 观察到，只有当一个点 u 的 dist 值变小时，才可能引起其邻居 v 的 dist 值变小。因此，SPFA 使用一个队列来维护那些 dist 值刚刚被更新过的顶点。

  1. 将源点 s 入队。
  2. 当队列不为空时，出队一个顶点 u。
  3. 对 u 的所有邻居 v 进行松弛操作。
  4. 如果 v 的 dist 值被更新了，并且 v 不在队列中，则将 v 入队。
  5. 为了检测负权环，可以记录每个顶点入队的次数。如果一个顶点入队次数超过 V 次，则说明存在负权环。

• 贪心策略分析：
  否，SPFA 也不是贪心算法。
  它处理顶点的顺序是由队列的先进先出（FIFO）特性决定的，而不是基于任何局部最优的属性（如距离大小）。它是一种动态的、基于传播的松弛方法。

• C++ 代码实现
  平均时间复杂度为 $O(kE)$，其中 k 是一个小的常数。但在最坏情况下（例如在特殊构造的网格图中），会退化到 $O(V\cdot E)$。

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const int INF = std::numeric_limits<int>::max();

struct Edge {
    int to;
    int weight;
};

bool spfa(int start, int n, const std::vector<std::vector<Edge>>& adj) {
    std::vector<int> dist(n + 1, INF);
    std::vector<bool> in_queue(n + 1, false);
    std::vector<int> count(n + 1, 0); // 记录入队次数
    std::queue<int> q;

    dist[start] = 0;
    q.push(start);
    in_queue[start] = true;
    count[start]++;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                    count[v]++;
                    if (count[v] > n) {
                        std::cout << "SPFA: Graph contains a negative-weight cycle.\n";
                        return false; // 发现负权环
                    }
                }
            }
        }
    }

    std::cout << "SPFA: Shortest distances from source " << start << ":\n";
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            std::cout << "Node " << i << ": Infinity\n";
        } else {
            std::cout << "Node " << i << ": " << dist[i] << "\n";
        }
    }
    return true;
}

int main() {
    int n = 5, start = 1;
    std::vector<std::vector<Edge>> adj(n + 1);
    adj[1].push_back({2, 6});
    adj[1].push_back({3, 7});
    adj[2].push_back({4, 5});
    adj[2].push_back({5, -4});
    adj[3].push_back({2, 8});
    adj[3].push_back({4, -3});
    adj[4].push_back({5, 9});
    adj[5].push_back({2, 2});

    spfa(start, n, adj);
    return 0;
}

4. Floyd-Warshall 算法

Floyd-Warshall 算法用于解决所有顶点对最短路问题。它可以处理带负权边的图，但不能处理负权环（如果存在负权环，算法可以检测出来）。

• 核心思想：
  这是一个非常经典的动态规划算法。它使用一个二维数组 dp[i][j] 来存储从顶点 i 到 j 的最短路径长度。算法的核心思想是：对于每一对顶点 (i, j)，我们尝试通过一个中间点 k 来缩短它们的路径。

  1. 初始化 dp[i][j] 为 i 到 j 的直接边权（如果无直连边则为无穷大），dp[i][i] 为 0。
  2. 进行 V 轮迭代，k 从 1 到 V。
  3. 在第 k 轮迭代中，对于所有的顶点对 (i, j)，检查 dp[i][k] + dp[k][j] 是否小于 dp[i][j]。如果是，则更新 dp[i][j]。
     $$dp[i][j]=\min (dp[i][j],dp[i][k]+dp[k][j])$$
  4. 所有迭代结束后，dp[i][j] 就存储了 i 到 j 的最短路径。如果 dp[i][i] < 0，则说明存在从 i 出发的负权环。

• 贪心策略分析：
  否，Floyd-Warshall 是动态规划算法，不是贪心算法。
  它没有做出任何局部最优选择。相反，它通过引入中间点 k，系统地、由简到繁地构建出最终解。dp[k][i][j] 的含义是“只允许经过前 k 个点作为中间点时，从 i 到 j 的最短路径”，这是典型的动态规划状态转移。

• C++ 代码实现
  时间复杂度为 $O(V^3)$。

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9; // 使用一个较大的数表示无穷大

void floyd_warshall(int n, std::vector<std::vector<int>>& dist) {
    // 核心 DP 过程
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 打印结果
    std::cout << "Floyd-Warshall: All-Pairs Shortest Paths:\n";
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dist[i][j] == INF) {
                std::cout << "INF\t";
            } else {
                std::cout << dist[i][j] << "\t";
            }
        }
        std::cout << "\n";
    }
}

int main() {
    int n = 4;
    std::vector<std::vector<int>> dist(n + 1, std::vector<int>(n + 1, INF));

    // 初始化邻接矩阵
    for (int i = 1; i <= n; ++i) dist[i][i] = 0;
    dist[1][2] = 3;
    dist[1][4] = 5;
    dist[2][1] = 2;
    dist[2][4] = 4;
    dist[3][2] = -2;
    dist[4][3] = 1;

    floyd_warshall(n, dist);
    return 0;
}

---

Part 2: 最小生成树算法 (Minimum Spanning Tree Algorithms)

最小生成树（MST）的目标是在一个加权的无向连通图中，找出一个边的子集，这个子集连接了图中所有的顶点，且没有环，同时总权重最小。

1. Prim 算法

• 核心思想：
  Prim 算法和 Dijkstra 算法非常相似。它也是从一个顶点开始，逐步扩大一棵树。

  1. 选择任意一个顶点作为起始点，将其加入到生成树集合 T 中。
  2. 维护一个 dist 数组，dist[i] 表示顶点 i 到集合 T 的最短边的权重。
  3. 重复以下步骤 V-1 次：
     a. 从所有不在 T 中的顶点里，找到 dist 值最小的顶点 u。
     b. 将 u 和连接它与 T 的那条最短边加入到生成树中。
     c. 更新 u 的所有邻居 v 的 dist 值：如果 u 到 v 的边权小于当前的 dist[v]，则更新 dist[v]。

• 贪心策略分析：
  是，Prim 是一个典型的贪心算法。
  它的贪心策略是：每一步都选择一条权重最小的边，这条边连接一个已在树中的顶点和一个未在树中的顶点。它总是选择“扩张”这棵树的“最便宜”的方式。这个贪心选择的正确性由图论中的“切割定理”（Cut Property）保证：对于图的任意一个切分（将顶点分为两部分），连接这两个部分的权重最小的边，必然属于图的某个最小生成树。Prim 算法的每一步选择都符合这个定理。

• C++ 代码实现 (类似 Dijkstra 的优先队列优化)
  时间复杂度为 $O(E\log V)$。

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const int INF = std::numeric_limits<int>::max();

// 边结构
struct Edge {
    int to;
    int weight;
};

// 优先队列中存储的状态
struct State {
    int u;
    int key; // 类似 dist，表示到树的最小边权

    bool operator>(const State& other) const {
        return key > other.key;
    }
};

void prim(int n, const std::vector<std::vector<Edge>>& adj) {
    std::vector<int> key(n + 1, INF);
    std::vector<int> parent(n + 1, -1);
    std::vector<bool> in_mst(n + 1, false);
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    int start_node = 1;
    key[start_node] = 0;
    pq.push({start_node, 0});

    long long total_weight = 0;

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
        int u = current.u;

        if (in_mst[u]) {
            continue;
        }
        in_mst[u] = true;
        total_weight += current.key;

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (!in_mst[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                pq.push({v, key[v]});
            }
        }
    }

    std::cout << "Prim's Algorithm: Minimum Spanning Tree Weight = " << total_weight << "\n";
    std::cout << "Edges in MST:\n";
    for (int i = 2; i <= n; ++i) {
        std::cout << parent[i] << " - " << i << "\n";
    }
}

int main() {
    int n = 5;
    std::vector<std::vector<Edge>> adj(n + 1);
    // 无向图，加两次边
    auto add_edge = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };
    
    add_edge(1, 2, 2);
    add_edge(1, 3, 6);
    add_edge(2, 3, 1);
    add_edge(2, 4, 5);
    add_edge(3, 4, 8);
    add_edge(3, 5, 7);
    add_edge(4, 5, 9);
    
    prim(n, adj);
    return 0;
}

2. Kruskal 算法

• 核心思想：
  Kruskal 算法的思路与 Prim 完全不同，它关注的是全局的边，而不是局部的点。

  1. 将图中所有的边按权重从小到大排序。
  2. 创建一个森林，其中每个顶点自成一棵树。
  3. 遍历排序后的边。对于每一条边 (u, v)，如果 u 和 v 不在同一棵树中（即加入这条边不会形成环），则将这条边加入到最小生成树中，并合并 u 和 v 所在的树。
  4. 重复此过程，直到加入了 V-1 条边。
     判断两个顶点是否在同一棵树中，通常使用**并查集（Disjoint Set Union, DSU）**数据结构来高效实现。

• 贪心策略分析：
  是，Kruskal 也是一个经典的贪心算法。
  它的贪心策略是：在所有可选的边中，永远选择权重最小的，并且保证这个选择不会破坏树的结构（即不形成环）。它总是从全局视角做出最“便宜”的选择。这个贪心策略的正确性同样可以由“切割定理”证明。每当算法选择一条边时，这条边必然是连接某个切分两部分的最小权重边。

• C++ 代码实现 (使用并查集)
  时间复杂度为 $O(E\log E)$（主要是排序的开销）。

#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
    int from, to, weight;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

// 并查集 (Disjoint Set Union)
struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; ++i) parent[i] = i;
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // 路径压缩
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

void kruskal(int n, std::vector<Edge>& edges) {
    // 1. 排序所有边
    std::sort(edges.begin(), edges.end(), compareEdges);

    DSU dsu(n);
    long long total_weight = 0;
    std::vector<Edge> mst_edges;
    
    // 2. 遍历边并构建MST
    for (const auto& edge : edges) {
        if (dsu.find(edge.from) != dsu.find(edge.to)) {
            dsu.unite(edge.from, edge.to);
            total_weight += edge.weight;
            mst_edges.push_back(edge);
        }
    }

    std::cout << "Kruskal's Algorithm: Minimum Spanning Tree Weight = " << total_weight << "\n";
    std::cout << "Edges in MST:\n";
    for (const auto& edge : mst_edges) {
        std::cout << edge.from << " - " << edge.to << " (weight " << edge.weight << ")\n";
    }
}

int main() {
    int n = 5, m = 7;
    std::vector<Edge> edges = {
        {1, 2, 2}, {1, 3, 6}, {2, 3, 1}, {2, 4, 5},
        {3, 4, 8}, {3, 5, 7}, {4, 5, 9}
    };

    kruskal(n, edges);
    return 0;
}

---

总结

算法	解决问题	核心思想	时间复杂度	负权边	是否贪心
Dijkstra	单源最短路	选最近的点进行扩展	$O(E\log V)$	不支持	是
Bellman-Ford	单源最短路	对所有边进行V-1轮松弛	$O(V\cdot E)$	支持，可检负权环	否 (DP)
SPFA	单源最短路	Bellman-Ford的队列优化	平均$O(kE)$,最坏$O(V\cdot E)$	支持，可检负权环	否
Floyd-Warshall	所有顶点对最短路	动态规划，枚举中转点	$O(V^3)$	支持，不可有负权环	否 (DP)
Prim	最小生成树	从一个点开始，逐步加点入树	$O(E\log V)$	支持 (无意义)	是
Kruskal	最小生成树	按边权排序，逐步加边成树	$O(E\log E)$	支持 (无意义)	是

注：对于最小生成树算法，负权边是“支持”的，因为其目标是总权重最小，负权边只会让这个总权重更小，不影响算法正确性。但在实际问题中，MST的边权通常表示成本、距离等非负概念。