基础图路径算法

单源最短路径算法

Dijsktra算法

核心思想是“贪心+松弛（relax）”：

• 每一步选出当前已知距离最小的未定点，把它“固定”（finalize），然后用它去松弛（更新）与其相连的邻居距离。
• 一旦一个点被取出并固定，其最短距离就是最终最短值（在非负权条件下成立）。

伪代码

初始化：对于所有 v，dist[v] = +∞；dist[s] = 0；prev[v] = -1
把 (dist[s], s) 放入优先队列 PQ

while PQ 不空:
    (d, u) = PQ.pop()   // 取出当前最小估计距离的节点
    if d != dist[u]: continue  // 跳过过期条目（如果实现不支持 decrease-key）
    // u 的距离已被“最终确定”
    for each 边 u -> v (权重 w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            prev[v] = u
            PQ.push( (dist[v], v) )

Java实现

import java.util.*;

public class Dijkstra {
    static final long INF = Long.MAX_VALUE / 4;

    static class Edge {
        int to;
        long w;
        Edge(int to, long w) { this.to = to; this.w = w; }
    }

    static class Result {
        long[] dist;
        int[] prev; // prev[v] = 前驱节点（-1 表示无）
        Result(long[] dist, int[] prev) { this.dist = dist; this.prev = prev; }
    }

    // n = 节点数（节点编号 0..n-1），graph 邻接表
    public static Result dijkstra(List<List<Edge>> graph, int source) {
        int n = graph.size();
        long[] dist = new long[n];
        int[] prev = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[source] = 0;

        // PQ 条目：[dist, node]
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.add(new long[]{0, source});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int) cur[1];
            if (d != dist[u]) continue; // 过期条目

            for (Edge e : graph.get(u)) {
                int v = e.to;
                long nd = d + e.w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    prev[v] = u;
                    pq.add(new long[]{nd, v});
                }
            }
        }
        return new Result(dist, prev);
    }

    // 重建从 source 到 target 的路径（若不可达返回空 list）
    public static List<Integer> reconstructPath(int target, int[] prev) {
        List<Integer> path = new ArrayList<>();
        for (int at = target; at != -1; at = prev[at]) path.add(at);
        Collections.reverse(path);
        if (path.size() == 0 || prev[path.get(0)] != -1 && path.get(0) != 0) {
            // this check is optional; usually we check dist[target] != INF before calling
        }
        return path;
    }

    // 简单示例用法
    public static void main(String[] args) {
        int n = 5; // 节点 0..4 对应 A..E
        List<List<Edge>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());

        // A=0,B=1,C=2,D=3,E=4
        g.get(0).add(new Edge(1,2));
        g.get(0).add(new Edge(2,5));
        g.get(1).add(new Edge(2,1));
        g.get(1).add(new Edge(3,2));
        g.get(2).add(new Edge(3,3));
        g.get(2).add(new Edge(4,1));
        g.get(3).add(new Edge(4,2));

        Result res = dijkstra(g, 0);
        System.out.println("dist: " + Arrays.toString(res.dist));
        System.out.println("path A->E: " + reconstructPath(4, res.prev));
    }
}

其中if (d != dist[u]) continue; // 过期条目处理了过期条目，由于队列中会加入未更新的边值，例如A->B的初始值为10，而A经过C到B的值为2，那么在第一次入队时，[10,B]的数据会进入队列，而当C固定后，经过C到B的数据[2,B]会入队，此时[10,B]为未更新的数据，应该被略过。

复杂度

最小堆中每次更新是log(V)每条边最多遍历一次，共计E次，共计Elog(V)

最小堆中每次取最小值并删除是log(V)，总共V个节点，共计Vlog(V)

时间复杂度为O((E+V)log(V))，对于稀疏图V=E为Vlog(V)，对于稠密图$E=V^2$ 为Elog(V)

空间复杂度为O(E+V)邻接表所占空间

特点

用于计算带非负权的有向图/无向图的单源最短路径。由于Dijsktra需要用到贪心算法，一个顶点的路径在确定后一定为从源点到该点的最小路径，如果存在负权，可能源点可以从之后的点通过负权获得一个更小的路径，将破坏贪心性质。

Bellman-Ford 算法

• 用一个 dist[] 数组维护从源 s 到各点的当前最短估计。
• 对 所有边 做“松弛（relax）”操作，重复 V-1 次（V = 节点数）。
  • 因为任意不重复的最短路径最多包含 V-1 条边，经过 V-1 次全边松弛，所有简单路径都会被考虑到。
