圖論（5）：最短路徑問題：Dijkstra與Floyd算法

定義

所謂最短路徑問題是指：如果從圖中某一頂點(diǎn)（源點(diǎn)）到達(dá)另一頂點(diǎn)（終點(diǎn)）的路徑可能不止一條花竞，如何找到一條路徑使得沿此路徑上各邊的權(quán)值總和（稱為路徑長度）達(dá)到最小约急。

下面我們介紹兩種比較常用的求最短路徑算法：

Dijkstra（迪杰斯特拉）算法

他的算法思想是按路徑長度遞增的次序一步一步并入來求取厌蔽，是貪心算法的一個(gè)應(yīng)用奴饮，用來解決單源點(diǎn)到其余頂點(diǎn)的最短路徑問題戴卜。

算法思想

首先，我們引入一個(gè)輔助向量D师脂，它的每個(gè)分量D[i]表示當(dāng)前找到的從起始節(jié)點(diǎn)v到終點(diǎn)節(jié)點(diǎn)vi的最短路徑的長度吃警。它的初始態(tài)為：若從節(jié)點(diǎn)v到節(jié)點(diǎn)vi有弧酌心，則D[i]為弧上的權(quán)值安券，否則D[i]為∞完疫，顯然壳鹤，長度為D[j] = Min{D[i] | vi ∈V}的路徑就是從v出發(fā)最短的一條路徑饰迹，路徑為(v, vi)。
那么匿值，下一條長度次短的最短路徑是哪一條呢挟憔？假設(shè)次短路徑的終點(diǎn)是vk绊谭，則可想而知达传，這條路徑或者是(v, vk)或者是(v, vj, vk)迫筑。它的長度或者是從v到vk的弧上的權(quán)值脯燃，或者是D[j]和從vj到vk的權(quán)值之和搂妻。

一般情況下，假設(shè)S為已知求得的最短路徑的終點(diǎn)集合曲伊，則可證明：一下條最短路徑（設(shè)其終點(diǎn)為x）或者是弧(v, x)或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑叽讳。這可用反證法來證明追他，假設(shè)此路徑上有一個(gè)頂點(diǎn)不在S中坟募，則說明存在一條終點(diǎn)不在S中而長度比此路徑短的路徑。但是這是不可能的邑狸。因?yàn)椋覀兪前绰窂匠６鹊倪f增次序來產(chǎn)生個(gè)最短路徑的单雾，故長度比此路徑端的所有路徑均已產(chǎn)生赚哗，他們的終點(diǎn)必定在S集合中，即假設(shè)不成立硅堆。

因此下一條次短的最短路徑的長度是：D[j] = Min{D[i] | vi ∈ V - S}屿储，其中，D[i]或者是弧(v, vi)的權(quán)值渐逃，或者是D[k](vk ∈ S)和弧(vk, vi)上權(quán)值之和够掠。

算法描述

假設(shè)現(xiàn)要求取如下示例圖所示的頂點(diǎn)V0與其余各頂點(diǎn)的最短路徑：

Dijkstra算法示例圖

我們使用Guava的ValueGraph作為該圖的數(shù)據(jù)結(jié)構(gòu)，每個(gè)頂點(diǎn)對應(yīng)一個(gè)visited變量來表示節(jié)點(diǎn)是在V中還是在S中茄菊，初始時(shí)S中只有頂點(diǎn)V0疯潭。然后從nodes集合中遍歷找出從V0出發(fā)到各節(jié)點(diǎn)路徑最短的節(jié)點(diǎn)赊堪，并將該節(jié)點(diǎn)并入S中（即修改該節(jié)點(diǎn)的visited屬性為true），此時(shí)就找到了一個(gè)頂點(diǎn)的最短路徑竖哩。然后哭廉，我們看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)，并且看看通過該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長度是否比從V0直接到達(dá)更短,如果是相叁，則修改這些頂點(diǎn)的權(quán)值(即if (D[j] + arcs[j][k] < D[k]) then D[k] = D[j] + arcs[j][k])遵绰。然后又從{V - S}中找最小值，重復(fù)上述動(dòng)作增淹，直到所有頂點(diǎn)都并入S中街立。

第一步，我們通過ValueGraphBuilder構(gòu)造圖的實(shí)例埠通，并輸入邊集：

MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed()
        .nodeOrder(ElementOrder.insertion())
        .expectedNodeCount(10)
        .build();
