4.4 最短路径

4.4 最短路径

模型:加权有向图

问题:单点最短路径:给定加权有向图和s,求”s到给定v是否存在有向路径,若有,找出权重最小的”

4.4.1最短路径性质

• 并非所有顶点都可达
• 最短路径不一定唯一
• 最短路径树:SPT,包含s到所以可达顶点的最短路径

4.4.2 加权有向图

加权有向边API:public class DirectedEdge

public class DirectedEdge {
    private final int v;//起
    private final int 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; }
    public String toStirng(){
        return String.format("%d->%d %.2f", v, w, weight);
    }
}

加权有向图API:public class EdgeWeightedDigraph

import edu.princeton.cs.algs4.In;
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 EdgeWeightedDigraph(In in){
        this(in.readInt());
        int E = in.readInt();
        for (int i = 0; i < E; i++){
            int v = in.readInt();
            int w = in.readInt();
            double weight = in.readDouble();
            DirectedEdge e = new DirectedEdge(v,w,weight);
            addEdge(e);
        }
    }
    public void addEdge(DirectedEdge e){
        adj[e.from()].add(e);
    }
    public int V(){ return V;}
    public int E(){ return E;}
    public Iterable<DirectedEdge> adj(int v){ return adj[v];}
    public Iterable<DirectedEdge> edges(){
        Bag<DirectedEdge> bag = new Bag<>();
        for (int v = 0; v < V; v++)
            for (DirectedEdge e: adj[v])
                bag.add(e);
            return bag;
    }
}

最短路径API:public class SP

• 数据结构选择
  • SPT中的边:顶点索引的DirectedEdge数组edgeTo[]
  • 到起点距离: distTo[]

松弛(relaxation)

• 边的松弛:放松v->w,即检查s->w是否经s->v->w:若distTo[v]+(v->w)e.weight()w失效,更新edgeTo[w]为由s->w为v->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;
        }
    }
}

SP中的查询方法

private double distTo(int v){ return distTo[v]};//s->v的距离
public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY;}
public Iterable<DirectedEdge> pathTo(int v){
    Stack<DirectedEdge> stack = new Stack<>();
    for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
        stack.push(e);
    return stack;//后根入栈
}

SP算法理论基础

• 最短路径的最优性条件

  • 命题:当且仅当从v到w的任意一条边满足distTo[w]<=distTo[v]+e.weight()时(即不存在有效边时),distTo[]中都为SP的长度

    证明:书P420

• 通用最短路径算法:

  1. 将distTo[s]初始化为0,其他都初始化为∞
  2. 放松G中任意边,知道不存在有效边
  • 对任意s可达的w,操作过后,distTo[w]即为s到w的最短路径长度,且edgeTo[w]为路径上最后一条边
  • 通用算法没有指定放松顺序

4.4.4 Dijkstra算法(算法4.9)

4.4.5 无环加权有向图的最短路径算法(算法4.10)

4.4.6 一般加权有向图的最短路径问题(算法4.11)

4.4.7 总结

• 不同最短路径算法总结 | 算法 | 局限 | 时间(最坏) | 最好 | 空间 | 优势 | | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | Dijkstra即时版本 | 边权必须为正 | ElogV | ElogV | V | 最坏时保证性能 | | 利用Topo排序 | 只适合无环加权有向图 | E+V | E+V | V | 无环图最优算法 | | 基于队列Bellman-Ford | 不能存在负权重环 | E+V | VE | V | 应用广泛 |