php网站外包,torrent种子猫,python做网站 jsp网站,发软文是什么意思最短路径问题
-返回c/c蓝桥杯经典编程题100道-目录 目录
最短路径问题
一、题型解释
二、例题问题描述
三、C语言实现
解法1#xff1a;Dijkstra算法#xff08;正权图#xff0c;难度★★#xff09;
解法2#xff1a;Bellman-Ford算法#xff08;含负权边返回c/c蓝桥杯经典编程题100道-目录 目录
最短路径问题
一、题型解释
二、例题问题描述
三、C语言实现
解法1Dijkstra算法正权图难度★★
解法2Bellman-Ford算法含负权边难度★★★
四、C实现
解法1Dijkstra算法优先队列优化难度★★☆
解法2Floyd-Warshall算法多源最短路径难度★★★
五、总结对比表
六、特殊方法与内置函数补充
1. C STL的优先队列
2. 动态规划思想
3. 负权环检测 一、题型解释
最短路径问题是图论中的核心问题目标是找到图中两点间权重和最小的路径。常见题型 单源最短路径求某一点到其他所有点的最短路径如Dijkstra、Bellman-Ford算法。 多源最短路径求所有点对之间的最短路径如Floyd-Warshall算法。 特殊场景 含负权边的最短路径Bellman-Ford。 含负权环的检测Bellman-Ford扩展。 边权为1的图BFS优化。 二、例题问题描述
例题1单源正权图 输入图的邻接矩阵起点为A。 输出A到各顶点的最短距离如A→D的最短距离为5。
例题2含负权边 输入带负权边的图检测是否存在负权环。 输出若存在环返回false否则返回最短路径。
例题3多源最短路径 输入任意两点间的最短距离矩阵。 输出更新后的最短距离矩阵。 三、C语言实现
解法1Dijkstra算法正权图难度★★
通俗解释 贪心策略每次选择当前距离起点最近的节点逐步扩展最短路径集合。 适用条件边权非负。
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;
}
代码逻辑 初始化距离数组dist设为无穷大起点距离为0。 循环处理每次选择未访问的最小距离节点更新其邻居的距离。 时间复杂度O(V²)适合稠密图。 解法2Bellman-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;
}
代码逻辑 初始化所有距离设为无穷大起点为0。 松弛操作进行V-1轮边遍历更新距离。 负权环检测若第V轮仍有更新说明存在负权环。 时间复杂度O(VE)适合稀疏图。 四、C实现
解法1Dijkstra算法优先队列优化难度★★☆
通俗解释 使用优先队列快速获取最小距离节点时间复杂度优化至O((VE)logV)。
cpp
#include iostream
#include vector
#include queue
#include climits
using namespace std;typedef pairint, int pii; // {距离, 节点}void dijkstra(vectorvectorpii graph, int src) {int V graph.size();vectorint dist(V, INT_MAX);priority_queuepii, vectorpii, greaterpii 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;vectorvectorpii 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;
}
代码逻辑 优先队列存储{距离, 节点}自动按距离排序。 懒惰删除当队列中的距离大于记录的距离时跳过。 STL使用vector存邻接表priority_queue实现最小堆。 解法2Floyd-Warshall算法多源最短路径难度★★★
通俗解释 动态规划通过中间节点逐步优化所有点对的最短路径。
cpp
#include iostream
#include vector
using namespace std;#define INF INT_MAXvoid floydWarshall(vectorvectorint graph) {int V graph.size();vectorvectorint 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() {vectorvectorint graph {{0, 5, INF, 10},{INF, 0, 3, INF},{INF, INF, 0, 1},{INF, INF, INF, 0}};floydWarshall(graph);return 0;
}
代码逻辑 初始化距离矩阵直接复制图的邻接矩阵。 三重循环依次考虑每个中间节点k更新所有i→j路径。 时间复杂度O(V³)适合小规模图。 五、总结对比表
算法时间复杂度空间复杂度适用场景DijkstraO((VE)logV)O(V)正权图单源最短路径Bellman-FordO(VE)O(V)含负权边的单源最短路径Floyd-WarshallO(V³)O(V²)多源最短路径 六、特殊方法与内置函数补充
1. C STL的优先队列 作用快速获取最小元素用于优化Dijkstra算法。 语法priority_queueT, 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道-目录
