适用条件：边权非负

解法1：Dijkstra算法（优先队列优化，难度★★☆）

解法2：Floyd-Warshall算法（多源最短路径，难度★★★）

五、题型解释

最短路径问题是图论中的核心问题，目标是找到图中两点间权重和最小的路径。

cpp

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;typedef pair<int, int> pii; // {距离, 节点}void dijkstra(vector<vector<pii>> &graph, int src) {    int V = graph.size();    vector<int> dist(V, INT_MAX);    priority_queue<pii, vector<pii>, greater<pii>> pq;    dist[src] = 0;    pq.push({0, src});    while (!pq.empty()) {        int u = pq.top().second;        int d = pq.top().first;        pq.pop();        if (d > dist[u]) continue; // 跳过旧数据        for (auto &edge : graph[u]) {            int v = edge.first;            int w = edge.second;            if (dist[u] + w < dist[v]) {                dist[v] = dist[u] + w;                pq.push({dist[v], v});            }        }    }    cout << "顶点\t距离" << endl;    for (int i = 0; i < V; i++)        cout << i << "\t" << dist[i] << endl;}int main() {    int V = 5;    vector<vector<pii>> graph(V);    graph[0].push_back({1, 4});    graph[0].push_back({2, 1});    graph[1].push_back({3, 2});    graph[2].push_back({1, 1});    graph[2].push_back({3, 5});    graph[3].push_back({4, 3});    dijkstra(graph, 0);    return 0;}

代码逻辑：

1. 优先队列：存储{距离, 节点}，自动按距离排序。

2. 动态规划思想

• Floyd-Warshall核心：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。C语言实现

  解法1：Dijkstra算法（正权图，难度★★）

  通俗解释：

  • 贪心策略：每次选择当前距离起点最近的节点，逐步扩展最短路径集合。

五、

时间复杂度：O(V³)，适合小规模图。

STL使用：vector存邻接表，priority_queue实现最小堆。

c

#include <stdio.h>#include <limits.h>#define V 6  // 顶点数int minDistance(int dist[], int visited[]) {    int min = INT_MAX, min_index;    for (int v = 0; v < V; v++)        if (!visited[v] && dist[v] <= min)            min = dist[v], min_index = v;    return min_index;}void dijkstra(int graph[V][V], int src) {    int dist[V];      // 存储最短距离    int visited[V];   // 记录节点是否已处理    for (int i = 0; i < V; i++)        dist[i] = INT_MAX, visited[i] = 0;    dist[src] = 0;  // 起点到自身距离为0    for (int count = 0; count < V - 1; count++) {        int u = minDistance(dist, visited); // 选取未处理的最小距离节点        visited[u] = 1;        // 更新相邻节点的距离        for (int v = 0; v < V; v++)            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX &&                dist[u] + graph[u][v] < dist[v])                dist[v] = dist[u] + graph[u][v];    }    // 输出结果    printf("顶点\t距离\n");    for (int i = 0; i < V; i++)        printf("%d\t%d\n", i, dist[i]);}int main() {    int graph[V][V] = {        {0, 4, 0, 0, 0, 0},        {4, 0, 8, 0, 0, 0},        {0, 8, 0, 7, 0, 4},        {0, 0, 7, 0, 9, 14},        {0, 0, 0, 9, 0, 10},        {0, 0, 4, 14, 10, 0}    };    dijkstra(graph, 0);    return 0;}

代码逻辑：

1. 初始化：距离数组dist设为无穷大，起点距离为0。常见题型：

   1. 单源最短路径：求某一点到其他所有点的最短路径（如Dijkstra、总结对比表

      六、

   2. 三重循环：依次考虑每个中间节点k，更新所有i→j路径。

      最短路径问题

      ->返回c/c++蓝桥杯经典编程题100道-目录

      ---

      目录

      最短路径问题

      一、

   ---

   四、

2. 负权环检测：若第V轮仍有更新，说明存在负权环。

---

解法2：Bellman-Ford算法（含负权边，难度★★★）

通俗解释：

• 松弛操作：通过多次迭代所有边，逐步逼近最短路径。C++实现

  解法1：Dijkstra算法（优先队列优化，难度★★☆）

  通俗解释：

  • 使用优先队列快速获取最小距离节点，时间复杂度优化至O((V+E)logV)。

  • 边权为1的图（BFS优化）。例题问题描述

    三、

  ---

  三、

• 懒惰删除：当队列中的距离大于记录的距离时跳过。

