算法（第四版）第四章圖4.4

最短路徑

即找到從一個頂點到達另一個頂點的成本最小的路徑筋量。

單點最短路徑植袍。給定一幅加權(quán)有向圖和一個起點s筋遭，回答“從s到給定的目的頂點v是否存在一條有向路徑打颤？如果有，找出最短（總權(quán)重最欣焯稀）的那條路徑编饺。”

我們計劃在本節(jié)討論下列問題：

  • 加權(quán)有向圖的API和實現(xiàn)以及單點最短路徑的API
  • 解決邊的權(quán)重非負的最短路徑問題的經(jīng)典Dijkstra算法响驴；
  • 在無環(huán)加權(quán)有向圖中解決該問題的一種快速算法透且，邊的權(quán)重甚至可以是負值
  • 適用于一般情況的經(jīng)典Bellman-Ford算法，其中圖可以含有環(huán)，邊的權(quán)重也可以是負值秽誊。

4.4.2 加權(quán)有向圖的數(shù)據(jù)結(jié)構(gòu)

image-20200821095938425.png

+++

加權(quán)有向邊的數(shù)據(jù)類型

/**
 * 加權(quán)有向邊的數(shù)據(jù)類型
 */
public class DirectedEdge {
    private final int v;    //邊的起點
    private final int w;    //邊的終點
    private final double weight;    //邊的權(quán)重

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

    @Override
    public String toString() {
        return String.format("%d->%d %.2f", v, w, weight);
    }
}

DirectedEdge類的實現(xiàn)比4.3節(jié)無向邊的數(shù)據(jù)類型Edge類更簡單鲸沮，因為邊的兩個端點是有區(qū)別的。用例可以使用慣用代碼

int v=e.to(),w=e.from();來訪問DirectedEdge的兩個端點锅论。

++++

加權(quán)有向圖的數(shù)據(jù)類型

++++

/**
 * 加權(quán)有向圖
 */
public class EdgeWeightedDigraph {
    private final int V;    //頂點總數(shù)
    private int E;          //邊總數(shù)
    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 int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(DirectedEdge e) {
        adj[e.from()].add(e);
        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;
    }
}

它維護了一個由頂點索引的Bag對象的數(shù)組讼溺，Bag對象的內(nèi)容為DirectedEdge對象。與Digraph類一樣最易，每條邊的鄰接表中只會出現(xiàn)一次：如果一條邊從v指向w怒坯，那么它只會出現(xiàn)在v的鄰接鏈表中。這個類可以處理自環(huán)和平行邊藻懒。

下圖是用EdgeWeightedDigraph表示左側(cè)的加權(quán)有向圖構(gòu)造出的數(shù)據(jù)結(jié)構(gòu)剔猿。

image-20200821100801988.png

最短路徑的API

image-20200821100859250.png

4.4.2.3 最短路徑的數(shù)據(jù)結(jié)構(gòu)

  • 最短路徑樹中的邊。和深度優(yōu)先搜索束析、廣度優(yōu)先搜索和Prim算法一樣艳馒，使用一個由頂點索引的DirectedEdge對象的父鏈接數(shù)組edgeTo[]，其中edgeTo[v]的值為樹中連接v和它的父節(jié)點的邊（也是從s到v的最短路徑上的最后一條邊）员寇。
  • 到達起點的距離弄慰。我們需要一個由頂點索引的數(shù)組distTo[],其中distTo[v]為從s到v的已知最短路徑的長度。

我們約定蝶锋，edgesTo[s]的值為null陆爽，distTo[s]的值為0，同時約定扳缕，從起點到不可達的頂點的距離均為Double.POSITIVE_INFINITY慌闭。

4.4.2.4 邊的松弛

我們的最短路徑API的實現(xiàn)基于一個被稱為松弛的簡單操作.一開始我們只知道圖的邊和它們的權(quán)重,distTo[]中只有起點所對應(yīng)的元素值為0，其余元素的值均被初始化為Double.POSITIVE_INFINITY躯舔。隨著算法的執(zhí)行驴剔，它將起點到其他頂點的最短路徑信息存入了edgeTo[]和distTo[]數(shù)組中。在遇到新的邊的時候粥庄，通過更新這些信息就可以得到新的最短路徑丧失。

我們在其中會用到邊的松弛技術(shù)，定義如下：放松邊v->w意味著檢查從s到w的最短路徑是否先從s到v惜互，然后再由v到w布讹。如果是，則根據(jù)這個情況更新數(shù)據(jù)結(jié)構(gòu)的內(nèi)容训堆。下面代碼實現(xiàn)了這個操作描验。由v到w的最短路徑是distTo[v]與e.weight()之和——如果這個值不小于distTo[w]，則稱這條邊失效了并忽略坑鱼；如果這個值更小膘流，則更新數(shù)據(jù)。