graph.putEdgeValue(V0, V2, 10);
graph.putEdgeValue(V0, V4, 30);
graph.putEdgeValue(V0, V5, 100);
graph.putEdgeValue(V1, V2, 5);
graph.putEdgeValue(V2, V3, 50);
graph.putEdgeValue(V3, V5, 10);
graph.putEdgeValue(V4, V3, 20);
graph.putEdgeValue(V4, V5, 60);

return graph;

初始輸出結(jié)果如下：

nodes: [v0, v2, v4, v5, v1, v3], 
edges: {<v0 -> v5>=100, <v0 -> v4>=30, <v0 -> v2>=10, 
<v2 -> v3>=50, <v4 -> v5>=60, <v4 -> v3>=20, <v1 -> v2>=5, 
<v3 -> v5>=10}

為了不破壞graph的狀態(tài)赎离，我們引入一個(gè)臨時(shí)結(jié)構(gòu)來記錄每個(gè)節(jié)點(diǎn)運(yùn)算的中間結(jié)果：

private static class NodeExtra {
    public String nodeName; //當(dāng)前的節(jié)點(diǎn)名稱
    public int distance; //開始點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑
    public boolean visited; //當(dāng)前節(jié)點(diǎn)是否已經(jīng)求的最短路徑（S集合）
    public String preNode; //前一個(gè)節(jié)點(diǎn)名稱
    public String path; //路徑的所有途徑點(diǎn)
}

第二步，我們首先將起始點(diǎn)V0并入集合S中端辱，因?yàn)樗淖疃搪窂揭阎獮?：

startNode = V0;
NodeExtra current = nodeExtras.get(startNode);
current.distance = 0; //一開始可設(shè)置開始節(jié)點(diǎn)的最短路徑為0
current.visited = true; //并入S集合
current.path = startNode;
current.preNode = startNode;

第三步梁剔，在當(dāng)前狀態(tài)下找出起始點(diǎn)V0開始到其他節(jié)點(diǎn)路徑最短的節(jié)點(diǎn)：

NodeExtra minExtra = null; //路徑最短的節(jié)點(diǎn)信息
int min = Integer.MAX_VALUE;
for (String notVisitedNode : nodes) {
    //獲取節(jié)點(diǎn)的輔助信息
    NodeExtra extra = nodeExtras.get(notVisitedNode); 
    
    //不在S集合中，且路徑較短
    if (!extra.visited && extra.distance < min) {
        min = extra.distance;
        minExtra = extra;
    }
}

第四步舞蔽，將最短路徑的節(jié)點(diǎn)并入集合S中：

if (minExtra != null) { //找到了路徑最短的節(jié)點(diǎn)
    minExtra.visited = true; //并入集合S中
    //更新其中轉(zhuǎn)節(jié)點(diǎn)路徑
    minExtra.path = nodeExtras.get(minExtra.preNode).path + " -> " + minExtra.nodeName; 
    current = minExtra; //標(biāo)識(shí)當(dāng)前并入的最短路徑節(jié)點(diǎn)
}

第五步荣病，更新與其相關(guān)節(jié)點(diǎn)的最短路徑中間結(jié)果：

/**
 * 并入新查找到的節(jié)點(diǎn)后，更新與其相關(guān)節(jié)點(diǎn)的最短路徑中間結(jié)果
 * if (D[j] + arcs[j][k] < D[k]) D[k] = D[j] + arcs[j][k]
 */
//只需循環(huán)當(dāng)前節(jié)點(diǎn)的后繼列表即可(優(yōu)化)
Set<String> successors = graph.successors(current.nodeName); 
for (String notVisitedNode : successors) {
    NodeExtra extra = nodeExtras.get(notVisitedNode);
    if (!extra.visited) {
        final int value = current.distance 
            + graph.edgeValueOrDefault(current.nodeName,
                notVisitedNode, 0); //D[j] + arcs[j][k]
        if (value < extra.distance) { //D[j] + arcs[j][k] < D[k]
            extra.distance = value;
            extra.preNode = current.nodeName;
        }
    }
}

第六步渗柿，輸出起始節(jié)點(diǎn)V0到每個(gè)節(jié)點(diǎn)的最短路徑以及路徑的途徑點(diǎn)信息