• 适用条件：边权非负。

例题3（多源最短路径）：

• 输入：任意两点间的最短距离矩阵。Bellman-Ford算法）。题型解释

  二、

---

解法2：Floyd-Warshall算法（多源最短路径，难度★★★）

通俗解释：

• 动态规划：通过中间节点逐步优化所有点对的最短路径。

• 时间复杂度：O(V²)，适合稠密图。

• 松弛操作：进行V-1轮边遍历更新距离。总结对比表

  算法	时间复杂度	空间复杂度	适用场景
  Dijkstra	O((V+E)logV)	O(V)	正权图单源最短路径
  Bellman-Ford	O(VE)	O(V)	含负权边的单源最短路径
  Floyd-Warshall	O(V³)	O(V²)	多源最短路径

  ---

  六、

• 循环处理：每次选择未访问的最小距离节点，更新其邻居的距离。

c

#include <stdio.h>#include <limits.h>#define E 8  // 边数#define V 5  // 顶点数struct Edge {    int src, dest, weight;};void bellmanFord(struct Edge edges[], int src) {    int dist[V];    for (int i = 0; i < V; i++)        dist[i] = INT_MAX;    dist[src] = 0;    // 松弛所有边V-1次    for (int i = 1; i <= V - 1; i++) {        for (int j = 0; j < E; j++) {            int u = edges[j].src;            int v = edges[j].dest;            int w = edges[j].weight;            if (dist[u] != INT_MAX && dist[u] + w < dist[v])                dist[v] = dist[u] + w;        }    }    // 检测负权环    for (int j = 0; j < E; j++) {        int u = edges[j].src;        int v = edges[j].dest;        int w = edges[j].weight;        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {            printf("图中存在负权环！\n");            return;        }    }    // 输出结果    printf("顶点\t距离\n");    for (int i = 0; i < V; i++)        printf("%d\t%d\n", i, dist[i]);}int main() {    struct Edge edges[E] = {        {0, 1, -1}, {0, 2, 4}, {1, 2, 3},        {1, 3, 2}, {1, 4, 2}, {3, 2, 5},        {3, 1, 1}, {4, 3, -3}    };    bellmanFord(edges, 0);    return 0;}

代码逻辑：

1. 初始化：所有距离设为无穷大，起点为0。

2. 特殊场景：

   • 含负权边的最短路径（Bellman-Ford）。

   • 输出：更新后的最短距离矩阵。特殊方法与内置函数补充

     1. C++ STL的优先队列

     2. 动态规划思想

     3. 负权环检测

     ---

     一、

   例题2（含负权边）：

   • 输入：带负权边的图，检测是否存在负权环。

---

二、

附加功能：可检测负权环。特殊方法与内置函数补充

1. C++ STL的优先队列

• 作用：快速获取最小元素，用于优化Dijkstra算法。

3. 负权环检测

• Bellman-Ford扩展：若第V次迭代仍有更新，则存在负权环。

• 语法：priority_queue<T, Container, Compare>，需头文件<queue>。C语言实现

  解法1：Dijkstra算法（正权图，难度★★）

  解法2：Bellman-Ford算法（含负权边，难度★★★）

  四、

• 输出：若存在环返回false，否则返回最短路径。

cpp

#include <iostream>#include <vector>using namespace std;#define INF INT_MAXvoid floydWarshall(vector<vector<int>> &graph) {    int V = graph.size();    vector<vector<int>> dist = graph;    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]);    // 输出结果    cout << "最短路径矩阵：" << endl;    for (int i = 0; i < V; i++) {        for (int j = 0; j < V; j++)            cout << (dist[i][j] == INF ? "INF" : to_string(dist[i][j])) << "\t";        cout << endl;    }}int main() {    vector<vector<int>> graph = {        {0, 5, INF, 10},        {INF, 0, 3, INF},        {INF, INF, 0, 1},        {INF, INF, INF, 0}    };    floydWarshall(graph);    return 0;}

代码逻辑：

1. 初始化距离矩阵：直接复制图的邻接矩阵。

2. 输出：A到各顶点的最短距离（如A→D的最短距离为5）。

3. 多源最短路径：求所有点对之间的最短路径（如Floyd-Warshall算法）。

4. 时间复杂度：O(VE)，适合稀疏图。例题问题描述

   例题1（单源正权图）：

   • 输入：图的邻接矩阵，起点为A。

   • 含负权环的检测（Bellman-Ford扩展）。