Algorithm14.1.3 SPFA
[TOC]
最短路-SPFA
SPFA
- 数据结构类似于Dijkstra，也是d数组和vi/vis数组
- 首先起点入队，标记已达
- 开始循环遍历队列，此时不用判断是否已是vis。（Dijkstra是需要判断两次的）
- 出队，标记未达
- 遍历到之后再次给标记已达。
int d[maxpoint], vi[maxpoint];
queue<nd> spf;
void spfa(int s) {
for (int i = 1; i <= n; ++i) d[i] = INF;d[s] = 0;
spf.push({0, s});vi[s] = 1;
while (!spf.empty()) {
nd nw = spf.front();spf.pop();
int nwpos = nw.pos;
vi[nwpos] = 0;
for (int i = head[nwpos]; i; i=edge[i].next) {
int to = edge[i].to;
if (d[to] > d[nwpos]+edge[i].cost) {
d[to] = d[nwpos]+edge[i].cost;
if (!vi[to]) {spf.push({d[to], to});vi[to] = 1;}
}
}
}
for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
}
区分于Dijkstra：
- 首先上来不用管任何节点的vis，因为只是表示是否划分点集
- 然后遍历到当前点之前要判断!vis
- 遍历到了之后要立刻把vis置为1
- 然后遍历到当前点的所有相邻点要判断vis，来查看是否可以放入
void dijkstra(int s) {
for (int i = 1; i <= n; ++i) dis[i] = INF;
dis[s] = 0;
pq.push(nd(0, s));
while (!pq.empty()) {
nd nw = pq.top();pq.pop();
int from = nw.pos;
if (!vis[from]) {
vis[from] = 1;
for (int i = head[from]; i; i=edge[i].next) {
int to = edge[i].to;
if (dis[to] > dis[from]+edge[i].cost) {
dis[to] = dis[from]+edge[i].cost;
if (!vis[to]) pq.push(nd(dis[to], to));
}
}
}
}
for (int i = 1; i <= n; ++i) printf("%d ", dis[i]);
}