资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/算法（第4版） Chapter 4.4 最短路径

算法（第4版） Chapter 4.4 最短路径

leap_frog / 1406人阅读

摘要：相关操作就是判断的不等号符号改反，初始值设为负无穷副本的最短路径即为原图的最长路径。方法是同上面一样构造图，同时会添加负权重边，再将所有边取反，然后求最短路径最短路径存在则可行没有负权重环就是可行的调度。

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[] adj; // adjacency lists

    public EdgeWeightedDigraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag();
    }

    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 adj(int v) {
        return adj[v];
    }

    public Iterable edges() {
        Bag bag = new Bag();
        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 pq; //优先队列

    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        pq = new IndexMinPQ(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 pathTo(int v) {
        if (!hasPathTo(v))
            return null;
        Stack path = new Stack();
        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 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 pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack path = new Stack();
        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 pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack path = new Stack();
        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 6
public 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
", i, lp.distTo(i));
        StdOut.printf("Finish time: %5.1f
", 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 queue; // vertices being relaxed
    private int cost; // number of calls to relax()
    private Iterable 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();
        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 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 negativeCycle() {
        return cycle;
    }
}
混合云 私有云 最短路径算法程序 最短路径算法大全 最短路径算法合集 最短路径算法简述

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66524.html

相关文章

  • 算法（第4版） Chapter 4 练习题 答案

    摘要：离心率计算题目释义计算点的离心率，图的直径，半径，中心计算图的围长定义点的离心率图中任意一点，的离心率是图中其他点到的所有最短路径中最大值。图的中心图中离心率长度等于半径的点。改动离心率计算，在遍历中增加的赋值即可。 离心率计算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...

    13651657101 评论0 收藏0

  • 【程序员必会十大算法】之弗洛伊德算法

    摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边 学习资料 迪杰斯特拉计算的是单源最...

    JellyBool 评论0 收藏0

  • 算法（第4版） Chapter 4.1 无向图

    摘要：边仅由两个顶点连接，并且没有方向的图称为无向图。用分隔符当前为空格，也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点，计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

    kamushin233 评论0 收藏0

  • 【程序员必会十大算法】之迪杰斯特拉算法

    摘要：推荐资料推荐学习文章代码不能设置为否则两个相加会溢出导致出现负权创建顶点和边创建图顶点数得到边的数目调用算法计算最短路径 推荐资料 推荐学习文章 代码 public...

    番茄西红柿 评论0 收藏2637

发表评论

登陆后可评论

0条评论

leap_frog

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<