SPFA 求最短路（poj2387）

小咪咪 2021-11-26 16:38 269阅读 0赞

*  SPFA 最短路算法
    
     *  原理
     *  例题
     *  题解

# SPFA 最短路算法 #

--------------------

## 原理 ##

spfa的算法思想（动态逼近法）：  
设立一个先进先出的队列q用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

## 例题 ##

[poj 2387 Til the Cows Come Home][]  
题目大意：裸的最短路，只不过是倒过来

## 题解 ##

具体可以看[B站视频][B]

#include <algorithm> #include <iostream> #include <queue> #include <memory.h> #define maxn 2005 #define INF 0x3f3f3f using namespace std; vector<pair<int, int>> e[maxn];//不定长pair数组的大小为maxn的数组 queue<int> q;//要计算的队列 int d[maxn];//某点到目标点的距离 int inq[maxn];//某点是否在要计算的队列中 int t, n;//t 条边，n个点 void init() { for (int i = 0; i <= n; i++) inq[i] = 0; for (int i = 0; i <= n; i++) d[i] = INF; for (int i = 0; i <= n; i++) e[i].clear();//清空 } void spfa() { q.push(n - 1);//push进去起点 d[n - 1] = 0; while (!q.empty()) { int now = q.front(); inq[now] = 0; q.pop(); for (int i = e[now].size() - 1; i >= 0; i--) { int v = e[now][i].first; if (d[v] > d[now] + e[now][i].second) { d[v] = d[now] + e[now][i].second; if (inq[v] == 1) continue; inq[v] = 1; q.push(v); } } } } int main() { cin >> t >> n; init(); for (int i = 0; i < t; i++) { int x, y, z; cin >> x >> y >> z; x--, y--; e[x].push_back(make_pair(y, z)); e[y].push_back(make_pair(x, z));//这里类似邻接表，不用做去重处理 } spfa(); cout << d[0];//d[x] x为终点 }

转载于:https://www.cnblogs.com/tttfu/p/11228372.html

[poj 2387 Til the Cows Come Home]: http://poj.org/problem?id=2387
[B]: https://www.bilibili.com/video/av4224493?from=search&seid=6840934442890208980