单源最短路径
Shortest Paths
Which vertices?
- Single source (单源最短路): from one vertex
to every other vertex. - Source-sink: from one vertex
to another . - 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 fromto . edgeTo[v]is last edge on shortest path fromto .
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 distTo[] are the shortest path distances from
distTo[s] = 0.- For each vertex
v,distTo[v]is the length of some path fromto . - For each edge
, distTo[w] <= distTo[v] + e.weight().
根据最短路的最优化条件,我们介绍一个操作:edge relaxation. Relax edge
distTo[v]is length of shortest known path fromto . distTo[w]is length of shortest known path fromto . edgeTo[w]is last edge on shortest known path fromto . - If
gives shorter path to through , update both distTo[w]andedgeTo[w].
Generic Shortest-paths Algorithm
利用最短路的最优化条件,我们能够设计一个理论上的最短路算法,它一定能够计算出以
- Initialize
distTo[s] = 0anddistTo[v] = inffor 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
- Consider vertices in increasing order of distance from
, 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 distTo[v] 是最小的。而当前 edgeTo[v] 中记录的边为 distTo[v] 与 edgeTo[v] 是全局最优的。
采用反证法,假设存在另一条由 distTo[v] 更短。我们将该路径中第一个非
在 Dijkstra 算法中,我们选择下一个待扩展节点的规则是 distTo[] 值最小的节点;那么一定有 distTo[x] >= distTo[v]。而由于图中没有负权边,distTo[x] + d 一定大于 distTo[v],与我们的假设相悖。(如果有负权边,该不等式就不一定成立了!) 算法正确性得证。
Dijkstra 算法最多 relax 每条边一次。因此,binary heap 优化后的 Dijkstra 算法复杂度为
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
对于 DAG,按照拓扑序 relax all edges 寻找最短路是一个很自然的思路。正确性比较 trivial,就不证明了。
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.
对于任务
Bellman-Ford Algorithm
Dijkstra 算法是基于贪心的最短路算法;而 Bellman-Ford 算法是基于动态规划的最短路算法。Bellman-Ford 算法能够很好的 handle 带有负权边的图。
// 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 算法的思想很好理解:其对所有的边进行
在第 1 轮 relax 后,得到了源点最多经过 1 条边到达的顶点的最短路,在第 2 轮 relax 后,得到了源点最多经过 2 条边到达的顶点的最短路……在第
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 这些顶点发射的边。
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 算法的理论上的最坏时间复杂度为 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.

