Dijkstra
Dijkstra屬于單源最短路徑算法，用于計算一個頂點到其他所有頂點的最短路徑。
- 使用前提：不能有負權(quán)邊。也就是說，如果圖中有負權(quán)邊，不能使用Dijkstra算法來計算最短路徑，但是可以使用Bellman-Ford來計算
- 時間復雜度：可優(yōu)化至O(ElogV)，E是邊的數(shù)量，V是頂點數(shù)量。
Dijkstra算法是由荷蘭科學家Edsger Wybe Dijkstra發(fā)明的，也曾在1972年獲得圖靈獎。
Dijkstra等價思考
現(xiàn)在就來研究一下，Dijkstra算法是怎樣的。
首先，Dijkstra的原理其實和生活中的一些自然現(xiàn)象是完全一樣的。什么自然現(xiàn)象呢？接下來就一起跟著下面的描述，來想想一件事情。如果想清楚的話，對于理解Dijkstra算法會大有幫助。
- 把圖中的沒一個頂點都想象成為一塊小石頭。
- 每一條邊想象成是一條繩子，每一條繩子都連接著2塊小石頭，邊的權(quán)值就是繩子的長度。
-
將小石頭和繩子平放在一張桌子上，（下圖是一張俯視圖，圖中黃顏色的是桌子）
什么是俯視圖？下圖所示的這張圖就是一張俯視圖，所以現(xiàn)在發(fā)揮你的想象力，將上圖黃顏色部分想象成為一張桌面，桌子上面擺了一堆的石頭，然后繩子兩邊連接著石頭
-
接下來想象以下，用手拽著小石頭A，慢慢地向上提起來，遠離桌面，如下圖所示的側(cè)視圖
- 離開桌面的順序取決于其余頂點距離頂點A的最短繩子長度，也就是最短路徑。所以，最終你會發(fā)現(xiàn)，B,D,C,E會依次離開桌面，當所有石頭都離開桌面時，有的繩子會蹦直，而有的繩子是松的。
- 最后繃直的繩子就是A到其他小石頭的最短路徑。
關(guān)鍵信息：后離開桌面的小石頭，都是被先離開桌面的小石頭拉起來的。
在本節(jié)中，討論的Dijkstra算法與這種自然現(xiàn)象的原理是非常像的，所以理解了這種自然現(xiàn)象，就對于理解Dijkstra算法有非常大的幫助。
Dijkstra執(zhí)行過程
假設現(xiàn)在有如下的有向圖
現(xiàn)在同樣是計算A到其他頂點之間的最短路徑，模擬剛剛的自然現(xiàn)象的話，就相當于現(xiàn)在要將石頭A拽起來，其他小石頭現(xiàn)在還在桌面，現(xiàn)在要計算A到其他頂點之間的最短路徑，A就是最先被拉起來的小石頭。然后上圖中有不同的顏色，其中黑色表示最短路徑的源頭，紅色表示與剛剛被拉起來的頂點直接相連的頂點，藍色表示不是與剛剛被拉起來的頂點直接相連的頂點。
由于現(xiàn)在A已經(jīng)離開桌面了，所以下一個即將被拽起來的石頭，一定是B，D，E中的其中一個石頭，因為B，D，E是與A直接相連的，C不能再A離開以后的下一個離開桌面，因為B還沒有離開桌面。并且與A直接相連的三個頂點，其中權(quán)值最小的頂點將會成為下一個離開桌面的石頭，被A拽起來。
所以現(xiàn)在由于A已經(jīng)被拽起來，離開了桌面，下一個即將被拽起來的石頭，一定是B，D，E中的其中一個石頭。所以B，D，E是有機會成為下一個離開桌面的石頭。那么在A離開桌面以后，就更新一下A到B，D，E之間的距離，用來表示A到其他頂點之間的最短路徑，更新的表格結(jié)果如下
通過頂點A的outEdges，目前能直接得到的A→B，A→D，A→E的權(quán)值，就如上表所示、由于現(xiàn)在C并沒有與A直接相連，所以A并不知道C的存在，因此A→C的權(quán)值，目前就用∞來進行表示。
通過這個表，就可以確定，下一步哪個石頭即將離開桌面，所以根據(jù)上面的數(shù)據(jù)，離A最近的石頭B將成為下一個離開桌面的石頭，離開后的結(jié)果如下
由于B已經(jīng)離開桌面，也就意味著，A到B之間的最短路徑已經(jīng)確定。并且由于B已經(jīng)離開桌面，所以與B直接相連的C也成為了下一個可能即將離開桌面的石頭，那么就可以認為C目前最有可能被B拽起來，所以認為A到C之間的最短路徑可能是A→B→C的路徑，所以更新表格，得到的數(shù)據(jù)如下
- 綠色：表示已經(jīng)離開桌面，并且是確定的最短路徑，后面不用再考慮這條路徑
- 紅色：表示更新了的最短路徑信息
- 藍色：表示本次更新沒有修改
通過這個表格，你可能會想，為什么不通過A→D→C這條路徑來將C拽起來呢？很簡單，因為現(xiàn)在D還沒有離開桌面，所以D目前就沒有能力將C從桌面拽起來，只有B才有可能。最終在下一個離開桌面的石頭中，可能是A拽來的E或者D，也可能是B拽起來的C，至于到底哪個石頭將會被拽起來，則取決于他們與A之間的路徑。
從上表中可以很明顯的看出，沒有離開桌面的C，D，E中，離A最近的是D，所以下一個即將被拽起來的是D，所以D離開桌面以后的結(jié)果如下
由于現(xiàn)在D已經(jīng)離開桌面了，并且發(fā)現(xiàn)D與E，C之間同樣連接著一根線，也就意味著，石頭E和石頭C有新的選擇。
為什么呢？就拿E來說，在D沒有被拽起來離開桌面之前，E只可能被A拽起來離開桌面，而現(xiàn)在D被拽起來了以后，E就可能既被A拽起來離開桌面，也可能被D拽起來離開桌面，至于最終被誰拽起來，則取決于A→E之間的權(quán)重與A→D→E之間的權(quán)重誰更小。
根據(jù)上面的解釋，也就意味著E和C均多了一種被D拽起來離開桌面的可能。所以當D被拽起來離開桌面以后，就更新A到C，A到E之間的路徑長度，所以更新后的表格如下
接下來，哪個石頭將被拽起來，同樣是依據(jù)表格中還沒有被拽起來石頭中個，哪個石頭到原點A之間的距離最小，最小的就將被拽起來。很明顯，下一個將被拉起來的石頭是C，拽起來以后的結(jié)果如下
到現(xiàn)在，A,B,C,D都被拽起來了，而且請注意，一旦C被拽起來，也就意味著E又多了一種新的選擇。因為在C被拽起來之前，認為E可能是通過A→D→E這條路徑，將E拽起來的。但是現(xiàn)在C也被拽起來了，所以E有可能通過A→D→C→E這條路徑被拽起來。所以就比較這兩條路徑，哪條路徑的路徑長度更短，最終比較發(fā)現(xiàn)是通過A→D→C→E這條路徑是更短的，所以更新表格中的路徑長度
由于到現(xiàn)在，沒有被拽起來的石頭只有E，所以下一個被拽起來的石頭就是E，并且通過A→D→C→E這條路徑被轉(zhuǎn)起來的。
最終，下圖中綠色的線，就是最終被繃直的線
最短路徑對應的表格如下
以上的這個過程，就是通過Dijkstra算法計算最短路徑的流程。
松弛操作（Relaxation）
松弛操作：表示更新兩個頂點之間最短路徑
例如前面D被拉起來以后，C和E都多了一種被拉起來的選擇，就是E可能被A拉起來，也可能被D拉起來；C可能被D拉起來，也可能被B拉起來。具體在D被來起來以后，C和E將被哪個石頭拉起來，就需要更新C到A之間的路徑，更新E到A之間的路徑。這種更新兩個頂點之間的路徑的操作，就叫做松弛操作。也就是說，確定A到D的最短路徑以后，對DC，DE邊進行松弛操作，更新了A到C，A到E的最短路徑。
在這里的松弛操作，一般指的是，更新源點到另一個點之間的最短路徑。
所以前面的過程，通過松弛操作來進行闡述的話，就是
- 一旦有石頭被拽起來，就需要對該石頭的outEdges進行松弛操作，計算出outEdges這些頂點被拽起來的最短路徑。
- 所以當A被拽起來以后，就需要對AB，AD，AE這些邊進行松弛操作，更新這些邊到原點之間的最短路徑
- 找出路徑長度最短的點，通過上面的表格可以知道，當前路徑最短的是A→B這條路徑，所以B被拽起來
- B一旦被拽起來，也就意味著A到B之間的最短路徑確定了，然后對B的outEdges進行松弛操作，由于目前B的outEdges只有一條表BC，所以現(xiàn)在對BC邊進行松弛操作
- 基礎超出路徑長度最小的頂點，所以這一次，D被拽了起來
- D被拽起來了以后，又會對D的outEdges進行一次松弛操作，所以會對DE，DC這兩條邊進行松弛操作
- 就依照這種流程，一直重復，直到確定所有頂點的最短路徑，算法就結(jié)束了。
Dijkstra實現(xiàn)
結(jié)合前面的分析，最終要實現(xiàn)的是計算出某個頂點到其他頂點的最短路徑。
其中要計算出最短路徑，則有以下幾個關(guān)鍵步驟：
- 每當有一個頂點被拽起來以后，就會從對路徑發(fā)生變化的頂點進行松弛操作，在不斷松弛的過程中，會更新該頂點到其他頂點之間的最短路徑長度
- 選擇一個路徑長度最短的頂點，作為下一個即將離開桌面的頂點
- 重復以上兩個步驟
所以結(jié)合這個思路，可以得到計算最短路徑的大概框架
public Map<V, E> shortestPath(V begin) {
Vertex beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
Map<V, E> selectedPaths = new HashMap<>();
Map<Vertex<V,E>, E> paths = new HashMap<>();
while (!paths.isEmpty()) {
Map.Entry<Vertex<V,E>,E> minEntry = getShortestPath(paths);
//minEntry離開桌面
Vertex<V,E> minVertex = minEntry.getKey();
selectedPaths.put(minVertex.value,minEntry.getValue());
paths.remove(minVertex);
//對minVertex的outEdges進行松弛操作
for (Edge<V,E> edge : minVertex.outEdges) {
relax();
}
}
return selectedPaths;
}
/*
* 從paths中選出一個最短的路徑出來
* */
private Map.Entry<Vertex<V,E>,E> getShortestPath(Map<Vertex<V,E>, E> paths) {
return null;
}
/*
* 進行松弛操作
* */
private void relax() {
}
其中selectedPaths這個Map用來保存已經(jīng)計算出最短路徑的頂點，paths這個Map用來保存下一個即將離開桌面的頂點。當paths中的所有頂點都計算出最短路徑以后，說明整個最短路徑就計算完畢了。
結(jié)合上面的框架，與前面的分析思路，最終得到的基礎版本實現(xiàn)如下
public Map<V, E> shortestPath(V begin) {
Vertex<V,E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
Map<V, E> selectedPaths = new HashMap<>();
Map<Vertex<V,E>, E> paths = new HashMap<>();
//初始化paths
for (Edge<V,E> edge: beginVertex.outEdges) {
paths.put(edge.to,edge.weight);
}
while (!paths.isEmpty()) {
Map.Entry<Vertex<V,E>,E> minEntry = getShortestPath(paths);
//minEntry離開桌面
Vertex<V,E> minVertex = minEntry.getKey();
selectedPaths.put(minVertex.value,minEntry.getValue());
paths.remove(minVertex);
//對minVertex的outEdges進行松弛操作
for (Edge<V,E> edge : minVertex.outEdges) {
//如果edge.to已經(jīng)離開桌面，就沒必要進行松弛操作
if (selectedPaths.containsKey(edge.to.value)) continue;;
//relax();
//新的可選的最短路徑：beginVertex到edge.from的最短路徑 + edge.weight
//minEntry.getValue() + edge.weight;
E newWeight = weightManager.add(minEntry.getValue(),edge.weight);
//以前的最短路徑：beginVertex到edge.to的最短路徑
E oldWeight = paths.get(edge.to);
//比較兩個路徑長度
if (oldWeight == null || weightManager.compare(newWeight,oldWeight) < 0) {
//如果新的路徑長度比舊的路徑更短,或者原來沒有舊的路徑長度，就更新路徑長度
paths.put(edge.to,newWeight);
}
}
}
//如果是無向圖，前面會將起點也添加進去，所以最后將起點刪除掉
selectedPaths.remove(begin);
return selectedPaths;
}
/*
* 從paths中選出一個最短的路徑出來
* */
private Map.Entry<Vertex<V,E>,E> getShortestPath(Map<Vertex<V,E>, E> paths) {
Iterator<Map.Entry<Vertex<V,E>,E>> it = paths.entrySet().iterator();
Map.Entry<Vertex<V,E>,E> minEntry = it.next();
while (it.hasNext()) {
Map.Entry<Vertex<V,E>,E> entry = it.next();
if (weightManager.compare(entry.getValue(),minEntry.getValue()) < 0) {
minEntry = entry;
}
}
return minEntry;
}
所以上面的代碼，就是完完全全按照前面的分析，結(jié)合將小石頭從桌子上提起來這種生活現(xiàn)象，對Dijkstra這種單源最短路徑算法進行實現(xiàn)。所以可以發(fā)現(xiàn)整體的思路還是挺簡單的，而且代碼也不復雜。
但是目前上面這種算法，返回的內(nèi)容是終點與原點之間，對應的路徑長度。并沒有包含是通過哪些頂點計算出來的最短路徑。所以有時候可能希望返回的數(shù)據(jù)里面，包含了從原點到達終點時，經(jīng)過了哪些頂點。所以需要將上面的算法進行改進
Dijkstra改進
為了達到前面想要實現(xiàn)的功能，所以需要對返回的數(shù)據(jù)進行修改。在返回的Map中，將經(jīng)過的最短路徑也保存到Map中，這樣返回的結(jié)果就跟全面了。
首先要改進的地方是對接口進行修改。在前面的Map中，每一個鍵值對中，key（頂點）對應的value是權(quán)值，所以現(xiàn)在要將頂點對應的信息修改為邊的信息+ 權(quán)值，這樣就能拿到最終計算出最短路徑時，經(jīng)過的路徑信息。
最終經(jīng)過改進后的算法如下：
public Map<V, PathInfo<V, E>> shortestPath(V begin) {
Vertex<V,E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
Map<Vertex<V,E>, PathInfo<V, E>> paths = new HashMap<>();
//初始化paths
for (Edge<V,E> edge: beginVertex.outEdges) {
PathInfo<V,E> path = new PathInfo<V,E>();
path.setWeight(edge.weight);
path.edgeInfos.add(edge.info());
paths.put(edge.to,path);
}
while (!paths.isEmpty()) {
Map.Entry<Vertex<V,E>, PathInfo<V,E>> minEntry = getShortestPath(paths);
//minEntry離開桌面
Vertex<V,E> minVertex = minEntry.getKey();
selectedPaths.put(minVertex.value,minEntry.getValue());
paths.remove(minVertex);
//對minVertex的outEdges進行松弛操作
for (Edge<V,E> edge : minVertex.outEdges) {
//如果edge.to已經(jīng)離開桌面，就沒必要進行松弛操作
if (selectedPaths.containsKey(edge.to.value)) continue;;
//relax();
//新的可選的最短路徑：beginVertex到edge.from的最短路徑 + edge.weight
//minEntry.getValue() + edge.weight;
E newWeight = weightManager.add(minEntry.getValue().weight,edge.weight);
//以前的最短路徑：beginVertex到edge.to的最短路徑
PathInfo<V,E> oldPath = paths.get(edge.to);
//比較兩個路徑長度
if (oldPath == null || weightManager.compare(newWeight,oldPath.weight) < 0) {
//如果新的路徑長度比舊的路徑更短,或者原來沒有舊的路徑長度，就更新路徑長度
PathInfo<V,E> path = new PathInfo<>();
path.weight = newWeight;
path.edgeInfos.addAll(minEntry.getValue().edgeInfos);
path.edgeInfos.add(edge.info());
paths.put(edge.to,path);
}
}
}
//如果是無向圖，前面會將起點也添加進去，所以最后將起點刪除掉
selectedPaths.remove(begin);
return selectedPaths;
}
/*
* 從paths中選出一個最短的路徑出來
* */
private Map.Entry<Vertex<V,E>, PathInfo<V,E>> getShortestPath(Map<Vertex<V,E>, PathInfo<V,E>> paths) {
Iterator<Map.Entry<Vertex<V,E>, PathInfo<V,E>>> it = paths.entrySet().iterator();
Map.Entry<Vertex<V,E>, PathInfo<V,E>> minEntry = it.next();
while (it.hasNext()) {
Map.Entry<Vertex<V,E>, PathInfo<V,E>> entry = it.next();
if (weightManager.compare(entry.getValue().weight,minEntry.getValue().weight) < 0) {
minEntry = entry;
}
}
return minEntry;
}
然后將以上代碼進行優(yōu)化后，結(jié)果如下
public Map<V, PathInfo<V, E>> shortestPath(V begin) {
Vertex<V,E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
Map<Vertex<V,E>, PathInfo<V, E>> paths = new HashMap<>();
//初始化paths
for (Edge<V,E> edge: beginVertex.outEdges) {
PathInfo<V,E> path = new PathInfo<V,E>();
path.setWeight(edge.weight);
path.edgeInfos.add(edge.info());
paths.put(edge.to,path);
}
while (!paths.isEmpty()) {
Map.Entry<Vertex<V,E>, PathInfo<V,E>> minEntry = getShortestPath(paths);
//minEntry離開桌面
Vertex<V,E> minVertex = minEntry.getKey();
PathInfo<V,E> minPath = minEntry.getValue();
selectedPaths.put(minVertex.value,minPath);
paths.remove(minVertex);
//對minVertex的outEdges進行松弛操作
for (Edge<V,E> edge : minVertex.outEdges) {
//如果edge.to已經(jīng)離開桌面，就沒必要進行松弛操作
if (selectedPaths.containsKey(edge.to.value)) continue;;
relax(edge,paths,minPath);
}
}
//如果是無向圖，前面會將起點也添加進去，所以最后將起點刪除掉
selectedPaths.remove(begin);
return selectedPaths;
}
/*
* 從paths中選出一個最短的路徑出來
* */
private Map.Entry<Vertex<V,E>, PathInfo<V,E>> getShortestPath(Map<Vertex<V,E>, PathInfo<V,E>> paths) {
Iterator<Map.Entry<Vertex<V,E>, PathInfo<V,E>>> it = paths.entrySet().iterator();
Map.Entry<Vertex<V,E>, PathInfo<V,E>> minEntry = it.next();
while (it.hasNext()) {
Map.Entry<Vertex<V,E>, PathInfo<V,E>> entry = it.next();
if (weightManager.compare(entry.getValue().weight,minEntry.getValue().weight) < 0) {
minEntry = entry;
}
}
return minEntry;
}
private void relax(Edge<V,E> edge, Map<Vertex<V,E> ,PathInfo<V,E>> paths, PathInfo<V,E> fromPath) {
//新的可選的最短路徑：beginVertex到edge.from的最短路徑 + edge.weight
//minEntry.getValue() + edge.weight;
E newWeight = weightManager.add(fromPath.weight,edge.weight);
//以前的最短路徑：beginVertex到edge.to的最短路徑
PathInfo<V,E> oldPath = paths.get(edge.to);
//如果新的路徑大于等于原來路徑，就不用做任何操作
if (oldPath != null && weightManager.compare(newWeight,oldPath.weight) >= 0) return;
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to,oldPath);
}else {
oldPath.edgeInfos.clear();
}
oldPath.weight = newWeight;
oldPath.edgeInfos.addAll(fromPath.edgeInfos);
oldPath.edgeInfos.add(edge.info());
paths.put(edge.to,oldPath);
}
到這里，就將Dijkstra計算原點到其他點的最短路徑計算出來了。不過這種算法并不是最優(yōu)的算法，因為在從paths中選出一個最短的路徑出來時，使用的是便于理解的遍歷比較來實現(xiàn)的，這種算法，效率比較低，在前面有介紹過使用堆這種數(shù)據(jù)結(jié)構(gòu)來獲取最值，效率非常高。所以如果要優(yōu)化的話， 可以考慮在從paths中選出一個最短的路徑出來時，使用最小堆這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。
完！
