每日算法 — 使用java实现青蛙过河：SPFA最短路径与负权边松弛策略

引言

青蛙过河是一个经典的图论问题变体：河中有若干石头，青蛙需要从起点跳到终点，每次跳跃有对应的体力消耗，某些石头之间可能存在”顺流”带来的负消耗。本文用Java实现SPFA（Shortest Path Faster Algorithm）算法，解决带负权边的最短路径问题，并分析其在动态图场景下的应用。

问题建模

将每块石头视为图中的一个节点，青蛙能跳跃的石头对构成有向边，边的权重为跳跃消耗的体力（逆流为正，顺流为负）。问题转化为：从起点到终点的最短路径，允许负权边但不含负权环。

import java.util.*;

/**
 * 青蛙过河问题模型
 * 使用SPFA算法求解带负权边的单源最短路径
 */
public class FrogRiverSPFA {

    // 图的邻接表表示：节点 -> (邻居, 权重)
    private final List<List<Edge>> graph;
    private final int n; // 节点数

    public FrogRiverSPFA(int n) {
        this.n = n;
        this.graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
    }

    /**
     * 添加有向边
     * @param from 起点（石头编号）
     * @param to 终点（石头编号）
     * @param weight 权重（体力消耗，可为负）
     */
    public void addEdge(int from, int to, int weight) {
        graph.get(from).add(new Edge(to, weight));
    }

    /**
     * SPFA核心算法
     * 使用队列优化Bellman-Ford，平均时间复杂度O(kE)，k通常很小
     * @param start 起点编号
     * @return 到各点的最短距离数组
     */
    public int[] spfa(int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // 记录节点入队次数，用于检测负权环
        int[] count = new int[n];
        boolean[] inQueue = new boolean[n];

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        inQueue[start] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            // 松弛操作：遍历所有出边
            for (Edge e : graph.get(u)) {
                int v = e.to;
                int w = e.weight;

                // 经典松弛条件：若经u到v更短，则更新
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;

                    // 只有当v不在队列中时才入队，避免冗余
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                        count[v]++;

                        // 负权环检测：若某节点入队超过n次，存在负权环
                        if (count[v] > n) {
                            throw new IllegalStateException(
                                "检测到负权环，青蛙可能无限获利！"
                            );
                        }
                    }
                }
            }
        }

        return dist;
    }

    /**
     * 获取最短路径的具体路线（通过前驱节点回溯）
     */
    public List<Integer> getShortestPath(int start, int end) {
        int[] dist = new int[n];
        int[] prev = new int[n]; // 前驱节点记录
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[start] = 0;

        boolean[] inQueue = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        inQueue[start] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (Edge e : graph.get(u)) {
                int v = e.to;
                int w = e.weight;

                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    prev[v] = u; // 记录前驱，用于路径重建

                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }

        // 回溯构建路径
        List<Integer> path = new ArrayList<>();
        if (dist[end] == Integer.MAX_VALUE) return path; // 不可达

        for (int at = end; at != -1; at = prev[at]) {
            path.add(at);
        }
        Collections.reverse(path);
        return path;
    }

    private static class Edge {
        final int to;
        final int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    // 演示主程序
    public static void main(String[] args) {
        // 场景：5块石头编号0~4，0为起点，4为终点
        FrogRiverSPFA solver = new FrogRiverSPFA(5);

        // 添加跳跃边（含负权边，表示顺流助力）
        solver.addEdge(0, 1, 3);   // 0->1 消耗3
        solver.addEdge(0, 2, 2);   // 0->2 消耗2
        solver.addEdge(1, 2, -1);  // 1->2 顺流，消耗-1（体力回复）
        solver.addEdge(1, 3, 4);   // 1->3 消耗4
        solver.addEdge(2, 3, 2);   // 2->3 消耗2
        solver.addEdge(2, 4, 5);   // 2->4 消耗5
        solver.addEdge(3, 4, -2);  // 3->4 顺流大助力，消耗-2

        int[] dist = solver.spfa(0);
        System.out.println("从起点0到各石头的最小体力消耗:");
        for (int i = 0; i < dist.length; i++) {
            System.out.printf("  到石头%d: %d%n", i, dist[i]);
        }

        List<Integer> path = solver.getShortestPath(0, 4);
        System.out.println("\n最优过河路线: " + path);
        System.out.println("总消耗: " + dist[4]);
    }
}

SPFA的SLF优化

对于稠密图或特殊构造的数据，SPFA可能退化。引入SLF（Small Label First）优化：若待入队节点的距离小于队首，则插入队首而非队尾。

/**
 * SLF优化的SPFA，使用双端队列
 */
public int[] spfaSLF(int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    boolean[] inQueue = new boolean[n];
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerFirst(start);
    inQueue[start] = true;

    while (!deque.isEmpty()) {
        int u = deque.pollFirst();
        inQueue[u] = false;

        for (Edge e : graph.get(u)) {
            int v = e.to;
            int w = e.weight;

            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                if (!inQueue[v]) {
                    // SLF优化：小距离放队首，大距离放队尾
                    if (!deque.isEmpty() && dist[v] < dist[deque.peekFirst()]) {
                        deque.offerFirst(v);
                    } else {
                        deque.offerLast(v);
                    }
                    inQueue[v] = true;
                }
            }
        }
    }

    return dist;
}

复杂度分析

总结

SPFA算法通过队列优化Bellman-Ford的松弛过程，在稀疏图上效率极高。本文将其应用于青蛙过河场景，正确处理了负权边（顺流助力），并通过入队次数检测负权环。SLF双端队列优化进一步提升了实际运行效率。