Set<String> keys = nodeExtras.keySet();
for (String node : keys) {
    NodeExtra extra = nodeExtras.get(node);
    if (extra.distance < Integer.MAX_VALUE) {
        Log.i(TAG, startNode + " -> " + node + ": min: " + extra.distance
                + ", path: " + extra.path); //path在運(yùn)算過程中更新
    }
}

實(shí)例圖的輸出結(jié)果為：

 v0 -> v0: min: 0, path: v0
 v0 -> v2: min: 10, path: v0 -> v2
 v0 -> v3: min: 50, path: v0 -> v4 -> v3
 v0 -> v4: min: 30, path: v0 -> v4
 v0 -> v5: min: 60, path: v0 -> v4 -> v3 -> v5

具體Dijkstra算法的示例demo實(shí)現(xiàn)个盆，請參考：https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/Dijkstra.java

Floyd（弗洛伊德）算法

Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。是解決任意兩點(diǎn)間的最短路徑(稱為多源最短路徑問題)的一種算法朵栖，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題颊亮。（動(dòng)態(tài)規(guī)劃算法是通過拆分問題規(guī)模，并定義問題狀態(tài)與狀態(tài)的關(guān)系陨溅，使得問題能夠以遞推（分治）的方式去解決终惑，最終合并各個(gè)拆分的小問題的解為整個(gè)問題的解。）

算法思想

從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能：1)直接從節(jié)點(diǎn)i到節(jié)點(diǎn)j门扇，2)從節(jié)點(diǎn)i經(jīng)過若干個(gè)節(jié)點(diǎn)k到節(jié)點(diǎn)j雹有。所以，我們假設(shè)arcs(i,j)為節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑的距離臼寄，對于每一個(gè)節(jié)點(diǎn)k霸奕，我們檢查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立，如果成立吉拳，證明從節(jié)點(diǎn)i到節(jié)點(diǎn)k再到節(jié)點(diǎn)j的路徑比節(jié)點(diǎn)i直接到節(jié)點(diǎn)j的路徑短质帅，我們便設(shè)置arcs(i,j) = arcs(i,k) + arcs(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)k临梗，arcs(i,j)中記錄的便是節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑的距離涡扼。（由于動(dòng)態(tài)規(guī)劃算法在執(zhí)行過程中，需要保存大量的臨時(shí)狀態(tài)（即小問題的解）盟庞，因此它天生適用于用矩陣來作為其數(shù)據(jù)結(jié)構(gòu)吃沪，因此在本算法中，我們將不使用Guava-Graph結(jié)構(gòu)什猖，而采用鄰接矩陣來作為本例的數(shù)據(jù)結(jié)構(gòu)）

算法分析及描述

假設(shè)現(xiàn)要求取如下示例圖所示任意兩點(diǎn)之間的最短路徑：


最短路徑示例圖

我們以一個(gè)4x4的鄰接矩陣（二維數(shù)組arcs[ ][ ]）作為圖的數(shù)據(jù)結(jié)構(gòu)票彪。比如1號(hào)節(jié)點(diǎn)到2號(hào)節(jié)點(diǎn)的路徑的權(quán)值為2，則arcs[1][2] = 2不狮，2號(hào)節(jié)點(diǎn)無法直接到達(dá)4號(hào)節(jié)點(diǎn)降铸，則arcs[2][4] = ∞(Integer.MAX_VALUE)，則可構(gòu)造如下矩陣：


有向圖的初始鄰接矩陣

