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

leap_frog 發布于2019-08-14 17:16 / 1515人閱讀

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

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之前完成...）

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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 2019-08-14 17:13 評論0 收藏0
【程序員必會十大算法】之弗洛伊德算法

摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊學習資料迪杰斯特拉計算的是單源最...

JellyBool 2021-09-30 09:47 評論0 收藏0
算法（第4版） Chapter 4.1 無向圖

摘要：邊僅由兩個頂點連接，并且沒有方向的圖稱為無向圖。用分隔符當前為空格，也可以是分號等分隔。深度優先算法最簡搜索起點構造函數找到與起點連通的其他頂點。路徑構造函數接收一個頂點，計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

kamushin233 2019-08-14 17:14 評論0 收藏0
【程序員必會十大算法】之迪杰斯特拉算法

摘要：推薦資料推薦學習文章代碼不能設置為否則兩個相加會溢出導致出現負權創建頂點和邊創建圖頂點數得到邊的數目調用算法計算最短路徑推薦資料推薦學習文章代碼 public...

番茄西紅柿 2021-09-29 09:35 評論0 收藏2637

發表評論

登陸后可評論

0條評論

leap_frog

男|高級講師

我要關注我要私信

TA的文章

tensorflow圖像處理

閱讀 2943·2023-04-25 19:20
周鴻祎的“花房上市”執念

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

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

閱讀 2430·2021-09-02 15:11
在單頁應用中，如何優雅的監聽url的變化

閱讀 2015·2019-08-30 15:55
無單位數字line-height

閱讀 3610·2019-08-30 15:54
ES6 常用知識點總結

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

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

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

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

相關文章

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

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

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

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

發表評論

0條評論

leap_frog

男|高級講師

TA的文章

tensorflow圖像處理

周鴻祎的“花房上市”執念

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

python破解加密的rar，zip文件

在單頁應用中，如何優雅的監聽url的變化

無單位數字line-height

ES6 常用知識點總結

H5視頻直播原理

最新活動

資訊專欄INFORMATION COLUMN

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

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

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

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