wordpress 删除自己的评论,seo搜索引擎优化简历,电子商务公司企业简介,怎样下载广安同城app1. Bellman-Ford
该算法适用于有负权边的情况#xff0c;注意#xff1a;如果有负权环的话#xff0c;最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路#xff0c;但求解负权回路#xff0c;通常用SPFA算法#xff0c…1. Bellman-Ford
该算法适用于有负权边的情况注意如果有负权环的话最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路但求解负权回路通常用SPFA算法而不用Bell-Ford算法因为前者的时间复杂度更低。
Bellman-ford不要求用邻接表或者邻接矩阵存储边为简化操作可以定义一个结构体存储abw。表示存在一条边a点指向b点权重为w。则遍历所有边时只要遍历全部的结构体数组即可
主要步骤
循环n次循环的次数的含义假设循环了k次则表示从起点经过不超过k条边走到某个点的最短距离每次循环遍历图中的所有的边。对每条边(a,b,w),(指的是从a点到b点权值是w的一条边更新d[b] min(d[b],d[a]w)。该操作称为松弛操作。该算法能够保证在循环n次后对所有的边(a,b,w),都满足d[b] d[a] w。这个不等式被称为三角不等式。
ACwing 853. 有边数限制的最短路
实现思路
利用上述的Bellman-ford算法依旧定义一个距离数组dist,初始化未正无穷(0x3f3f3f3f)。注意最后判断到n号节点是否有路径不是直接判断dist[n] 0x3f3f3f3f,因为存在负权边可能更新的时候会存在dist[n] 0x3f3f3f3f - c,即无穷大加上一个负数仍为无穷大但数值还是改变了所以最后有路径的判断改为dist[n] 0x3f3f3f3f / 2.本题要求1号到n号点不超过k条边的最短距离则循环k次来寻找最短路每次再遍历m条边判断加入当前点后各店点到起点的距离是否变小若变小则更新距离注意该距离更新时可能会导致参与的边的数量大于k因此应在每次遍历前设置一个备份数组backup,记录在k次遍历中本次遍历的上一次的距离数组状态在该次遍历中对每条边的距离数组更新时采用备份数组确保本次更新范围在当前的边数限制内。
具体实现代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 510, M 10010;int n, m, k; // n: 顶点数, m: 边数, k: 最多使用的边数
int dist[N], backup[N]; // dist: 存储当前节点的最短距离backup: 每轮备份上一轮的最短距离// 定义一个结构体存储边的信息
struct Edge {int a, b, w; // a: 起点, b: 终点, w: 边的权重
} edges[M]; // 存储所有的边最多 M 条// Bellman-Ford 算法的核心函数返回 1 到 n 的最短距离
int bellman_ford() {// 初始化距离数组将所有点的距离设置为一个非常大的值(无穷大)memset(dist, 0x3f, sizeof dist);dist[1] 0; // 源点起点1到自己的距离为 0// Bellman-Ford 算法允许最多使用 k 条边来放松所有边for (int i 0; i k; i) { // 执行 k 轮松弛操作memcpy(backup, dist, sizeof dist); // 将当前距离备份// 遍历每条边尝试更新目标顶点的最短距离for (int j 0; j m; j) {int a edges[j].a, b edges[j].b, w edges[j].w; // 获取边的起点终点和权重dist[b] min(dist[b], backup[a] w); // 更新顶点 b 的距离}}// 如果最终 dist[n] 的值仍然非常大说明无法在 k 条边以内到达顶点 nif (dist[n] 0x3f3f3f3f / 2) return -1; // 0x3f3f3f3f 是表示无穷大的近似值return dist[n]; // 返回最短路径距离
}int main() {cin n m k; // 读取顶点数 n, 边数 m 和最多可用边数 k// 读取每条边的起点、终点和权重并存入 edges 数组for (int i 0; i m; i) {int a, b, w;cin a b w;edges[i] {a, b, w};}// 调用 bellman_ford 函数计算最短路径int t bellman_ford();// 如果 t 返回 -1 且 dist[n] 不是 -1没有负权环输出 impossibleif (t -1 dist[n] ! -1) puts(impossible); else cout t endl; // 否则输出最短路径的距离return 0;
}2.SPFA 若要使用SPFA算法一定要求图中不能有负权回路。只要图中没有负权回路都可以用SPFA即也可以求解正权边的题这个算法的限制是比较小的。时间复杂度一般为 O ( m ) O(m) O(m)最差为 O ( m n ) . O(mn). O(mn).在一些情况下可以代替Dijkstra算法 SPFA其实是对Bellman-Ford的一种优化相比Bellman-Ford判环的时间复杂度也更低。 它优化的是这一步d[b] min (d[b],d[a] w) 我们观察可以发现只有当d[a]变小了在下一轮循环中以a为起点的点或者说a的出边就会更新即下一轮循环必定更新d[b]。 考虑用一个队列queue来存放距离变小的节点(当图中存在负权回路时队列永远都不会为空因为总是存在某个点在一次松弛操作后距离变小。
具体实现代码详解版
#include iostream
#include cstring
#include algorithm
#include queueusing namespace std;const int N 100010;int e[N], ne[N], idx, w[N], h[N]; // e: 邻接点, ne: 下一条边的索引,
//idx: 当前边的索引, w: 边的权重, h: 头节点int dist[N]; // 存储从起点 1 到每个节点的最短距离
int n, m;
bool s[N]; // 记录节点是否在队列中避免重复入队// 添加一条从 a 到 b 的边权重为 c 的边
void add(int a, int b, int c) {e[idx] b; // 终点 bne[idx] h[a]; // 将边 idx 加到节点 a 的邻接表中w[idx] c; // 边的权重h[a] idx; // 更新节点 a 的头指针指向新加的边
}// SPFA 算法求解最短路径
int spfa() {memset(dist, 0x3f, sizeof dist); // 初始化距离为无穷大dist[1] 0; // 起点 1 到自己的距离为 0queueint q; // 定义队列用于处理节点q.push(1); // 将起点 1 入队s[1] true; // 标记起点 1 已入队// 队列不为空时进行循环while (q.size()) {auto t q.front(); // 取出队首节点q.pop(); // 弹出队首节点s[t] false; // 标记节点 t 不在队列中// 遍历节点 t 的所有邻接边for (int i h[t]; i ! -1; i ne[i]) {int j e[i]; // 获取节点 t 的邻接点 j// 如果从节点 t 到 j 的路径更短则更新 j 的距离if (dist[j] dist[t] w[i]) {dist[j] dist[t] w[i];// 如果节点 j 不在队列中则将其加入队列if (!s[j]) {s[j] true; // 标记节点 j 已入队q.push(j); // 节点 j 入队}}}}// 如果终点 n 的距离仍然为无穷大表示无法到达返回 -1if (dist[n] 0x3f3f3f3f / 2) return -1;else return dist[n]; // 否则返回最短距离
}int main() {cin n m; // 输入节点数 n 和边数 mmemset(h, -1, sizeof h); // 初始化头节点数组为 -1表示没有边// 读取每条边的信息并调用 add 函数将其加入邻接表while (m--) {int a, b, w;cin a b w;add(a, b, w);}// 调用 spfa 函数计算最短路径int t spfa();// 如果最短距离为 -1且终点距离不为 -1则输出 impossibleif (t -1 dist[n] ! -1) puts(impossible);else cout t endl; // 否则输出最短路径的距离return 0;
}
