最短路径问题

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

---

目录

最短路径问题

一、题型解释

二、例题问题描述

三、C语言实现

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

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

四、C++实现

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

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

五、总结对比表

六、特殊方法与内置函数补充

1. C++ STL的优先队列

2. 动态规划思想

3. 负权环检测

---

一、题型解释

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

1. 单源最短路径：求某一点到其他所有点的最短路径（如Dijkstra、Bellman-Ford算法）。

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

3. 特殊场景：

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

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

   • 边权为1的图（BFS优化）。

---

二、例题问题描述

例题1（单源正权图）：

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

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

例题2（含负权边）：

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

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

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

• 输入：任意两点间的最短距离矩阵。

• 输出：更新后的最短距离矩阵。

---

三、C语言实现

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

通俗解释：

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

• 适用条件：边权非负。

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;  // 起点到自身距离为0for (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。

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

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

---

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

通俗解释：

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

• 附加功能：可检测负权环。

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. 松弛操作：进行V-1轮边遍历更新距离。

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

4. 时间复杂度：O(VE)，适合稀疏图。

---

四、C++实现

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

通俗解释：

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

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. 懒惰删除：当队列中的距离大于记录的距离时跳过。

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

---

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

通俗解释：

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

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. 三重循环：依次考虑每个中间节点k，更新所有i→j路径。

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

---

五、总结对比表

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

---

六、特殊方法与内置函数补充

1. C++ STL的优先队列

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

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

2. 动态规划思想

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

3. 负权环检测

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

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