SPFA算法可以求解带权有向图上某个点到其余点的最短路径距离,支持负权边。
时间复杂度:如果图是随机生成的,时间复杂度为O(K·M),K是某个常数;最坏情况下时间复杂度为O(N·M)。
用dis数组记录源点到有向图上任意一点的距离,其中源点到自身距离为0,到其他点距离为INF。将源点入队,并重复以下步骤:
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <climits>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
const int MAXN = 10005;
const int MAXM = 500005;
const int INF = 0x3f3f3f3f;
struct Edge {
int dest, next, weight;
} edges[MAXM];
int head[MAXN];
int edges_cnt;
int dis[MAXN]; // 源点到每个点的最短距离
bool inq[MAXN]; // 某个点是否在队列内
int n, m, s;
void addEdge(int src, int dest, int weight) {
++edges_cnt;
edges[edges_cnt].dest = dest;
edges[edges_cnt].weight = weight;
edges[edges_cnt].next = head[src];
head[src] = edges_cnt;
}
void spfa(int src) {
memset(dis, 0x3f, sizeof(dis));
memset(inq, 0, sizeof(inq));
dis[src] = 0;
queue<int> q;
q.emplace(src);
while (!q.empty()) {
int top = q.front();
q.pop();
inq[top] = false;
for (int i = head[top]; i; i = edges[i].next) {
int dest = edges[i].dest;
int weight = edges[i].weight;
if (dis[top] + weight < dis[dest]) {
dis[dest] = dis[top] + weight;
if (!inq[dest]) {
q.emplace(dest);
inq[dest] = true;
}
}
}
}
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d%d", &n, &m, &s);
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
}
spfa(s);
for (int node = 1; node <= n; ++node) {
printf("%d ", dis[node] < INF ? dis[node] : INT_MAX);
}
putchar('\n');
return 0;
}
本文地址:https://blog.csdn.net/hcmdghv587/article/details/107599391
如对本文有疑问, 点击进行留言回复!!
pytorch安装实录(win10+cuda8+pycharm+anaconda)
小练习题(69)有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位
两种方法 更改jupyter notebook的打开路径/默认工作路径
RobotFramework接口自动化-全局变量解决保持登录问题
mysql中如何实现 row_number分组求topN的功能
网友评论