SPFA算法

概念

SPFA算法是一种基于Bellman-Ford算法的改进版本，它用于计算图中各节点到源节点的最短路径。与Bellman-Ford算法不同的是，SPFA算法使用了队列来优化计算，从而在某些情况下加速了计算过程。

SPFA算法的基本思想是从源节点开始，将源节点放入队列中，然后不断从队列中取出节点，考察它的邻接节点，以更新到这些邻接节点的最短距离。如果某个节点的最短距离被更新，且该节点不在队列中，那么将该节点加入队列中，以便后续继续考察。

复杂度是O(V*E)

步骤

初始化：将源节点的最短距离设置为0，其他节点的最短距离设置为无穷大（或一个足够大的值），并将源节点加入队列中。
迭代处理队列中的节点：
- 从队列中取出一个节点。
- 考察该节点的所有邻接节点，如果通过当前节点到达邻接节点的路径比已知的最短路径更短，则更新邻接节点的最短路径。
- 如果邻接节点的最短路径被更新，且邻接节点不在队列中，将它加入队列中。
重复步骤2，直到队列为空。
最短路径计算完成后，可以从源节点到任意目标节点的最短路径已知。

原则

只让当前点能到达的点入队
如果一个点已经在队列里，便不重复入队
如果一条边未被更新，那么它的终点不入队

原理

假设，我们的目标是松弛完S->P1->P2->...D，所以我们先把S能到达的所有点加入队列，
P1则一定在队列中。然后对于队列中每个点，我们都把它能到达的所有点加入队列（不重复入队），
这时我们又可以保证P2一定在队列中。另外注意到，假如Pi->Pi+1是目标最短路上的一段，
那么在松弛这条边时它一定是会被更新的，所以如果一条边未被更新，它的终点就不入队。

模板

class SPFA {
    final int INF = Integer.MAX_VALUE;
    // n->num, s->start, dists->distances, counts->记录顶点入队次数，用于负圈检测
    int n, s, dists[], counts[];  
    List<int[]> g[];  // 邻接表建图(g[u]->[v,w])
    public SPFA(int n, int s, List<int[]> g[]) {
        this.n = n; this.s = s; this.g = g;
        this.dists = new int[n]; this.counts = new int[n];
    }
    public boolean bfs() {
        Arrays.fill(dists, INF);
        dists[s - 1] = 0;
        Deque<Integer> q = new LinkedList<>();
        q.add(s - 1);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int vw[] : g[u]) {
                int v = vw[0], w = vw[1];
                if (dists[u] + w < dists[v]) {  // 松弛u的邻接顶点
                    dists[v] = dists[u] + w;
                    if (!q.contains(v)) {  // 入队的前提是此时v不在q中，否则程序虽正确，但复杂度将不再是O(|V||E|)
                        q.add(v);
                        if (counts[v] > n - 1) {  // 负圈检测
                            System.out.println("Negative Cycle Found!");
                            return false;
                        } else {
                            counts[v] += 1;
                        }
                    }
                }
            }
        }
        return true;
    }
}

algorithm-SPFA

SPFA算法

概念

步骤

原则

原理

模板

题解