根據(jù)以往的經(jīng)驗(yàn)摇零，如果要讓任意兩個(gè)頂點(diǎn)（假設(shè)從頂點(diǎn)a到頂點(diǎn)b）之間的距離變得更短推掸，唯一的選擇就是引入第三個(gè)頂點(diǎn)（頂點(diǎn)k），并通過頂點(diǎn)k中轉(zhuǎn)（a -> k ->b）才可能縮短頂點(diǎn)a到頂點(diǎn)b之間的距離驻仅。于是谅畅，現(xiàn)在的問題便分解為：求取某一個(gè)點(diǎn)k，使得經(jīng)過中轉(zhuǎn)節(jié)點(diǎn)k后噪服，使得兩點(diǎn)之間的距離可能變短毡泻，且還可能需要中轉(zhuǎn)兩個(gè)或者多個(gè)節(jié)點(diǎn)才能使兩點(diǎn)之間的距離變短。比如圖中的4號(hào)節(jié)點(diǎn)到3號(hào)節(jié)點(diǎn)（4 -> 3）的距離原本是12（arcs[4][3] = 12）粘优，如果在只通過1號(hào)節(jié)點(diǎn)時(shí)中轉(zhuǎn)時(shí)（4 -> 1 ->3）仇味，距離將縮短為11（arcs[4][1] + arcs[1][3] = 5 + 6 = 11）。其實(shí)1號(hào)節(jié)點(diǎn)到3號(hào)節(jié)點(diǎn)也可以通過2號(hào)節(jié)點(diǎn)中轉(zhuǎn)雹顺，使得1號(hào)到3號(hào)節(jié)點(diǎn)的路程縮短為5（arcs[1][2] + arcs[2][3] = 2 + 3 = 5）丹墨，所以如果同時(shí)經(jīng)過1號(hào)和2號(hào)兩個(gè)節(jié)點(diǎn)中轉(zhuǎn)的話，從4號(hào)節(jié)點(diǎn)到3號(hào)節(jié)點(diǎn)的距離會(huì)進(jìn)一步縮短為10无拗。于是带到，延伸到一般問題：
1昧碉、當(dāng)不經(jīng)過任意第三節(jié)點(diǎn)時(shí)英染，其最短路徑為初始路徑，即上圖中的鄰接矩陣所示被饿。
2四康、當(dāng)只允許經(jīng)過1號(hào)節(jié)點(diǎn)時(shí)，求兩點(diǎn)之間的最短路徑該如何求呢狭握？只需判斷arcs[i][1]+arcs[1][j]是否比arcs[i][j]要小即可闪金。arcs[i][j]表示的是從i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)之間的距離，arcs[i][1] + arcs[1][j]表示的是從i號(hào)頂點(diǎn)先到1號(hào)頂點(diǎn)，再從1號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的路程之和哎垦。循環(huán)遍歷一遍二維數(shù)組囱嫩，便可以獲取在僅僅經(jīng)過1號(hào)節(jié)點(diǎn)時(shí)的最短距離，實(shí)現(xiàn)如下：

for (int i = 1; i <= vexCount; i++) {
    for (int j = 1; j < vexCount; j++) {
        if (arcs[i][1] + arcs[1][j] < arcs[i][j]) {
            arcs[i][j] = arcs[i][1] + arcs[1][j]; 
        }
    }
}

由于上述代碼更新了兩點(diǎn)之間經(jīng)過1號(hào)節(jié)點(diǎn)的最短距離arcs[i][j]漏设，因此墨闲，數(shù)組中每兩個(gè)節(jié)點(diǎn)之間對應(yīng)距離都是最短的。由于此時(shí)arcs[i][j]的結(jié)果已經(jīng)保存了中轉(zhuǎn)1號(hào)節(jié)點(diǎn)的最短路徑郑口，此時(shí)如果繼續(xù)并入2號(hào)節(jié)點(diǎn)為中轉(zhuǎn)節(jié)點(diǎn)鸳碧，則是任意兩個(gè)節(jié)點(diǎn)都經(jīng)過中轉(zhuǎn)節(jié)點(diǎn)1號(hào)節(jié)點(diǎn)和2號(hào)節(jié)點(diǎn)的最短路徑，因?yàn)檫\(yùn)算完中轉(zhuǎn)1號(hào)節(jié)點(diǎn)時(shí)犬性，arcs[i][j]的結(jié)果已經(jīng)更新為中轉(zhuǎn)1號(hào)節(jié)點(diǎn)的最短路徑了瞻离。更一般的，繼續(xù)并入下一個(gè)中轉(zhuǎn)節(jié)點(diǎn)一直到vexCount個(gè)時(shí)乒裆，arcs[i][j]的結(jié)果保存的就是整個(gè)圖中兩點(diǎn)之間的最短路徑了套利。這就是Floyd算法的描述，變成代碼就是下面幾行行：

for (int k = 1; k <= vexCount; k++) { //并入中轉(zhuǎn)節(jié)點(diǎn)1,2,...vexCount
    for (int i = 1; i <= vexCount; i++) {
        for (int j = 1; j < vexCount; j++) {
            if (arcs[i][k] + arcs[k][j] < arcs[i][j]) {
                arcs[i][j] = arcs[i][k] + arcs[k][j];
                path[i][j] = path[i][k]; //這里保存當(dāng)前是中轉(zhuǎn)的是哪個(gè)節(jié)點(diǎn)的信息
            }
        }
    }
}