image-20200821103035529.png

4.4.2.5 頂點的松弛

實際上，實現(xiàn)會放松從一個給定頂點只會的所有邊睡扬，如下面（被重載的）relax()的實現(xiàn)所示盟蚣。注意，從任意distTo[v]為有限值的頂點v指向任意distTo[]為無窮的頂點都是有效的卖怜。如果v被放松屎开，那么這些有效邊就會被添加到edgeTo[]中。某條從起點指出的邊將會是第一條被加入edgeTo[]中的邊马靠。算法會謹慎選擇頂點奄抽，使得每次頂點松弛操作都能得出到達某個頂點的最短的路徑，最后逐漸找出到達每個頂點的最短路徑甩鳄。

image-20200821103450635.png

4.4.2.6 為用例準備的查詢方法

edgeTo[]和distTo[]直接支持pathTo()逞度、hasPathTo()和distTo()的查詢方法。默認所有最短路徑的實現(xiàn)都包含這段代碼妙啃。前面已經(jīng)提到過档泽，只有v是從s可達的情況下，distTo[v]才是有意義的揖赴，還約定馆匿，對于從s不可達的頂點，distTo()方法都應(yīng)該返回?zé)o窮大燥滑。在實現(xiàn)這個約定時渐北，將distTo[]中所有元素都初始化為Double.POSITIVE_INFINITY,distTo[s]則為0。最短路徑算法會將從起點可達的頂點v的distTo[v]設(shè)為一個有限制铭拧，這樣就不必再用marked[]數(shù)組來在圖的搜索中標記可達的頂點赃蛛，而是檢查distTo[v]是否為Double.POSITIVE_INFINITY來實現(xiàn)hasPathTo(v)。對于pathTo()方法搀菩，我們約定如果v不是從起點科大的則返回null呕臂，如果v等于起點返回一條不含任何邊的路徑

image-20200821104514383.png

4.4.3最短路徑算法的理論基礎(chǔ)

4.4.3.1 最優(yōu)性條件

一下命題證明了判斷路徑是否最短路徑的全局條件與放松一條邊的時候檢測的局部條件是否等價。

image-20200821105637483.png

4.4.3.3 通用算法

由最優(yōu)性條件可以得到一個涵蓋所有最短路徑的通用算法》景希現(xiàn)在诵闭，我們暫時只研究非負權(quán)重的情況。

image-20200821110321443.png

通用算法沒有指定邊的放松順序澎嚣。

Dijkstra算法

Dijkstra首先將distTo[s]初始化為0，distTo[]中的其他元素初始化為正無窮瘟芝。然后將distTo[]最小的非樹頂點放松并加入樹中易桃，知道所有的頂點都在樹中或所有的非樹頂點的distTo[]值為無窮大

image-20200821112412112.png

4.4.4.1 數(shù)據(jù)結(jié)構(gòu)

要實現(xiàn)Dijkstra算法，除了distTo[]和edgeTo[]外锌俱，還需要一條索引優(yōu)先隊列pq晤郑，保存需要放松的頂點并確認下一個被放松的頂點。

代碼實現(xiàn)：

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<>(G.V());
        for (int i = 0; i < G.V(); i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.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)) {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (pq.contains(w)) pq.change(w, distTo[w]);
                else pq.insert(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<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }
}

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

許多應(yīng)用中的加權(quán)有向圖都是不含有有向環(huán)的，我們現(xiàn)在來學(xué)習(xí)一種比Dijkstra算法更快造寝、更簡單的在無環(huán)加權(quán)有向圖中找出最短路徑的算法磕洪，它的特點是

  • 能夠在線性時間內(nèi)解決單點最短路徑問題
  • 能夠處理負權(quán)重的邊
  • 能夠解決相關(guān)的問題，例如找出最長路徑诫龙。

這些算法都是無環(huán)有向圖的拓撲排序算法的簡單擴展析显。

特別的是，只要將頂點的放松和拓撲排序結(jié)合起來签赃，馬上就能得到一種解決無環(huán)加權(quán)有向圖中最短路徑問題的算法谷异。

首先，將distTo[s]初始化為0锦聊，其他distTo[]元素初始化為無窮大歹嘹，然后一個個按照拓撲排序順序放松所有頂點

image-20200821144337028.png

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

