SPFA算法（Bellman-ford算法队列优化）（邻接表）（C++实现）
SPFA算法（Bellman-ford算法队列优化）（贝尔曼-福特算法队列优化）（邻接表）（C++实现）
实现代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Sat Apr 18 17:39:56 2020
*/#include<bits/stdc++.h>
using namespace std;const int INF = 0xFFFF;struct Edge{int to;int weight;
};vector< vector<Edge> > adjacentList;
vector<int> path;
vector<int> dist;bool spfa(int vexNum, int source) {queue<int> q;vector<int> cnt;vector<bool> tag;cnt.resize(vexNum);tag.resize(vexNum);for (int i = 0; i < vexNum; i++) {dist[i] = INF;cnt[i] = 0;tag[i] = false;}q.push(source);tag[source] = true;dist[source] = 0;path[source] = source + 1;while (!q.empty()) {int u = q.front();q.pop();tag[u] = false;for (int i = 0; i < adjacentList[u].size(); i++) {Edge edge = adjacentList[u][i];if (dist[edge.to] > dist[u] + edge.weight) {dist[edge.to] = dist[u] + edge.weight;path[edge.to] = u + 1;if (!tag[edge.to]) {q.push(edge.to);tag[edge.to] = true;if (++cnt[edge.to] > vexNum) {return false;}}}}}return true;
}void print() {printf("SPFA path\n");for (int i = 0; i < path.size(); i++) {printf("%d ", path[i]);}printf("\nSPFA edges weight\n");for (int i = 0; i < dist.size(); i++) {printf("%d ", dist[i]);}printf("\n");
}int main(int argc, char const *argv[])
{int from, to;int weight;int vexNum;int edgeNum;int source;while (~scanf("%d%d%d", &vexNum, &edgeNum, &source)) {adjacentList.resize(vexNum);path.resize(vexNum);dist.resize(vexNum);for (int i = 0; i < edgeNum; i++) {scanf("%d%d%d", &from, &to, &weight);adjacentList[from - 1].push_back((Edge){to - 1, weight});}if (spfa(vexNum, source - 1)) {print();} else {printf("Negative circle exists!\n");}adjacentList.clear();path.clear();dist.clear();}return 0;
}
算法思路
- SPFA算法的思想和BFS算法思想
SPFA算法的思想和BFS算法思想相似，都可以通过队列优化，都是在较“广”地进行搜索 - 思路
借助队列存放待优化的顶点，每次将队首顶点的所有邻接点入队，更新邻接顶点最短路径累积权值，对每个邻接点进行“松弛”操作，若邻接顶点对应的dist数组值需要更新，则将邻接顶点入队，队首元素出队，重新选择队首元素，循环上述操作，直至队列为空 - 定理——百度百科
只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。 - 负权环判定
负权环会导致累积权值无限降低，故不存在最短路。根据上述的算法思路，每次顶点入队都将进行优化，也只有需要被优化才会入队。存在最短路径顶点情况下，每个顶点所对应dist数组的值最多被更新|V| - 1次，即最多入队|V| - 1次（其最多存在|V|-1个邻接点，对应dist数组值最多被更新|V|-1次，上述算法对队首顶点的所有邻接点进行判断更新，极限情况下，若所有邻接点对一个顶点对应dist数组值更新一次则最多为|V|-1次），否则则表示存在负权环，故判定入队次数是否大于n即可判定网中是否存在负权环。 - 复杂度
上述算法在最坏情况下时间复杂度复杂度为O(|V|·|E|) - 注释
主要代码及注释与Bellman-ford算法相似，在此不再赘述 - 样例
测试数据与Dijkstra，Floyd,Bellman-ford等算法的样例相似，再次便不再赘述 - Dijkstra算法
- Bellman-ford算法
测试数据
3 5 1
1 2 6
1 3 13
2 1 10
2 3 4
3 1 53 5 1
1 2 -10
2 3 1
3 1 6
2 1 1
1 3 4
输出结果
SPFA path
1 1 2
SPFA edges weight
0 6 10
Negative circle exists!
鸣谢
- 感谢百度百科提供的百科知识
- 感谢刘汝佳和陈锋编著的算法竞赛入门经典：训练指南提供的宝贵思路，上述借鉴了书中的Bellman-Ford算法并稍加修改
最后
- 为了避免最坏情况的出现，在正权图上应使用效率更高的Dijkstra算法，经过堆优化的Dijkstra算法时间复杂度较为稳定地保持在O(|V| · lg|E|)
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
发布评论