對應(yīng)到示例圖的中間運(yùn)算結(jié)果如下：

print array step of 1: //并入1號(hào)節(jié)點(diǎn)的結(jié)果
    0     2     6     4 
    ∞     0     3     ∞ 
    7     9     0     1 
    5     7    11     0 

print array step of 2: //并入2號(hào)節(jié)點(diǎn)的結(jié)果
    0     2     5     4 
    ∞     0     3     ∞ 
    7     9     0     1 
    5     7    10     0 

print array step of 3: //并入3號(hào)節(jié)點(diǎn)的結(jié)果
    0     2     5     4 
   10     0     3     4 
    7     9     0     1 
    5     7    10     0 

print array step of 4: //并入4號(hào)節(jié)點(diǎn)（圖最終兩兩節(jié)點(diǎn)之間的最短路徑值）
    0     2     5     4 
    9     0     3     4 
    6     8     0     1 
    5     7    10     0

雖然此時(shí)已求得了節(jié)點(diǎn)的最短路徑鹤耍，但結(jié)果卻不能明顯的表達(dá)最終最短路徑是中轉(zhuǎn)了哪些節(jié)點(diǎn)日裙，因此這里對應(yīng)到動(dòng)態(tài)規(guī)劃算法中的強(qiáng)項(xiàng)——算法過程中可以完全記錄所有的中間結(jié)果。我們再定義一個(gè)二位數(shù)組path[][]惰蜜，其大小規(guī)模對應(yīng)arcs[][]昂拂，初始結(jié)果path[i][j] = j，表示節(jié)點(diǎn)i到節(jié)點(diǎn)j最后的中轉(zhuǎn)節(jié)點(diǎn)是j抛猖。在運(yùn)算中是在判斷arcs[i][k]+arcs[k][j]比arcs[i][j]要小時(shí)格侯，我們進(jìn)一步更新為：path[i][j] = path[i][k]，即當(dāng)前最短路徑的最后中轉(zhuǎn)節(jié)點(diǎn)是path[i][k]對應(yīng)的節(jié)點(diǎn)（如果只允許中專一個(gè)節(jié)點(diǎn)時(shí)即為k财著，但中轉(zhuǎn)多個(gè)節(jié)點(diǎn)時(shí)联四，需要對應(yīng)上一步的中轉(zhuǎn)節(jié)點(diǎn)，因此這里要指明是path[i][k]而不是k）撑教。
于是我們通過向前遞推path[][]數(shù)組朝墩，直到path[i][j]是目標(biāo)節(jié)點(diǎn)。則可輸出其中轉(zhuǎn)節(jié)點(diǎn)伟姐，輸出函數(shù)實(shí)現(xiàn)如下：

private void printPath(int arcs[][], int path[][], int vexCount) {
    int temp;
    for (int i = 1; i <= vexCount; i++) {
        StringBuilder builder = new StringBuilder();
        for (int j = 1; j <= vexCount; j++) { //遍歷打印任意亮點(diǎn)的路徑
            builder.append(i).append("->").append(j)
                .append(", weight: "). append(arcs[i][j])
                    .append(":").append(i);
            temp = path[i][j];
            while(temp != j) {
                builder.append("->").append(temp);
                temp = path[temp][j];
            }
            builder.append("->").append(j).append("\n");
        }
        Log.i(TAG, builder.toString());
    }
}

對應(yīng)示例圖的最短路徑的中轉(zhuǎn)節(jié)點(diǎn)結(jié)果輸出如下：

 1->1, weight: 0, path: 1->1
 1->2, weight: 2, path: 1->2
 1->3, weight: 5, path: 1->2->3
 1->4, weight: 4, path: 1->4
 2->1, weight: 9, path: 2->3->4->1
 2->2, weight: 0, path: 2->2
 2->3, weight: 3, path: 2->3
 2->4, weight: 4, path: 2->3->4
 3->1, weight: 6, path: 3->4->1
 3->2, weight: 8, path: 3->4->1->2
 3->3, weight: 0, path: 3->3
 3->4, weight: 1, path: 3->4
 4->1, weight: 5, path: 4->1
 4->2, weight: 7, path: 4->1->2
 4->3, weight: 10, path: 4->1->2->3
 4->4, weight: 0, path: 4->4

