Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 谢路云
Chapter 4 Section 4 最短路径
基本假设
图是强连通的
权重都为正
最短路径不一定是唯一的，我们只找出其中一条
可能存在平行边和自环（但我们会忽略自环）
数据结构
加权有向边API
有向边，所以新增方法from() 和 to()
DirectedEdge 代码
public class DirectedEdge {
private final int v; // edge source
private final int w; // edge target
private final double weight; // edge 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;
}
public String toString() {
return String.format("%d->%d %.2f", v, w, weight);
}
}加权有向图API
EdgeWeightedDigraph 代码
public class EdgeWeightedDigraph {
private final int V; // number of vertices
private int E; // number of edges
private Bag<DirectedEdge>[] adj; // adjacency lists
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<DirectedEdge>();
}
public EdgeWeightedDigraph(In in)// See Exercise 4.4.2.
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(DirectedEdge e) {
adj[e.from()].add(e);
E++;
}
public Iterable<Edge> adj(int v) {
return adj[v];
}
public Iterable<DirectedEdge> edges() {
Bag<DirectedEdge> bag = new Bag<DirectedEdge>();
for (int v = 0; v < V; v++)
for (DirectedEdge e : adj[v])
bag.add(e);
}
}最短路径API
边的松弛
两条路径
s --> w
s --> v , v -> w
比较哪一条路径更短，记录更短的那个边。
-
若 路径1 < 路径2，原路径 s --> w 已经最短，不更新。
边 v -> w 失效
-
若 路径1 > 路径2，新路径 s --> v , v -> w 更短，更新，放松成功
路径 s --> w 中 原指向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;//记录的是边，而不是点
}
}顶点的松弛
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;
}
}
}最短路径算法的理论基础
最优性条件
当且仅当 v -> w 的任意一条边e都满足 distTo[w] <= distTo[v] + e.weight()，它们是最短路径
通用最短路径算法
distTo[s]=0, distTo[v]=INFINITY(v≠s)
放松G中的任意边，直到不存在有效边为止
Dijkstra算法
算法步骤
非负权重
distTo[s]=0, distTo[v]=INFINITY(v≠s)
将distTo[]中 离顶点s最近的非树顶点 放松， 并加入到树中
重复2，直到所有顶点都在树中 或者 所有的非树顶点的distTo[]值均为无穷大
DijkstraSP 代码
-
复杂度
空间：V
时间：ElogV
public class DijkstraSP {
private DirectedEdge[] edgeTo; //记录路径
private double[] distTo; //记录权重
private IndexMinPQ<Double> pq; //优先队列
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; //顶点s到顶点s的距离当然为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)) { //遍历从v出发的每一条边
int w = e.to(); // v -> w
if (distTo[w] > distTo[v] + e.weight()) { //如果存在比目前s-->w更短的路径, s-->v,v->w
distTo[w] = distTo[v] + e.weight(); //更新距离/权重
edgeTo[w] = e; //更新路径
if (pq.contains(w)) // 队列中有这个点
pq.change(w, distTo[w]); //更新，更新队列中w的权重distTo[w]的值
else //队列中没有这个点
pq.insert(w, distTo[w]); //插入，把点w和权重distTo[w]作为整体插入到队列中
}
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v))
return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
path.push(e);
return path;
}
}-
DijkstraSP算法 VS Prim 算法
DijkstraSP算法 每次添加的都是离起点最近的非树顶点
Prim 算法 每次添加的是离树顶点最近的非树顶点
不需要数组marked[]，!marked[v] 等价于 distTo[v]无穷大
DijkstraSP算法忽略relax()方法中的distTo[v]部分的代码，即可得到Prim算法的即时版本
任意顶点对的最短路径
-
顶点s,v的最短路径怎么求？
用DijkstraSP算法，并在优先队列中删除顶点v后停止
任意顶点对的最短路径怎么求？
public class DijkstraAllPairsSP {
private DijkstraSP[] all;
DijkstraAllPairsSP(EdgeWeightedDigraph G)
{
all = new DijkstraSP[G.V()];
for (int v = 0; v < G.V(); v++)
all[v] = new DijkstraSP(G, v);
}
Iterable<Edge> path(int s, int t) {
return all[s].pathTo(t);
}
double dist(int s, int t) {
return all[s].distTo(t);
}
}无环加权有向图的最短路径算法
更快更简单更好的算法
线性时间
能够处理负权重
能够解决其他相关问题，eg 距离最长
算法步骤
distTo[s]=0, distTo[v]=INFINITY(v≠s)
按照 拓扑顺序 放松所有顶点
AcyclicSP 代码
复杂度
时间： E+V
空间： V
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 top = new Topological(G); //只增加了这一个！！！就把性能提高了！！！
for (int v : top.order())
relax(G, v);
}
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) { //遍历从v出发的每一条边
int w = e.to(); // v -> w
if (distTo[w] > distTo[v] + e.weight()) { //如果存在比目前s-->w更短的路径, s-->v,v->w
distTo[w] = distTo[v] + e.weight(); //更新距离/权重
edgeTo[w] = e; //更新路径
}
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] > Double.NEGATIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}最长路径
做一个副本，将无环加权有向图的权重取反即可。（相关操作就是判断的不等号符号改反，初始值设为负无穷）
副本的最短路径即为原图的最长路径。
AcyclicLP 代码
public class AcyclicLP {
private double[] distTo; // distTo[v] = distance of longest s->v path
private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on longest s->v path
public AcyclicLP(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.NEGATIVE_INFINITY;
distTo[s] = 0.0;
// relax vertices in toplogical order
Topological topological = new Topological(G);
if (!topological.hasOrder())
throw new IllegalArgumentException("Digraph is not acyclic.");
for (int v : topological.order()) {
for (DirectedEdge e : G.adj(v))
relax(e);
}
}
// relax edge e, but update if you find a *longer* path
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;
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] > Double.NEGATIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}平行任务调度
为每一个点添加一个点作为任务的结束点，并从结束点出发指向充分条件。
添加一个起点，一个终点。
输入文本格式（解读，共10个任务，任务0耗时41秒，需在1,7,9之前完成...）
10
41.0 1 7 9
51.0 2
50.0
36.0
38.0
45.0
21.0 3 8
32.0 3 8
32.0 2
29.0 4 6public class CPM {
public static void main(String[] args) {
int N = StdIn.readInt();
StdIn.readLine();
EdgeWeightedDigraph G;
G = new EdgeWeightedDigraph(2 * N + 2);
int s = 2 * N, t = 2 * N + 1; //s为起点，t为终点
for (int i = 0; i < N; i++) {
String[] a = StdIn.readLine().split("\\s+");
double duration = Double.parseDouble(a[0]);
G.addEdge(new DirectedEdge(i, i + N, duration)); //添加一个点作为任务的结束点
G.addEdge(new DirectedEdge(s, i, 0.0)); //和起点相连
G.addEdge(new DirectedEdge(i + N, t, 0.0));//任务的结束点和终点相连
for (int j = 1; j < a.length; j++) {
int successor = Integer.parseInt(a[j]);//读取充分条件
G.addEdge(new DirectedEdge(i + N, successor, 0.0));//任务的结束点和充分条件相连
}
}
AcyclicLP lp = new AcyclicLP(G, s); //最长路径
StdOut.println("Start times:");
for (int i = 0; i < N; i++)
StdOut.printf("%4d: %5.1f\n", i, lp.distTo(i));
StdOut.printf("Finish time: %5.1f\n", lp.distTo(t));
}
}相对最后期限下的并行任务调度
再加一个限制：deadline，也就是截止时间限制（相对某个任务的截止时间，比如2号任务必须在4号任务启动的12个单位时间内开始）。
方法是同上面一样构造图，同时会添加负权重边，再将所有边取反，然后求最短路径
最短路径存在则可行（没有负权重环就是可行的调度）。
一般有向加权图的最短路径问题
考虑有环也可能负边的最短路径问题
负权重环会导致绕圈现象，因此负权重环存在求不出最短路径
Bellman-ford算法
以任意顺序放松所有边
重复V轮
-
复杂度
时间： EV
空间： V
public BellmanFord_BruceAlg() {
for (int pass = 0; pass < G.V(); pass++) //第i轮
for (v = 0; v < G.V(); v++) //在每一轮中放松所有边
for (DirectedEdge e : G.adj(v))
relax(e);
}基于队列的Bellman-ford算法
在后几轮中，很多边的放松都不会成功
只有上一轮distTo[]的值发生改变的顶点指出的边，才能改变其他顶点的distTo[]值
用队列记录这样的顶点
public class BellmanFordSP {
private double[] distTo; // length of path to v
private DirectedEdge[] edgeTo; // last edge on path to v
private boolean[] onQ; // Is this vertex on the queue?
private Queue<Integer> queue; // vertices being relaxed
private int cost; // number of calls to relax()
private Iterable<DirectedEdge> cycle; // negative cycle in edgeTo[]?
public BellmanFordSP(EdgeWeightedDigraph G, int s) {
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
onQ = new boolean[G.V()];
queue = new Queue<Integer>();
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() && !this.hasNegativeCycle()) {
int v = queue.dequeue();
onQ[v] = false;
relax(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]){
q.enqueue(w);
onQ[w] = true;
}
}
if (cost++ % G.V() == 0) //居然在这里判断是否循环了V轮。。。
findNegativeCycle();
}
}
public double distTo(int v) // standard client query methods
public boolean hasPathTo(int v) // for SPT implementatations
public Iterable<Edge> pathTo(int v) // (See page 649.)
private void findNegativeCycle() {
int V = edgeTo.length;
EdgeWeightedDigraph spt;
spt = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++)
if (edgeTo[v] != null)
spt.addEdge(edgeTo[v]);
EdgeWeightedCycleFinder cf;
cf = new EdgeWeightedCycleFinder(spt);
cycle = cf.cycle();
}
public boolean hasNegativeCycle() {
return cycle != null;
}
public Iterable<Edge> negativeCycle() {
return cycle;
}
}
