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

leap_frog 發(fā)布于2019-08-14 17:16 / 1525人閱讀

摘要：相關(guān)操作就是判斷的不等號符號改反，初始值設(shè)為負無窮副本的最短路徑即為原圖的最長路徑。方法是同上面一樣構(gòu)造圖，同時會添加負權(quán)重邊，再將所有邊取反，然后求最短路徑最短路徑存在則可行沒有負權(quán)重環(huán)就是可行的調(diào)度。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 4 Section 4 最短路徑

基本假設(shè)

圖是強連通的

權(quán)重都為正

最短路徑不一定是唯一的，我們只找出其中一條

可能存在平行邊和自環(huán)（但我們會忽略自環(huán)）

數(shù)據(jù)結(jié)構(gòu) 加權(quán)有向邊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);
    }
}

加權(quán)有向圖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 已經(jīng)最短，不更新。

邊 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;
        }
    }
}

最短路徑算法的理論基礎(chǔ) 最優(yōu)性條件

當且僅當 v -> w 的任意一條邊e都滿足 distTo[w] <= distTo[v] + e.weight()，它們是最短路徑

通用最短路徑算法

distTo[s]=0, distTo[v]=INFINITY(v≠s)

放松G中的任意邊，直到不存在有效邊為止

Dijkstra算法 算法步驟

非負權(quán)重

distTo[s]=0, distTo[v]=INFINITY(v≠s)

將distTo[]中離頂點s最近的非樹頂點放松，并加入到樹中

重復(fù)2，直到所有頂點都在樹中 或者所有的非樹頂點的distTo[]值均為無窮大

DijkstraSP 代碼

復(fù)雜度

空間：V

時間：ElogV

public class DijkstraSP {
    private DirectedEdge[] edgeTo; //記錄路徑
    private double[] distTo; //記錄權(quán)重
    private IndexMinPQ pq; //優(yōu)先隊列

    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出發(fā)的每一條邊
            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();  //更新距離/權(quán)重
                edgeTo[w] = e; //更新路徑
                if (pq.contains(w)) // 隊列中有這個點
                    pq.change(w, distTo[w]); //更新，更新隊列中w的權(quán)重distTo[w]的值
                else //隊列中沒有這個點
                    pq.insert(w, distTo[w]); //插入，把點w和權(quán)重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 算法每次添加的是離樹頂點最近的非樹頂點

不需要數(shù)組marked[]，!marked[v] 等價于 distTo[v]無窮大

DijkstraSP算法忽略relax()方法中的distTo[v]部分的代碼，即可得到Prim算法的即時版本

任意頂點對的最短路徑

頂點s,v的最短路徑怎么求？

用DijkstraSP算法，并在優(yōu)先隊列中刪除頂點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);
    }
}

無環(huán)加權(quán)有向圖的最短路徑算法

更快更簡單更好的算法

線性時間

能夠處理負權(quán)重

能夠解決其他相關(guān)問題，eg 距離最長

算法步驟

distTo[s]=0, distTo[v]=INFINITY(v≠s)

按照 拓撲順序 放松所有頂點

AcyclicSP 代碼

復(fù)雜度

時間： 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出發(fā)的每一條邊
            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();  //更新距離/權(quán)重
                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;
    }
}

最長路徑

做一個副本，將無環(huán)加權(quán)有向圖的權(quán)重取反即可。（相關(guān)操作就是判斷的不等號符號改反，初始值設(shè)為負無窮）
副本的最短路徑即為原圖的最長路徑。

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;
    }
}

平行任務(wù)調(diào)度

為每一個點添加一個點作為任務(wù)的結(jié)束點，并從結(jié)束點出發(fā)指向充分條件。

添加一個起點，一個終點。

輸入文本格式（解讀，共10個任務(wù)，任務(wù)0耗時41秒，需在1,7,9之前完成...）

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)); //添加一個點作為任務(wù)的結(jié)束點
            G.addEdge(new DirectedEdge(s, i, 0.0)); //和起點相連
            G.addEdge(new DirectedEdge(i + N, t, 0.0));//任務(wù)的結(jié)束點和終點相連
            for (int j = 1; j < a.length; j++) {
                int successor = Integer.parseInt(a[j]);//讀取充分條件
                G.addEdge(new DirectedEdge(i + N, successor, 0.0));//任務(wù)的結(jié)束點和充分條件相連
            }
        }
        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));
    }
}

相對最后期限下的并行任務(wù)調(diào)度

再加一個限制：deadline，也就是截止時間限制（相對某個任務(wù)的截止時間，比如2號任務(wù)必須在4號任務(wù)啟動的12個單位時間內(nèi)開始）。

方法是同上面一樣構(gòu)造圖，同時會添加負權(quán)重邊，再將所有邊取反，然后求最短路徑

最短路徑存在則可行（沒有負權(quán)重環(huán)就是可行的調(diào)度）。

一般有向加權(quán)圖的最短路徑問題

考慮有環(huán)也可能負邊的最短路徑問題

負權(quán)重環(huán)會導(dǎo)致繞圈現(xiàn)象，因此負權(quán)重環(huán)存在求不出最短路徑

Bellman-ford算法

以任意順序放松所有邊

重復(fù)V輪

復(fù)雜度

時間： 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[]的值發(fā)生改變的頂點指出的邊，才能改變其他頂點的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) //居然在這里判斷是否循環(huán)了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;
    }
}

云服務(wù)器 GPU云服務(wù)器最短路徑算法程序最短路徑算法大全最短路徑算法合集最短路徑算法簡述

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66524.html

發(fā)表評論

登陸后可評論

0條評論

leap_frog

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow圖像處理

閱讀 2952·2023-04-25 19:20
周鴻祎的“花房上市”執(zhí)念

閱讀 814·2021-11-24 09:38
一起用python做個炫酷音樂播放器，想聽啥隨便搜！【V2.0升級版，含源碼及打包exe】

閱讀 2066·2021-09-26 09:55
python破解加密的rar，zip文件

閱讀 2443·2021-09-02 15:11
在單頁應(yīng)用中，如何優(yōu)雅的監(jiān)聽url的變化

閱讀 2075·2019-08-30 15:55
無單位數(shù)字line-height

閱讀 3621·2019-08-30 15:54
ES6 常用知識點總結(jié)

閱讀 3159·2019-08-30 14:03
H5視頻直播原理

閱讀 2972·2019-08-29 17:11

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

**算法（第4版） Chapter 4 練習題答案**

【程序員必會十大算法】之弗洛伊德算法

**算法（第4版） Chapter 4.1 無向圖**

【程序員必會十大算法】之迪杰斯特拉算法

發(fā)表評論

0條評論

leap_frog

男|高級講師

TA的文章

tensorflow圖像處理

周鴻祎的“花房上市”執(zhí)念

一起用python做個炫酷音樂播放器，想聽啥隨便搜！【V2.0升級版，含源碼及打包exe】

python破解加密的rar，zip文件

在單頁應(yīng)用中，如何優(yōu)雅的監(jiān)聽url的變化

無單位數(shù)字line-height

ES6 常用知識點總結(jié)

H5視頻直播原理

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！