最短路徑問題：Dijkstra算法
- 2020 年 2 月 11 日
- 筆記
定義
所謂最短路徑問題是指：如果從圖中某一頂點（源點）到達另一頂點（終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權值總和（稱為路徑長度）達到最小。
下面我們介紹兩種比較常用的求最短路徑算法：
Dijkstra（迪傑斯特拉）算法
他的算法思想是按路徑長度遞增的次序一步一步併入來求取，是貪心算法的一個應用，用來解決單源點到其餘頂點的最短路徑問題。
算法思想
首先，我們引入一個輔助向量D，它的每個分量D[i]表示當前找到的從起始節點v到終點節點vi的最短路徑的長度。它的初始態為：若從節點v到節點vi有弧，則D[i]為弧上的權值，否則D[i]為∞，顯然，長度為D[j] = Min{D[i] | vi ∈V}的路徑就是從v出發最短的一條路徑，路徑為(v, vi)。
那麼，下一條長度次短的最短路徑是哪一條呢？假設次短路徑的終點是vk，則可想而知，這條路徑或者是(v, vk)或者是(v, vj, vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的權值之和。
因此下一條次短的最短路徑的長度是：D[j] = Min{D[i] | vi ∈ V – S}，其中，D[i]或者是弧(v, vi)的權值，或者是Dk和弧(vk, vi)上權值之和。
算法描述
假設現要求取如下示例圖所示的頂點V0與其餘各頂點的最短路徑：
我們使用Guava的ValueGraph作為該圖的數據結構，每個頂點對應一個visited變量來表示節點是在V中還是在S中，初始時S中只有頂點V0。然後，我們看看新加入的頂點是否可以到達其他頂點，並且看看通過該頂點到達其他點的路徑長度是否比從V0直接到達更短,如果是，則修改這些頂點的權值(即if (D[j] + arcs[j][k] < D[k]) then D[k] = D[j] + arcs[j][k])。然後又從{V – S}中找最小值，重複上述動作，直到所有頂點都併入S中。
第一步，我們通過ValueGraphBuilder構造圖的實例，並輸入邊集：
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;
初始輸出結果如下：
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的狀態，我們引入一個臨時結構來記錄每個節點運算的中間結果：
private static class NodeExtra { public String nodeName; //當前的節點名稱 public int distance; //開始點到當前節點的最短路徑 public boolean visited; //當前節點是否已經求的最短路徑（S集合） public String preNode; //前一個節點名稱 public String path; //路徑的所有途徑點 }
第二步，我們首先將起始點V0併入集合S中，因為他的最短路徑已知為0：
startNode = V0; NodeExtra current = nodeExtras.get(startNode); current.distance = 0; //一開始可設置開始節點的最短路徑為0 current.visited = true; //併入S集合 current.path = startNode; current.preNode = startNode;
第三步，在當前狀態下找出起始點V0開始到其他節點路徑最短的節點：
NodeExtra minExtra = null; //路徑最短的節點信息 int min = Integer.MAX_VALUE; for (String notVisitedNode : nodes) { //獲取節點的輔助信息 NodeExtra extra = nodeExtras.get(notVisitedNode); //不在S集合中，且路徑較短 if (!extra.visited && extra.distance < min) { min = extra.distance; minExtra = extra; } }
第四步，將最短路徑的節點併入集合S中：
if (minExtra != null) { //找到了路徑最短的節點 minExtra.visited = true; //併入集合S中 //更新其中轉節點路徑 minExtra.path = nodeExtras.get(minExtra.preNode).path + " -> " + minExtra.nodeName; current = minExtra; //標識當前併入的最短路徑節點 }
第五步，更新與其相關節點的最短路徑中間結果：
/** * 併入新查找到的節點後，更新與其相關節點的最短路徑中間結果 * if (D[j] + arcs[j][k] < D[k]) D[k] = D[j] + arcs[j][k] */ //只需循環當前節點的後繼列表即可(優化) 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; } } }
第六步，輸出起始節點V0到每個節點的最短路徑以及路徑的途徑點信息
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在運算過程中更新 } }
實例圖的輸出結果為：
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實現，請參考：