具體Floyd算法的示例demo實(shí)現(xiàn)收苏，請參考：https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/Floyd.java

參考文檔

《數(shù)據(jù)結(jié)構(gòu)》（嚴(yán)蔚敏版）
http://developer.51cto.com/art/201403/433874.htm

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市愤兵，隨后出現(xiàn)的幾起案子鹿霸，更是在濱河造成了極大的恐慌，老刑警劉巖秆乳，帶你破解...
    沈念sama閱讀 218,858評論 6贊 508
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件懦鼠，死亡現(xiàn)場離奇詭異钻哩，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)肛冶，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,372評論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門街氢，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人睦袖，你說我怎么就攤上這事阳仔。” “怎么了扣泊？”我有些...
    開封第一講書人閱讀 165,282評論 0贊 356
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵近范，是天一觀的道長。 經(jīng)常有香客問我延蟹，道長评矩，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,842評論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任阱飘，我火速辦了婚禮斥杜，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘沥匈。我一直安慰自己蔗喂，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,857評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布高帖。 她就那樣靜靜地躺著缰儿，像睡著了一般。 火紅的嫁衣襯著肌膚如雪散址。 梳的紋絲不亂的頭發(fā)上乖阵，一...
    開封第一講書人閱讀 51,679評論 1贊 305
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音预麸，去河邊找鬼瞪浸。 笑死，一個(gè)胖子當(dāng)著我的面吹牛吏祸，可吹牛的內(nèi)容都是我干的对蒲。 我是一名探鬼主播，決...
    沈念sama閱讀 40,406評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼贡翘，長吁一口氣：“原來是場噩夢啊……” “哼蹈矮！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起床估，我...
    開封第一講書人閱讀 39,311評論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤含滴，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后丐巫，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,767評論 1贊 315
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,945評論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年递胧，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了碑韵。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,090評論 1贊 350
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡缎脾，死狀恐怖祝闻，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情遗菠，我是刑警寧澤联喘，帶...
    沈念sama閱讀 35,785評論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站辙纬，受9級特大地震影響豁遭，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜贺拣，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,420評論 3贊 331
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一蓖谢、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧譬涡，春花似錦闪幽、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,988評論 0贊 22
  • 一樁弒父案盯腌，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至陨瘩，卻和暖如春腊嗡，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背拾酝。 一陣腳步聲響...
    開封第一講書人閱讀 33,101評論 1贊 271
  • 情欲美人皮
    我被黑心中介騙來泰國打工燕少， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人蒿囤。 一個(gè)月前我還...
    沈念sama閱讀 48,298評論 3贊 372
  • 代替公主和親
    正文 我出身青樓客们，卻偏偏與公主長得像，于是被迫代替她去往敵國和親材诽。 傳聞我的和親對象是個(gè)殘疾皇子底挫，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,033評論 2贊 355

推薦閱讀更多精彩內(nèi)容

  • 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)溫故-5.圖（下）：最短路徑 圖的最重要的應(yīng)用之一就是在交通運(yùn)輸和通信網(wǎng)絡(luò)中尋找最短路徑。例如在交通網(wǎng)...
    mengjz閱讀 842評論 0贊 1
  • 一脸侥、定義 在一幅加權(quán)有向圖中建邓，最短路徑是指從頂點(diǎn)s到頂點(diǎn)t的最短路徑是所有從s到t的路徑中的權(quán)重最小者。求解最短路...
    null12閱讀 2,468評論 0贊 4
  • Floyd 算法 簡介 Floyd 算法又稱為插點(diǎn)法睁枕，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑...
    廖少少閱讀 8,510評論 0贊 1
  • 圖的定義與術(shù)語 1官边、圖按照有無方向分為無向圖和有向圖沸手。無向圖由頂點(diǎn)和邊構(gòu)成，有向圖由頂點(diǎn)和弧構(gòu)成注簿∑跫弧有弧尾和弧頭之...
    unravelW閱讀 408評論 0贊 0
  • 俗話說"病從口入"。人吃五谷雜糧哪有不生病的诡渴？生病按說是一種正尘杈В現(xiàn)象⊥纾可今天與史大夫的一番談話卻讓我領(lǐng)悟到：人能自...
    關(guān)耳子閱讀 761評論 8贊 18