单源最短路径

Shortest Paths

Which vertices?

  • Single source (单源最短路): from one vertex ss to every other vertex.
  • Source-sink: from one vertex ss to another tt.
  • All pairs: between all pairs of vertices.

在这里我们主要讨论单源最短路。代表单源最短路的数据结构是 shortest-paths tree (SPT, 最短路树)。We can represent the SPT with two vertex-indexed arrays:

  • distTo[v] is length of shortest path from ss to vv.
  • edgeTo[v] is last edge on shortest path from ss to vv.
java
public double distTo(int v) { return distTo[v]; }

public Iterable<DirectedEdge> pathTo(int v) {
    Stack<DirectedEdge> path = new Stack<DirectedEdge>();
    for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
        path.push(e);
    return path;
}

Shortest-paths Optimality Conditions

最短路的最优化条件,即所谓的三角形条件 (两边之和大于第三边)。Let GG be an edge-weighted digragh. Then distTo[] are the shortest path distances from ss iff:

  • distTo[s] = 0.
  • For each vertex v, distTo[v] is the length of some path from ss to vv.
  • For each edge e=v→we = v\to w, distTo[w] <= distTo[v] + e.weight().

根据最短路的最优化条件,我们介绍一个操作:edge relaxation. Relax edge e=v→we=v\to w 的意义是:

  • distTo[v] is length of shortest known path from ss to vv.
  • distTo[w] is length of shortest known path from ss to ww.
  • edgeTo[w] is last edge on shortest known path from ss to ww.
  • If e=v→we=v\to w gives shorter path to ww through vv, update both distTo[w] and edgeTo[w].

Generic Shortest-paths Algorithm

利用最短路的最优化条件,我们能够设计一个理论上的最短路算法,它一定能够计算出以 ss 为源点的 SPT。

  • Initialize distTo[s] = 0 and distTo[v] = inf for all other vertices.
  • Repeat until optimality conditions are satisfied.
    • Relax any edge.

我们能够证明该算法是可行的:每一次成功的 relaxation 都能使得某个 distTo[v] 减小;而由于最短路一定存在 (under certain assumption),distTo[v] 只会减小有限次。

(Efficient) Implementation Challenge. How to choose which edge to relax? 对这个问题的解答区分了不同的最短路算法。

  • Dijkstra's algorithm (nonnegative weights).
  • Topological sort algorithm (no directed cycles).
  • Bellman-Ford algorithm/SPFA (no negative cycles).

Dijkstra's Algorithm

Dijkstra 算法求 SPT 与 Prim 算法求 MST 的本质相同。Prim 算法维护逐渐增长的 MST TT,每次选择离 TT 最近的非 TT 点进行扩展。而 Dijkstra 算法维护逐渐增长的 SPT TT,每次选择离源点 ss 最近的非 TT 点进行扩展。

  • Consider vertices in increasing order of distance from ss, e.g., pick non-tree vertex with the lowest distTo[] value.
  • Add vertex to tree and relax all edges pointing from that vertex.

Dijkstra's algorithm computes a SPT in any edge-weighted diagraph with nonnegative weights.

下面将给出对于 Dijkstra 算法非正式的正确性证明 (这节课并没有 cover 该内容,是我自己想的!)

画图工具画的渣图...感觉有必要掌握一下这方面的技能

假设下一个将被扩展入 SPT TT 的节点为 vv,即在所有非 TT 节点中 distTo[v] 是最小的。而当前 edgeTo[v] 中记录的边为 u−vu-v。我们想要证明的是当前的 distTo[v] 与 edgeTo[v] 是全局最优的。

采用反证法,假设存在另一条由 ss 到 vv 的路径距离比 distTo[v] 更短。我们将该路径中第一个非 TT 节点标记为 xx,xx 与 vv 在 TT 的外部经过若干条边相连。

在 Dijkstra 算法中,我们选择下一个待扩展节点的规则是 distTo[] 值最小的节点;那么一定有 distTo[x] >= distTo[v]。而由于图中没有负权边,xx 到 vv 的距离 d>0d>0。那么该路径的长度 distTo[x] + d 一定大于 distTo[v],与我们的假设相悖。(如果有负权边,该不等式就不一定成立了!) 算法正确性得证。

Dijkstra 算法最多 relax 每条边一次。因此,binary heap 优化后的 Dijkstra 算法复杂度为 O(Elog⁡V)O(E\log{V}).

