最短路径

一、定义与背景

• 加权有向图：每条边具有权值（时间、距离等）的有向图。
• 最短路径：从起点 ( s ) 到终点 ( t ) 的路径中，总权值最小的路径。
• 单点最短路径问题：给定起点 ( s )，找到从 ( s ) 到所有可达顶点的最短路径。
• 应用：
• 地图：交叉路口（顶点）、公路（边）、距离/时间（权值）。
• 网络：路由器（顶点）、连接（边）。
• 任务调度：任务（顶点）、优先级限制（边）。
• 套汇：货币（顶点）、汇率（边）。

---

二、最短路径的性质

• 有向性：路径必须遵循边的方向。
• 权值灵活性：不一定代表距离，可为时间、成本等，不要求与距离成正比。
• 可达性：不可达顶点无最短路径，假设示例图强连通。
• 负权值：增加问题复杂性，需特殊处理。
• 简单性：最短路径通常不含环（忽略零权值环）。
• 唯一性：可能存在多条权值相等的最短路径，算法只需返回一条。
• 平行边与自环：选择权值最小的平行边，忽略自环。

最短路径树（SPT）

• 定义：以 ( s ) 为根，包含从 ( s ) 到所有可达顶点的最短路径的子图。
• 表示：父链接数组 ( edgeTo[] )，每条路径对应从 ( s ) 到顶点的唯一路径。

---

三、数据结构

1. 加权有向边（DirectedEdge）

public class DirectedEdge {
    private final int v, w;     // 起点和终点
    private final double weight; // 权值
    public DirectedEdge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; }
    public double weight() { return weight; }
    public int from() { return v; }
    public int to() { return w; }
}

2. 加权有向图（EdgeWeightedDigraph）

public class EdgeWeightedDigraph {
    private final int V;           // 顶点数
    private int E;                 // 边数
    private Bag<DirectedEdge>[] adj; // 邻接表
    public EdgeWeightedDigraph(int V) {
        this.V = V; this.E = 0;
        adj = (Bag<DirectedEdge>[]) new Bag[V];
        for (int v = 0; v < V; v++) adj[v] = new Bag<>();
    }
    public void addEdge(DirectedEdge e) { adj[e.from()].add(e); E++; }
    public Iterable<DirectedEdge> adj(int v) { return adj[v]; }
    public Iterable<DirectedEdge> edges() {
        Bag<DirectedEdge> b = new Bag<>();
        for (int v = 0; v < V; v++) for (DirectedEdge e : adj[v]) b.add(e);
        return b;
    }
}

3. 最短路径 API

public class SP {
    public SP(EdgeWeightedDigraph G, int s) {} // 构造最短路径树
    public double distTo(int v) {}              // 从 s 到 v 的距离
    public boolean hasPathTo(int v) {}          // 是否存在路径
    public Iterable<DirectedEdge> pathTo(int v) {} // 返回路径
}

4. 数据结构支持

• ( edgeTo[v] )：从 ( s ) 到 ( v ) 的路径上的最后一条边。
• ( distTo[v] )：从 ( s ) 到 ( v ) 的最短路径长度，初始为无穷大，不可达时保持无穷大。

5. 松弛操作（Relaxation）

• 边的松弛：
• 检查 ( s \to v \to w ) 是否比当前 ( s \to w ) 更短。
• 若 ( distTo[w] > distTo[v] + e.weight() )，更新 ( distTo[w] ) 和 ( edgeTo[w] )。

private void relax(DirectedEdge e) {
    int v = e.from(), w = e.to();
    if (distTo[w] > distTo[v] + e.weight()) {
        distTo[w] = distTo[v] + e.weight();
        edgeTo[w] = e;
    }
}

• 顶点的松弛：放松从 ( v ) 指出的所有边。

---

四、理论基础

1. 最优性条件（命题 P）

• ( distTo[w] \leq distTo[v] + e.weight() ) 对所有边成立时，( distTo[] ) 为最短路径长度。
• 证明：若存在有效边（违反条件），可构造更短路径，与最短性矛盾。