/**
 * 無環(huán)加權(quán)有向圖的最短路徑算法
 */
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)) {
            int 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.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> stack = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            stack.push(e);
        }
        return stack;
    }
}

4.4.5.1 最長路徑

無環(huán)加權(quán)有向圖中的單點最長路徑。給定一幅無環(huán)加權(quán)有向圖（邊的權(quán)重可為負）和一個起點s孔庭，回答“是否存在一條從s到給定的頂點v的路徑尺上？如果有，找出最長的那條路徑”

image-20200821145703078.png

實現(xiàn)該類的一個簡單方法是修改AcyclicSP圆到，將distTo[]的初始值變?yōu)镈ouble.NEGATIVE_INFINITY并改變relax()不等式的方向

/**
 * 無環(huán)加權(quán)有向圖的最長路徑算法
 */
public class AcyclicLP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;

    public AcyclicLP(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.NEGATIVE_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)) {
            int 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> stack = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            stack.push(e);
        }
        return stack;
    }
}

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

4.4.6.3 負權(quán)重的環(huán)

我們研究含有負權(quán)重邊的有向圖的時候怎抛，如果該圖含有一個權(quán)重為負的環(huán)，那么最短路徑的概念就失去意義了构资。例如圖4.4.20抽诉，除了

5->4的權(quán)重為-0.66外，它和第一個示例完全相同吐绵。這里迹淌，環(huán)4->7->5->4權(quán)重為0.37+0.28-0.66=-0.01

只要圍著這個環(huán)兜圈子就能得到權(quán)重任意短的路徑

image-20200821153909049.png
定義：加權(quán)有向圖的**負權(quán)重環(huán)**是一個總權(quán)重（環(huán)上所有邊的權(quán)重之和）為負的有向環(huán)

無論是否存在負權(quán)重環(huán)，從s到可達的其他頂點的一條最短路徑都是存在的己单。不幸的是唉窃，解決這個問題的最好方法在最壞情況下所需的時間是指數(shù)級別的。一般來說纹笼，我們認為這個問題“太難了”纹份。

現(xiàn)在我們解決下列問題：

  • 負權(quán)重環(huán)的檢測。給定的加權(quán)有向圖中含有負權(quán)重環(huán)嗎廷痘？ 如果有蔓涧，找到它。
  • 負權(quán)重環(huán)不可達時的單點最短路徑笋额。給定一幅加權(quán)有向圖和一個起點s且s無法到達任何負權(quán)重環(huán)元暴，回答“是否存在一條從s到給定頂點v的有向路徑？如果有兄猩，找出最短（總權(quán)重最熊哉怠）的那條路徑”鉴未。

總結(jié)盡管在含有環(huán)的有向圖中最短路徑?jīng)]有意義，而且也無法解決在這種有向圖中高效找出最短簡單路徑的問題鸠姨，但在實際應(yīng)用中仍需要識別出其中的負權(quán)重環(huán)铜秆。

image-20200821160220606.png
image-20200821161945156.png

我們不會仔細研究這個版本，因為它總是放松VE條邊且只需要稍加修改即可使算法在一般的應(yīng)用場景中更高效讶迁。

4.4.6.5 基于隊列的Bellman-Ford算法

根據(jù)經(jīng)驗我們知道在任意一輪中許多邊的放松都不會成功：只有上一輪中的distTo[]值發(fā)生變化的頂點指出的邊才能夠改變其他distTo[]元素的值连茧。

為了記錄這樣的頂點，我們使用了一條FIFO隊列添瓷。

4.4.6.6 實現(xiàn)

根據(jù)這些描述實現(xiàn)Bellman-Ford算法需要的代碼非常少

基于下面兩種數(shù)據(jù)結(jié)構(gòu)：

  • 一條用來保存即將被放松的頂點隊列queue梅屉；
  • 一個由頂點索引的boolean的數(shù)據(jù)onQ[]，用來指示頂點是否存在隊列中鳞贷，以防止將頂點重復(fù)插入隊列坯汤。

這些數(shù)據(jù)結(jié)構(gòu)保證，隊列中不出現(xiàn)重復(fù)的頂點搀愧，在某一輪中改變了edgeTo[]和distTo[]的所有頂點在下一輪中被處理惰聂。

算法 基于隊列的Bellman-Ford算法

/**
 * 基于隊列的Bellman-Ford算法
 */
