以前做弹幕现在的电影网站,深圳企业有哪些,精美微信小程序模板,佛山网站建设培训文章目录1 Dijkstra 算法2 Bellman-Ford 算法3 SPFA 算法4 Floyd 算法1 Dijkstra 算法
Dijkstra#xff08;迪杰斯特拉#xff09;算法适用于单源最短路径问题#xff0c;即从一个起点出发#xff0c;计算到所有其他点的最短路径。它只能用于边权非负的图#xff08;所有…
文章目录1 Dijkstra 算法2 Bellman-Ford 算法3 SPFA 算法4 Floyd 算法1 Dijkstra 算法
Dijkstra迪杰斯特拉算法适用于单源最短路径问题即从一个起点出发计算到所有其他点的最短路径。它只能用于边权非负的图所有边的权重 ≥ 0无法解決带负权的图的最短路问题。
Dijkstra 算法的核心思想是贪心算法将所有节点分为已确定最短路径的节点和未确定最短路径的节点:
初始时将所有顶点的最短距离设为∞源点的距离设为0每次从未确定节点中选择距离最小的节点作为当前节点将其标记为已确定遍历当前节点的所有邻居更新该节点的所有邻居节点的距离松弛操作重复上述过程直到所有节点都被加入已确定集合 “松弛”就是检查当前路径是否更短如果是就更新最短距离。 邻接矩阵迭代
const int N 1010;
int n, m, s, mp[N][N], dis[N]; // 节点 边 起始点 图 距离
bool vis[N]; // 已确定节点void dij() { fill(dis, dis N, INT_MAX); // 未确定节点的距离设为无穷大dis[s] 0; // 起始节点距离设为0// 一次确定一个节点的最短路n个节点需要n次循环for(int i 1; i n; i) { int id 0; // id标记当前节点初始化为0距离为无穷大for(int j 1; j n; j) // 在未确定节点中寻找距离最小的节点if (!vis[j] dis[j] dis[id]) id j; vis[id] true; // 将当前节点标记为已确定for (int j 1; j n; j) // 松弛当前节点的邻居从当前节点出发路径更短if (mp[id][j] ! INT_MAX dis[id] mp[id][j] dis[j]) dis[j] dis[id] mp[id][j]; }
}递归实现数据稍大会栈溢出
const int N 1010;
int n, m, s, mp[N][N], dis[N]; // 节点 边 起始点 图 距离
bool vis[N]; // 已确定节点void dij(int id) { // 当前节点int mini INT_MAX, ni -1; // 未确定节点中的最短距离和节点编号vis[id] true; // 标记为已确定for(int i 1; i n; i) { if(!vis[i]) { // 遍历还未确定的节点// 当前节点能访问到的邻居 并且 从当前节点出发的路径更短if(mp[id][i] ! INT_MAX dis[id] mp[id][i] dis[i]) dis[i] dis[id] mp[id][i]; // 松弛// 在所有还未确定的节点中寻距离最短的if(dis[i] mini) { mini dis[i]; // 更新最短距离ni i; // 更新节点编号} } } // 如果找到了未确定节点中的最短距离节点作为当前节点传入dijif(ni ! -1) dij(ni);
} int main() { cin n m s; fill(mp[0], mp[0] N * N, INT_MAX); // 边初始化为无穷大while(m--) { int u, v, w; cin u v w; mp[u][v] min(mp[u][v], w); // 处理重边 } fill(dis, dis N, INT_MAX); // 距离初始化为无穷大dis[s] 0; // 起始点距离初始化为0dij(s); for(int i 1; i n; i) if(dis[i] ! INT_MAX) cout dis[i] ; else cout -1 ;
}2 Bellman-Ford 算法
Bellman-Ford贝尔曼-福特算法是用于解决单源最短路径问题的经典算法它可以处理图中包含负权边的情况并能检测出图中是否存在负环。
Bellman-Ford算法的核心是“不断松弛边”。对所有边进行 n - 1 次松弛n为顶点个数之后再跑一次检测负环。
初始化将所有顶点的最短距离估计值设为∞源点的距离设为0松弛操作重复 n-1 次松弛每次遍历所有边对每条边进行松弛操作检查负环再进行一次松弛操作如果还能更新则说明存在负环 为什么进行 n-1 次松弛因为进行一次 Bellman-Ford距离起点一条边的点的最短路确定 进行两次距离起点两条边的点的最短路确定 总共n个点最短路最多经过 n-1 条边所以进行 n-1 次松弛即可。 const int N 1e5 10;
int n, m, s, t, dis[N]; // 节点数 边数 起始点 目标点 距离
struct Edge { int u; int v; int w; Edge(int from, int to, int weight) : u(from), v(to), w(weight) {}
};
vectorEdge egs; // 使用边集数组进行存储方便对每一条void bf() { // 除起始点之外的距离设为无穷大fill(dis, dis N, 1e9); dis[s] 0; for(int i 1; i n; i) { // n-1 次操作每次确定距离为 i 的节点最短路for(int j 1; j m; j) { // 每次操作对所有边进行// 当前边的起始点 当前边的到达点 当前边的权值int from egs[j].u, to egs[j].v, weight egs[j].w; if(dis[from] weight dis[to]) // 松弛操作dis[to] dis[from] weight; } }} int main() { cin n m s t; egs.emplace_back(0, 0, 0); // 占位 vector 的 0 号位for(int i 0; i m; i) { int x, y, z; cin x y z; // 直接将 Edge(x,y,z) push_back 进 vectoregs.emplace_back(x, y, z); } bf(); cout dis[t]; return 0;
}3 SPFA 算法
SPFAShortest Path Faster Algorithm是 Bellman-Ford 算法的队列优化版本用于求单源最短路径减少了不必要的冗余运算同样可以处理存在负权边的情况。
与 Bellman-Ford 每次都遍历所有边不同SPFA 利用队列优化了 Bellman-Ford 算法中不必要的松弛操作只对发生了松弛操作的结点的邻接结点进行松弛。
初始化所有节点到起始点的距离为 ∞源点为 0将源点入队并标记为在队列中当队列不为空时 取出队首节点作为当前节点弹出并标记为不在队列中遍历从当前节点的所有临接边尝试松弛操作如果松弛成功判断这个邻居节点是否在队列中如果不在则入队 重复以上操作直到队列为空
const int N 5010;
int n, m, s, t, dis[N], mp[N][N]; // 节点 边 源点 终点 距离 图
queueint q; // 辅助队列
bool vis[N]; // 标记节点是否在队列void spfa() { // 除源点外的其他节点距离初始化为无穷大fill(dis, dis N, 1e9); dis[s] 0; q.push(s); // 源点入队vis[s] true; // 并把源点标记为在队列while(!q.empty()) { int id q.front(); // 取出队首元素q.pop(); vis[id] false; // 标记为不在队列for(int i 1; i n; i) {// 遍历所有邻居节点if(mp[id][i] ! 1e9 dis[id] mp[id][i] dis[i]) { dis[i] dis[id] mp[id][i]; // 松弛// 如果不在队列则入队并标记为在队列if(!vis[i]) { q.push(i); vis[i] true; } } } }
}SPFA 每轮更新中将“更近一层”的节点的最短路径传递出去这个过程和 BFS 逐层访问节点的方式有点相似。 4 Floyd 算法