• 做完 V-1 次后，再做一次全边扫描：
  • 若还能松弛说明存在 源可达的负权环（最短路不存在或可任意减小）。

松弛操作：若 dist[u] + w < dist[v]，则 dist[v] = dist[u] + w，并记录 prev[v] = u。

伪代码

initialize dist[v] = +INF for all v
dist[s] = 0
for i = 1 to V-1:
    for each edge (u, v, w):
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            prev[v] = u

// 检测负权回路
for each edge (u, v, w):
    if dist[u] != INF and dist[u] + w < dist[v]:
        report "存在负权回路"

Java实现

import java.util.*;

public class BellmanFord {
    static final long INF = Long.MAX_VALUE / 4;

    static class Edge {
        int u, v;
        long w;
        Edge(int u, int v, long w) { this.u = u; this.v = v; this.w = w; }
    }

    static class Result {
        long[] dist;
        int[] prev;
        boolean hasNegativeCycle;
        List<Integer> negativeCycle; // 若存在负环，按顺序返回环上的顶点
        Result(long[] dist, int[] prev, boolean hasNegativeCycle, List<Integer> negativeCycle) {
            this.dist = dist; this.prev = prev;
            this.hasNegativeCycle = hasNegativeCycle;
            this.negativeCycle = negativeCycle;
        }
    }

    // n = 节点数，节点编号 0..n-1，edges = 边列表，source = 源点
    public static Result bellmanFord(int n, List<Edge> edges, int source) {
        long[] dist = new long[n];
        int[] prev = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[source] = 0;

        boolean updated;
        for (int i = 0; i < n - 1; i++) {
            updated = false;
            for (Edge e : edges) {
                if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                    prev[e.v] = e.u;
                    updated = true;
                }
            }
            if (!updated) break; // 提前退出
        }

        // 检测负环并尝试重构
        int x = -1;
        for (Edge e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                x = e.v;
                break;
            }
        }
        if (x == -1) {
            return new Result(dist, prev, false, null);
        } else {
            // 把 x 移入负环内部：重复 n 次沿 prev 走
            int y = x;
            for (int i = 0; i < n; i++) {
                y = prev[y];
            }
            // 现在 y 在某个负环上，重构该环
            List<Integer> cycle = new ArrayList<>();
            int cur = y;
            do {
                cycle.add(cur);
                cur = prev[cur];
            } while (cur != y && cur != -1);
            Collections.reverse(cycle); // 可选：使环以循环方向输出
            return new Result(dist, prev, true, cycle);
        }
    }

    // 从 prev 重建从 source 到 target 的路径（若不可达返回空 list）
    public static List<Integer> reconstructPath(int target, int[] prev) {
        List<Integer> path = new ArrayList<>();
        if (target < 0) return path;
        for (int at = target; at != -1; at = prev[at]) path.add(at);
        Collections.reverse(path);
        return path;
    }

    // 示例用法
    public static void main(String[] args) {
        int n = 3; // A=0,B=1,C=2
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 4));   // A->B 4
        edges.add(new Edge(0, 2, 2));   // A->C 2
        edges.add(new Edge(2, 1, -3));  // C->B -3

        Result r = bellmanFord(n, edges, 0);
        System.out.println("hasNegativeCycle = " + r.hasNegativeCycle);
        System.out.println("dist = " + Arrays.toString(r.dist));
        if (r.hasNegativeCycle) {
            System.out.println("negative cycle nodes = " + r.negativeCycle);
        } else {
            System.out.println("path A->B = " + reconstructPath(1, r.prev));
        }
    }
}

特点

用于计算含负权的有向图/无向图的单源最短路径，但不允许负权回路。

复杂度

• 时间复杂度：O(V·E)（V = 顶点数，E = 边数）
• 空间复杂度：O(V + E)（边表 + dist / prev）

SPFA 算法

SPFA是Ford的优化版本，主要只在 某个顶点的距离被更新 时，才把它放进队列里，之后只松弛这个顶点的出边。这样避免了大量不必要的操作。

任意两点最短路径

Floyd算法

设有一个图 $G=(V,E)$，顶点数为 $n$。

用一个二维数组 dist[i][j] 表示从顶点i到顶点j的当前最短路径长度。

递推公式为
$$
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
$$
主要实现为三重循环

for k = 1..n
    for i = 1..n
        for j = 1..n
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

复杂度

时间复杂度：O(n³) （三重循环）。

空间复杂度：O(n²)。

适合 顶点数较小（几百级别） 的稠密图。

特点

简单易实现，适用于任意权图（可含负边，但不能有负环）。

最小生成树

Kruskal

Prim

并查集