图 单源最短路径延伸
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了图 单源最短路径延伸,现在分享给大家,供学习和参考。文章包含3550字,纯文字阅读大概需要9分钟。
教程信息
算法介绍
我们知道Dijkstra算法只能用来解决正权图的单源最短路径问题,但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了,而本文介绍的bellman—ford算法可以解决负权图且可以判断有无负权回路(迭代超过V-1次,就说明存在负权回路)的单源最短路径问题。
它的优点是可以解决有负权边的单源最短路径问题,而且可以用来判断是否有负权回路。
它也有明显的缺点,它的时间复杂度 O(N*E) (N是点数,E是边数)普遍是要高于Dijkstra算法O(N2)的。
思路讲解
1. 初始化源点s到各个点v的路径dis[v] = ∞,dis[s] = 0。
2. 进行n - 1次遍历,每次遍历对所有边进行松弛操作,满足则将权值更新。
松弛操作:以a为起点,b为终点,ab边长度为w为例。dis[a]代表源点s到a点的路径长度,dis[b]代表源点s到b点的路径长度。如果满足下面的式子则将dis[b]更新为dis[a] + w。
dis[b] > dis[a] + w
3. 遍历都结束后,若再进行一次遍历,还能得到s到某些节点更短的路径的话,则说明存在负环路。
案例分析与代码实现
案例分析
先举个栗子:
如下图按Bellman–Ford算法思路获取起点A到终点的最短路径
1.得出边权信息:
A B -1 A C 4 B C 3 B D 2 B E 2 D B 1 D C 5 E D -3
2.首先初始化起点A到各个节点耗费的时间:
父节点 | 节点 | 初始化 |
---|---|---|
A | A | 0 |
B | ∞ | |
C | ∞ | |
D | ∞ | |
E | ∞ |
3.进行第一次的遍历
(1). 统计经过一条边所能到达的节点的值
A B -1 A C 4
父节点 | 节点 | 路径长度 |
---|---|---|
A | A | 0 |
A | B | -1 |
A | C | 4 |
D | ∞ | |
E | ∞ |
(2). 统计经过二条边所能到达的节点的值
B D 2 B E 2 B C 3
父节点 | 节点 | 路径长度 |
---|---|---|
A | A | 0 |
A | B | -1 |
B | C | 2 |
B | D | 1 |
B | E | 1 |
以C节点为例:dis[B] + weight(B -> C) < dis[C](-1 + 3 < 4)则dis[C] = dis[B] + weight(B -> C)
(3).统计经过三条边所能到达的节点的值
D C 5 D B 1 E D -3
父节点 | 节点 | 路径长度 |
---|---|---|
A | A | 0 |
A | B | -1 |
B | C | 2 |
E | D | -2 |
B | E | 1 |
4.进行第二次遍历,发现没有权值更新,这时可以提前结束循环,优化效率。 | ||
5.则点A到其它点的最短路径与线路如图所示 | ||
父节点 | 节点 | 路径长度 |
– | – | – |
A | A | 0 |
A | B | -1 |
B | C | 2 |
E | D | -2 |
B | E | 1 |
实现代码:
#include <iostream> #include <string.h> using namespace std; #define INF 0x3f const int a = 2e4 + 5; int n, m; int q, p, w, road[a][a]; int dis[a]; int check = 0; void BellmanFord() { memset(dis, INF, sizeof(dis)); dis[1] = 0; for (int x = 1; x <= n; x++) { check = 0; for (int y = 1; y <= m; y++) { if (dis[y] > dis[x] + road[x][y]) { dis[y] = dis[x] + road[x][y]; check = 1; } } if (!check) { break; } } } int main() { scanf("%d%d", & n, & m); memset(road, INF, sizeof(road)); for (int x = 1; x <= m; x++) { scanf("%d%d%d", & q, & p, & w); road[q][p] = w; } BellmanFord(); for (int x = 2; x <= n; x++) { printf("%d\n", dis[x]); } }
执行结果:
优先队列优化(SPFA)
Bellman—Ford算法的队列优化还有一个名字叫做SPFA(各大竞赛都会进行卡SPFA)。
优化原理
简洁起见,我们约定加权有向图G不存在负权回路,即最短路径一定存在。用数组dis记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
代码实现:
#include <iostream> #include <algorithm> #include <string.h> #include <queue> #define inf 1e5 + 5 using namespace std; int n, m, s, t; int vis[1005], cost[1005], h[205]; int tot; struct Node //结点信息 { int to, w, next; } road[3000]; struct Node2 { int cost1, to; friend bool operator < (Node2 x, Node2 y) { return x.cost1 > y.cost1; } } road1[3000]; void add(int u, int v, int w) //链式前向星存储邻接表 { road[tot].to = v; road[tot].w = w; road[tot].next = h[u]; h[u] = tot++; } void SPFA(int s) { priority_queue < Node2 > pq; int e = 0; memset(vis, 0, sizeof(vis)); cost[s] = 0; road1[e].cost1 = 0; road1[e].to = s; pq.push(road1[e]); while (!pq.empty()) { int x = pq.top().to; pq.pop(); if (vis[x]++) continue; for (int i = h[x]; i != -1; i = road[i].next) { int to = road[i].to; if (!vis[to] && cost[x] + road[i].w <= cost[to]) { cost[to] = cost[x] + road[i].w; e++; road1[e].cost1 = cost[to]; road1[e].to = to; pq.push(road1[e]); } } } } int main() { while (~scanf("%d%d", & n, & m)) { int u, v, w; tot = 0; memset(h, -1, sizeof(h)); for (int x = 0; x < 1005; x++) { cost[x] = inf; } for (int i = 0; i < m; i++) { cin >> u >> v >> w; add(u, v, w); add(v, u, w); } cin >> s >> t; SPFA(s); if (cost[t] == inf) { cout << -1 << endl; } else { cout << cost[t] << endl; } } }
执行结果:
文章来源:https://blog.csdn.net/hahahahahaha5/article/details/119022511
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供图 单源最短路径延伸的全部内容,希望教程文章能够帮你了解学习图 单源最短路径延伸,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-335.html