Loading... SPFA算法是一种基于贪心思想的单源最短路径算法,它的核心思想是通过不断松弛每一条边来更新每个节点的最短路径。具体来说,我们维护一个队列,将起点加入队列中,然后不断从队列中取出节点,并将其邻居节点加入队列中。每次取出一个节点时,我们遍历其所有邻居节点,如果发现某个邻居节点的最短路径可以通过当前节点更新,则更新该邻居节点的最短路径,并将其加入队列中。这样,我们就可以不断地松弛每一条边,直到所有节点的最短路径都被更新为止。 每次选择当前距离起点最近的一个点进行扩展。具体实现时,维护一个队列,将起点加入队列,然后每次从队列中取出一个点,遍历该点的所有出边,并更新与这些出边相连的点的距离。如果某个点的距离被更新,则将该点加入队列中,继续扩展。 我们可以使用一个数组dist来记录每个节点的最短路径长度,初始时,将起点的dist值设为0,其他节点的dist值设为正无穷大。然后将起点加入队列中,不断从队列中取出节点,并遍历其所有邻居节点,如果发现某个邻居节点的最短路径可以通过当前节点更新,则更新该邻居节点的dist值,并将其加入队列中。最后,当队列为空时,所有节点的最短路径长度就被计算出来了。 需要注意的是,如果存在负权环,则最短路不存在。因为在负权环中,可以无限次地绕圈,因此最短路没有意义。为了判断是否存在负权环,可以记录每个点进队列的次数,如果某个点进队列的次数超过n次,则说明存在负权环。 ``` #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } int t = spfa(); if (t == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", t); return 0; } ``` 最后修改:2023 年 12 月 21 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