2. 通用算法（命题 Q）

• 初始化 ( distTo[s] = 0 )，其他为无穷大，反复放松边直到无有效边。
• 时间依赖放松顺序，正确性由最优性条件保证。

---

五、算法实现

1. Dijkstra 算法（非负权值）

• 思想：贪心策略，每次选择 ( distTo[] ) 最小的非树顶点放松。
• 实现：

public class DijkstraSP {
    private double[] distTo;
    private DirectedEdge[] edgeTo;
    private IndexMinPQ<Double> pq;
    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        pq = new IndexMinPQ<>(G.V());
        for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0; pq.insert(s, 0.0);
        while (!pq.isEmpty()) relax(G, pq.delMin());
    }
    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (pq.contains(w)) pq.changeKey(w, distTo[w]);
                else pq.insert(w, distTo[w]);
            }
        }
    }
}

• 性能：时间 ( O(E \log V) )，空间 ( O(V) )。
• 证明（命题 R）：非负权值保证 ( distTo[] ) 单调递减，优先队列确保最优性。

2. 无环图算法（AcyclicSP）

• 思想：按拓扑顺序放松顶点。
• 实现：

public class AcyclicSP {
    private double[] distTo;
    private DirectedEdge[] edgeTo;
    public AcyclicSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        Topological top = new Topological(G);
        for (int v : top.order()) relax(G, v);
    }
}

• 性能：时间 ( O(E + V) )，空间 ( O(V) )。
• 证明（命题 S）：拓扑顺序确保每条边放松一次即达最优。

3. Bellman-Ford 算法（支持负权值）

• 思想：基于队列，反复放松边，检测负权重环。
• 实现：

public class BellmanFordSP {
    private double[] distTo;
    private DirectedEdge[] edgeTo;
    private boolean[] onQ;
    private Queue<Integer> queue;
    private Iterable<DirectedEdge> cycle;
    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        onQ = new boolean[G.V()];
        queue = new Queue<>();
        for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0; queue.enqueue(s); onQ[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) {
            int v = queue.dequeue();
            onQ[v] = false;
            relax(G, v);
        }
    }
    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (!onQ[w]) { queue.enqueue(w); onQ[w] = true; }
            }
        }
    }
    private void findNegativeCycle() { /* 检测 edgeTo[] 中的环 */ }
}

• 性能：时间 ( O(EV) )（最坏情况），空间 ( O(V) )。
• 证明（命题 Y）：( V-1 ) 轮后无有效边则最优，否则存在负权重环。

---

六、应用

1. 无环图最长路径

• 问题：找总权值最大的路径。
• 方法：将权值取反，求最短路径。
• 性能：( O(E + V) )（命题 T）。

2. 并行任务调度

• 问题：在优先级限制下，最短时间内完成任务。
• 方法：构造无环图，求从起点到终点的最长路径（关键路径）。
• 性能：线性时间（命题 U）。

3. 套汇

• 问题：检测汇率中的盈利环。
• 方法：权值取 ( -\ln(w) )，用 Bellman-Ford 检测负权重环。
• 性能：( O(EV) )（命题 Z）。

---

七、性能比较

算法	限制条件	时间复杂度	空间复杂度	优势
Dijkstra	权值非负	( E \log V )	( V )	最坏情况性能优
AcyclicSP	无环	( E + V )	( V )	无环图最优
Bellman-Ford	无负权重环	( E + V \sim EV )	( V )	适用性广，支持负权值

---

八、展望

• 历史：Dijkstra (1959)、Bellman-Ford (20世纪50年代)。
• 优化：斐波那契堆改进 Dijkstra 至 ( E + V \log V )。
• 开放问题：负权值图的最坏情况线性时间算法尚未解决。

---

九、总结

• 核心：松弛操作与最优性条件。
• 算法：
• Dijkstra：贪心，适用于非负权值。
• AcyclicSP：拓扑排序，适用于无环图。
• Bellman-Ford：队列迭代，处理负权值。
• 适用性：根据图的性质选择算法，满足多样化需求。