java
public class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;	// Eager Implementation of Dijkstra
    
    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        pq = new IndexMinPQ<Double>(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()) {
            int v = pq.delMin();
            for (DirectedEdge e : G.adj(v))	relax(e);
        }
    }
    
    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;
            if (pq.contains(w))  pq.decreaseKey(w, distTo[w]);
            else                 pq.insert     (w, distTo[w]);
        }
    }
}

Longest Paths in DAG

Suppose that an edge-weighted digraph has no directed cycles (weighted DAG), it is easier to find shortest paths than in a general digraph.

Topological sort algorithm computes SPT in any edge-weighted DAG in time proportional to E+VE+V. Note that edge weights can be negative!

对于 DAG,按照拓扑序 relax all edges 寻找最短路是一个很自然的思路。正确性比较 trivial,就不证明了。

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

对于 DAG 还存在最长路问题 (longest paths in edge-weighted DAGs);将其转化为最短路问题加以解决。

  • Nagate all weights.
  • Find shortest paths.
  • Negate weights in result.

该问题的一个经典应用是 parallel job scheduling 问题。对于一组有 durations 与 precedence constraints 的任务,我们可以将其抽象为最长路问题以找到最佳的安排方案,使得完成所有任务的总时间最少。

对于给出的任务集合,我们将其抽象为一个 weighted DAG。该方法称为 critical path method。

  • Create a source and sink vertices.
  • Two vertices (begin and end) for each job.
  • Three edges for each job.
    • Begin to end (weighted by duration).
    • Source to begin (0 weight).
    • End to sink (0 weight).
  • Critical path: one 0-weight edge for each precedence constraint.

对于任务 ii,从源点 source 到任务 ii 对应的结束点 end 最长路的长度即是该任务的最早完成时间;因此我们将从源点 source 到任务 ii 对应的起始点 begin 最长路的长度设为该任务的安排时间即可。

Bellman-Ford Algorithm

Dijkstra 算法是基于贪心的最短路算法;而 Bellman-Ford 算法是基于动态规划的最短路算法。Bellman-Ford 算法能够很好的 handle 带有负权边的图。

java
// After pass i, found shortest path containing at most i edges
for (int i = 0; i < G.V(); ++i)
    for (int v = 0; v < G.V(); ++v)
        for (DirectedEdge e : G.adj(v))
            relax(e);

Bellman-Ford 算法的思想很好理解:其对所有的边进行 V−1V-1 轮 relax。这是因为在一个含有 VV 个顶点的图中,任意两点间的最短路径最多包含 V−1V-1 条边。

在第 1 轮 relax 后,得到了源点最多经过 1 条边到达的顶点的最短路,在第 2 轮 relax 后,得到了源点最多经过 2 条边到达的顶点的最短路……在第 V−1V-1 轮 relax 后能够保证得到所有其他顶点的最短路。

Observation. If distTo[v] does not change during pass i, no need to relax any edge pointing from v in pass i+1.

根据这一 observation 能设计出队列优化的 Bellman-Ford 算法 — 即 SPFA (shortest-path fast algorithm) 算法。我们使用一个 queue 来记录 distTo[] 值发生更改的顶点,在下一轮中只 relax 这些顶点发射的边。

java
public SPFA(EdgeWeightedDigraph G, int s) {
	... // initialize
    for (int v = 0; v < G.V(); ++v)
        distTo[v] = Double.POSITIVE_INFINITY;
    distTo[s] = 0.0;
    que.push(s);
    vis[s] = true;	// vis[x] marks whether x is in queue
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (DirectedEdge e : G.adj(u))	{	// relax
            int v = e.from(), w = e.to();
    		if (distTo[w] > distTo[v] + e.weight()) {
        		distTo[w] = distTo[v] + e.weight();
        		edgeTo[w] = e;
        		if (!vis[w]) {
            		que.push(w);
                    vis[w] = true;
        		}
    		}
        }
    }
}

Bellman-Ford-based 算法的理论上的最坏时间复杂度为 Ω(EV)\Omega(EV);但实际应用中经过队列优化的 SPFA 算法效率是可以接受的。另外,Bellman-Ford-based 算法还能用于判负环 — 对存在负环的图,Bellman-Ford 算法将陷入死循环,不断更新负环内顶点的 distTo[] 与 edgeTo[] 值。

A negative cycle is a directed cycle whose sum of edge weights is negative. A SPT exists iff no negative cycles.

综上所述,最短路问题有三个困难性阶段:

  • Directed cycles make the problem harder. (Dijkstra -> Topological DP)
  • Negative weights make the problem harder. (Bellman-Ford/SPFA -> Dijkstra)
  • Negative cycles makes the problem intractable.
CC BY-NC-SA 4.0
正在加载评论…