public class BellmanFordSP {
    private double[] distTo;    //從起點到某個頂點的路徑長度
    private DirectedEdge[] edgeTo;  //從起點到某個頂點的最后一條邊
    private boolean[] onQ;  //該頂點是否存在于隊列中
    private Queue<Integer> queue;   //正在被放松的頂點
    private int cost;   //relax()的調(diào)用次數(shù)
    private Iterable<DirectedEdge> cycle;//edgeTo[]中是否有負權(quán)重環(huán)

    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        onQ = new boolean[G.V()];
        queue = new ArrayDeque<>();
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0;
        queue.add(s);
        onQ[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) {
            int v = queue.remove();
            onQ[v] = false;
            relax(G, 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]) {
                    queue.add(w);
                    onQ[w] = true;
                }
            }
            if (cost++ % G.V() == 0) {
                findNegativeCycle();
            }
        }
    }

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

    private boolean hasNegativeCycle() {
        return cycle != null;
    }
}
public Iterable<DirectedEdge> negativeCycle(){
        return cycle;
    }

4.4.6.7 負權(quán)重的邊

image-20200821161955946.png
image-20200821162009090.png
image-20200821162023292.png

4.4.6.8 負權(quán)重環(huán)的檢測

檢測負權(quán)重環(huán)來避免無限的循環(huán)。


image-20200821162134336.png
  • 添加一個變量cycle和一個私有函數(shù)findNegativeCycle()咱筛。如果找到負權(quán)重環(huán)搓幌，則會將cycle設(shè)為含有環(huán)中所有邊的一個迭代器。
  • 每調(diào)用V次relax()方法后即調(diào)用findNegativeCycle()方法迅箩。

4.4.7 展望

image-20200821162645633.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末溉愁，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子饲趋，更是在濱河造成了極大的恐慌拐揭，老刑警劉巖，帶你破解...
    沈念sama閱讀 212,383評論 6贊 493
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件奕塑，死亡現(xiàn)場離奇詭異堂污，居然都是意外死亡，警方通過查閱死者的電腦和手機龄砰，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,522評論 3贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門盟猖，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人换棚，你說我怎么就攤上這事式镐。” “怎么了固蚤？”我有些...
    開封第一講書人閱讀 157,852評論 0贊 348
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵娘汞，是天一觀的道長。 經(jīng)常有香客問我颇蜡，道長价说，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 56,621評論 1贊 284
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任风秤，我火速辦了婚禮鳖目，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘缤弦。我一直安慰自己领迈，他們只是感情好，可當我...
    茶點故事閱讀 65,741評論 6贊 386
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布碍沐。 她就那樣靜靜地躺著狸捅，像睡著了一般。 火紅的嫁衣襯著肌膚如雪累提。 梳的紋絲不亂的頭發(fā)上尘喝，一...
    開封第一講書人閱讀 49,929評論 1贊 290
  • 城市分裂傳說
    那天，我揣著相機與錄音斋陪，去河邊找鬼朽褪。 笑死，一個胖子當著我的面吹牛无虚，可吹牛的內(nèi)容都是我干的缔赠。 我是一名探鬼主播，決...
    沈念sama閱讀 39,076評論 3贊 410
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼友题，長吁一口氣：“原來是場噩夢啊……” “哼嗤堰！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起度宦，我...
    開封第一講書人閱讀 37,803評論 0贊 268
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤踢匣，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后斗埂，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體符糊，經(jīng)...
    沈念sama閱讀 44,265評論 1贊 303
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,582評論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年呛凶，在試婚紗的時候發(fā)現(xiàn)自己被綠了男娄。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,716評論 1贊 341
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡漾稀，死狀恐怖模闲，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情崭捍，我是刑警寧澤尸折，帶...
    沈念sama閱讀 34,395評論 4贊 333
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站殷蛇，受9級特大地震影響实夹，放射性物質(zhì)發(fā)生泄漏橄浓。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 40,039評論 3贊 316
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一亮航、第九天 我趴在偏房一處隱蔽的房頂上張望荸实。 院中可真熱鬧，春花似錦缴淋、人聲如沸准给。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,798評論 0贊 21
  • 一樁弒父案重抖，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽露氮。三九已至，卻和暖如春钟沛，著一層夾襖步出監(jiān)牢的瞬間畔规，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,027評論 1贊 266
  • 情欲美人皮
    我被黑心中介騙來泰國打工讹剔， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留油讯，地道東北人。 一個月前我還...
    沈念sama閱讀 46,488評論 2贊 361
  • 代替公主和親
    正文 我出身青樓延欠，卻偏偏與公主長得像陌兑，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子由捎，可洞房花燭夜當晚...
    茶點故事閱讀 43,612評論 2贊 350