算法模板之SPFA

标签：static   problem   链式前向星   队列   tar   遍历   math   pre   turn   

Bellman-Ford能够处理带负权图的单源最短路问题。（带负劝环的图，无法求出单源最短路）

Bellman-Ford的主要思想如下：

? 给定一张有向图，若对于图中的某一条边(x,y,z),有\(dist[y]成立,则称该边满足三角不等式。若所有边都满足三角不等式，则dist数组就是所求最短路

Bellman-Ford的流程如下：

1. 扫描所有的边(x,y,z),若dist[y] > dist[x] + z , 则用dist[x] + z 更新 dist[y]

2. 重复上述步骤，直到没有更新操作发生。

SPFA是在上述基础上，使用队列进行优化，核心思想就是说：只有已经被松弛的点，才可能去松弛其他的点。我们可以通过队列来维护已经被松弛的点，那么我们就不需要每次遍历所有的边了。

C++ 板子 Bellman-Ford & SPFA

/**
  链式前向星来存图
  int e[MAX_EDGE][2],hd[MAX_N],nxt[MAX_EDGE],top;
  void add(int u,int v,int w){
  	e[++top][0]=v;
  	e[top][1]=w;
  	nxt[top]=hd[u];
  	hd[u]=top;
  }
**/
// Bellman-Ford
while(true){
  	bool f=false;
    for(int i=1;iq;
q.push(start);
while(q.size()>0){
	int u=q.front();
    q.pop();
    vis[u]=0;
    
    for(int ev=hd[u];ev;ev=next[ev]){
        int v=e[ev][0],w=e[ev][1];
        if(dis[u]+w

Java 板子 SPFA

/*
	题目链接:https://ac.nowcoder.com/acm/problem/14369?&headNav=www
    spfa的最短路的写法
    链式前向星   
*/
import java.util.*;
public class Main {
    
    private static int e[][] = new int[202000][2];
    private static int nxt[] = new int[220000];
    private static int hd[] = new int [20020];
    private static int top = 0;
    
    private static int n,m;
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i=1;iq = new LinkedList();
        q.offer(1);
        while(!q.isEmpty()) {
            int u = q.peek();
            q.poll();
            vis[u] = 0;
            
            for(int i=hd[u];i>0;i=nxt[i]){
                int v=e[i][0],w=e[i][1];
                if(dis[u]+w 

算法模板之SPFA

标签：static   problem   链式前向星   队列   tar   遍历   math   pre   turn   

原文地址：https://www.cnblogs.com/backkom-buaa/p/13855313.html