Cpp算法-图论-SPFA

说明

n, m, s点数、边数、源点

cnt, head[], edge[], add(int, int, int)链式前向星

dist[]各点到源点路径长

vis[]记录

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
const int maxn = 10010;
const int maxm = 500010;

int n, m, s, dist[maxn], vis[maxn];

int cnt, head[maxn];
struct Edge
{
int next, to, dis;
}edge[maxm];
void add(int from, int to, int dis)
{
edge[++cnt].next = head[from];
edge[cnt].to = to;
edge[cnt].dis = dis;
head[from] = cnt;
}

void SPFA()
{
queue<int> q;
for (int i = 1; i <= n; ++i)
{
dist[i] = INT_MAX;
}
q.push(s);
dist[s] = 0; vis[s] = true;
while (!q.empty())
{
int u = q.front();
q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if (dist[v] > dist[u] + edge[i].dis)
{
dist[v] = dist[u] + edge[i].dis;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
return;
}
作者

TonyCrane

发布于

2019-01-10

更新于

2020-05-05

许可协议