spfa模板

SPFA算法的本质是队列优化的Bellman-Ford算法

• 使用一个queue保存待优化的node, 每次取出队首节点u, 并且用u点当前的最短路估计值对u点所指向的节点v进行松弛.

• 如果满足三角不等式dist[v]>dist[u]+w[u,v]满足, 则将v插入队尾, 循环知道队列为空.

SPFA可以用来判断负环, 如果某个点出队次数超过n-1次, 则存在负环, 对于存在负环的图, 无法计算单源最短路径.

c++ spfa

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
#define fi first
#define se second

const int N=2505;
int n, m, S, T;
int dist[N];
bool vis[N]; // 记录当前点是否在队列中
vector<PII> G[N];
queue<int> q;

void spfa(){
    dist[S]=0;
    q.push(S);
    vis[S]=true;
    while(!q.empty()){
        int node=q.front();
        q.pop();
        vis[node]=false;
        for(PII &e: G[node]){
            int v=e.fi;
            int w=e.se;
            if(dist[v]>dist[node]+w){
                dist[v]=dist[node]+w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
}


int main(){
    memset(vis, 0x00, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    cin>>n>>m>>S>>T;
    for(int i=0; i<m; ++i){
        int a, b, c;
        cin>>a>>b>>c;
        // 建立无向图
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    spfa();
    cout<<dist[T]<<endl;
    return 0;
}

python spfa

from typing import List
class Solution:
    def main(self, G:List[List], S:int, T:int):
        q, INF=[], 0x3f3f3f3f
        vis=[False for _ in range(n+1)]
        dist=[INF for _ in range(n+1)]

        def spfa():
            dist[S]=0
            q.append(S)
            vis[S]=True
            while q:
                node = q.pop(0)
                vis[node]=False
                for e in G[node]:
                    v, w=e[0], e[1]
                    if dist[v]>dist[node]+w:
                        dist[v]=dist[node]+w
                        if not vis[v]:
                            q.append(v)
                            vis[v]=True

        spfa()
        print(dist[T])


if __name__ == '__main__':
    n, m, S, T=map(int, input().split())
    G=[[] for _ in range(n+1)]
    for _ in range(m):
        u, v, w=map(int, input().split())
        G[u].append((v, w))
        G[v].append((u, w))

    sol=Solution()
    sol.main(G, S, T)