JAVA實現最短距離算法之迪傑斯特拉算法
最短路徑問題是圖論研究中的一個經典的算法問題，旨在尋找圖中兩個節點之間的最短路徑，最常用的算法有Dijkstra算法、SPFA算法\Bellman-Ford算法、Floyd算法\Floyd-Warshall算法、Johnson算法等，這篇博客將重點介紹Dijkstra算法。
迪傑斯特拉算法
迪傑斯特拉算法是由荷蘭計算機科學家狄克斯特拉於1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪傑斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。具體的計算規則我們可以通過下圖進行查看。
通過這幅圖我們可以簡單的理解迪傑斯特拉算法算法的基礎思路，下面我們就通過JAVA來實現這個算法。
算法實現
在具體的實現之前，我們先有一個基礎的約定，就是途中的每一個節點我們都用正整數進行編碼，相鄰兩點之間的距離是正整數，圖中兩個直接相鄰兩點的距離我們保存到map中，也就是求最短距離我們需要實現這樣的一個方法：
public MinStep getMinStep(int start, int end, final HashMap> stepLength);
第一個參數是起始節點的編號，第二個參數是終點節點的編號，第三個參數是圖中直接相鄰兩個節點的距離組成的map。關於第三個參數，會在後面做詳細的介紹。這裡我們定義一個接口，用於計算兩點之間的最短路徑，具體如下：
/**
[email protected]:
*/
package com.lulei.distance;
import java.util.HashMap;
import com.lulei.distance.bean.MinStep;
public interface Distance {
public static final MinStep UNREACHABLE = new MinStep(false, -1);
/**
* @param start
* @param end
* @param stepLength
* @return
* @Author:lulei
* @Description: 起點到終點的最短路徑
*/
public MinStep getMinStep(int start, int end, final HashMap> stepLength);
}
一、方法返回值介紹
上面方法的返回值是我們自定義的一個數據類型，下面我們通過代碼來看其具體的數據結構：
/**
[email protected]:
*/
package com.lulei.distance.bean;
import java.util.List;
public class MinStep {
private boolean reachable;//是否可達
private int minStep;//最短步長
private List step;//最短路徑
public MinStep() {
}
public MinStep(boolean reachable, int minStep) {
this.reachable = reachable;
this.minStep = minStep;
}
public boolean isReachable() {
return reachable;
}
public void setReachable(boolean reachable) {
this.reachable = reachable;
}
public int getMinStep() {
return minStep;
}
public void setMinStep(int minStep) {
this.minStep = minStep;
}
public List getStep() {
return step;
}
public void setStep(List step) {
this.step = step;
}
}
其中最短路徑的那個List數組保存了從起點到終點最短路徑所經歷的節點。
二、每一個節點的最優前一節點
在迪傑斯特拉算法中我們需要保存從起點開始到每一個節點最短步長，這也是圖中需要比較得出的步長，同時我們還需要存儲該步長下的前一個節點是哪個，這樣我們就可以通過終點一個一個往前推到起點，這樣就出來了完整的最優路徑。
/**
[email protected]:
*/
package com.lulei.distance.bean;
public class PreNode {
private int preNodeNum;// 最優 前一個節點
private int nodeStep;// 最小步長
public PreNode(int preNodeNum, int nodeStep) {
this.preNodeNum = preNodeNum;
this.nodeStep = nodeStep;
}
public int getPreNodeNum() {
return preNodeNum;
}
public void setPreNodeNum(int preNodeNum) {
this.preNodeNum = preNodeNum;
}
public int getNodeStep() {
return nodeStep;
}
public void setNodeStep(int nodeStep) {
this.nodeStep = nodeStep;
}
}
三、迪傑斯特拉算法計算過程中需要關注的變量
從介紹迪傑斯特拉算法的圖中，我們知道在計算的過程中我們需要保存起點到各個節點的最短距離、已經計算過的節點、下次需要計算節點隊列和圖中相鄰兩個節點的距離。我們通過代碼來看下具體的定義：
//key1節點編號，key2節點編號，value為key1到key2的步長
private HashMap> stepLength;
//非獨立節點個數
private int nodeNum;
//移除節點
private HashSet outNode;
//起點到各點的步長，key為目的節點，value為到目的節點的步長
private HashMap nodeStep;
//下一次計算的節點
private LinkedList nextNode;
//起點、終點
private int startNode;
private int endNode;
我們這裡看下stepLength這個屬性，它保存了圖中相鄰兩個節點之間的距離，比如key1=1;key2=3;value=9;這代表的意義就是從節點1到節點3的距離是9。通過這樣的存儲，我們就需要把圖中每兩個相鄰的點保存到這個類型的map中。
四、屬性初始化
在開始計算之前，我們需要對這些屬性進行初始化，具體如下：
private void initProperty(int start, int end) {
outNode = new HashSet();
nodeStep = new HashMap();
nextNode = new LinkedList();
nextNode.add(start);
startNode = start;
endNode = end;
}
這一步我們需要把起點添加到下一次需要計算的節點隊列中。
五、迪傑斯特拉算法
這一步也就是迪傑斯特拉算法的核心部分，在計算的過程中，我們需要進行如下步驟：
1）判斷是否達到終止條件，如果達到終止條件，結束本次算法，如果沒有達到，執行下一步；（終止條件：下一次需要計算的節點隊列沒有數據或已經計算過的節點數等於節點總數）
2）獲取下一次計算的節點A；
3）從起點到各節點之間的最短距離map中獲取到達A點的最小距離L；
4）獲取A節點的可達節點B，計算從起點先到A再到B是否優於已有的其他方式到B，如果優於，則更新B節點，否則不更新；
5）判斷B是否是已經移除的節點，如果不是移除的節點，把B添加到下一次需要計算的節點隊列中，否則不做操作；
6）判斷A節點是否還有除B以外的其他節點，如果有，執行第4）步，否則執行下一步；
7）將A節點從下一次需要計算的節點中移除添加到已經計算過的節點中；
8）執行第一步。
我們來看下具體的代碼實現：
private void step() {
if (nextNode == null || nextNode.size() < 1) {
return;
}
if (outNode.size() == nodeNum) {
return;
}
//獲取下一個計算節點
int start = nextNode.removeFirst();
//到達該節點的最小距離
int step = 0;
if (nodeStep.containsKey(start)) {
step = nodeStep.get(start).getNodeStep();
}
//獲取該節點可達節點
HashMap nextStep = stepLength.get(start);
Iterator> iter = nextStep.entrySet().iterator();
while (iter.hasNext()) {
Entry entry = iter.next();
Integer key = entry.getKey();
//如果是起點到起點，不計算之間的步長
if (key == startNode) {
continue;
}
//起點到可達節點的距離
Integer value = entry.getValue() + step;
if ((!nextNode.contains(key)) && (!outNode.contains(key))) {
nextNode.add(key);
}
if (nodeStep.containsKey(key)) {
if (value < nodeStep.get(key).getNodeStep()) {
nodeStep.put(key, new PreNode(start, value));
}
} else {
nodeStep.put(key, new PreNode(start, value));
}
}
//將該節點移除
outNode.add(start);
//計算下一個節點
step();
}
六、組裝最短路徑返回結果
通過前面的計算，已經計算出了起點到各個節點的最短路徑，下面就需要組裝起點到終點的最短路徑，在計算最短距離下的路徑方式，我們需要從終點依次往前推，即到達終點最短距離下的前一個節點是A，到達A節點最短距離下的前一節點是B，直到找到起點終止。
private MinStep changeToMinStep() {
MinStep minStep = new MinStep();
minStep.setMinStep(nodeStep.get(endNode).getNodeStep());
minStep.setReachable(true);
LinkedList step = new LinkedList();
minStep.setStep(step);
int nodeNum = endNode;
step.addFirst(nodeNum);
while (nodeStep.containsKey(nodeNum)) {
int node = nodeStep.get(nodeNum).getPreNodeNum();
step.addFirst(node);
nodeNum = node;
}
return minStep;
}
七、接口定義方法實現
public MinStep getMinStep(int start, int end, final HashMap> stepLength) {
this.stepLength = stepLength;
this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;
//起點、終點不在目標節點內，返回不可達
if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {
return UNREACHABLE;
}
initProperty(start, end);
step();
if (nodeStep.containsKey(end)) {
return changeToMinStep();
}
return UNREACHABLE;
}
八、迪傑斯特拉算法完整代碼
/**
[email protected]:
*/
package com.lulei.distance.dijkstra;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;
import com.lulei.distance.Distance;
import com.lulei.distance.bean.MinStep;
import com.lulei.distance.bean.PreNode;
public class DistanceDijkstraImpl implements Distance{
//key1節點編號，key2節點編號，value為key1到key2的步長
private HashMap> stepLength;
//非獨立節點個數
private int nodeNum;
//移除節點
private HashSet outNode;
//起點到各點的步長，key為目的節點，value為到目的節點的步長
private HashMap nodeStep;
//下一次計算的節點
private LinkedList nextNode;
//起點、終點
private int startNode;
private int endNode;
/**
* @param start
* @param end
* @param stepLength
* @return
* @Author:lulei
* @Description: start 到 end 的最短距離
*/
public MinStep getMinStep(int start, int end, final HashMap> stepLength) {
this.stepLength = stepLength;
this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;
//起點、終點不在目標節點內，返回不可達
if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {
return UNREACHABLE;
}
initProperty(start, end);
step();
if (nodeStep.containsKey(end)) {
return changeToMinStep();
}
return UNREACHABLE;
}
/**
* 返回最短距離以及路徑
*/
private MinStep changeToMinStep() {
MinStep minStep = new MinStep();
minStep.setMinStep(nodeStep.get(endNode).getNodeStep());
minStep.setReachable(true);
LinkedList step = new LinkedList();
minStep.setStep(step);
int nodeNum = endNode;
step.addFirst(nodeNum);
while (nodeStep.containsKey(nodeNum)) {
int node = nodeStep.get(nodeNum).getPreNodeNum();
step.addFirst(node);
nodeNum = node;
}
return minStep;
}
/**
* @param start
* @Author:lulei
* @Description: 初始化屬性
*/
private void initProperty(int start, int end) {
outNode = new HashSet();
nodeStep = new HashMap();
nextNode = new LinkedList();
nextNode.add(start);
startNode = start;
endNode = end;
}
/**
* @param end
* @Author:lulei
* @Description:
*/
private void step() {
if (nextNode == null || nextNode.size() < 1) {
return;
}
if (outNode.size() == nodeNum) {
return;
}
//獲取下一個計算節點
int start = nextNode.removeFirst();
//到達該節點的最小距離
int step = 0;
if (nodeStep.containsKey(start)) {
step = nodeStep.get(start).getNodeStep();
}
//獲取該節點可達節點
HashMap nextStep = stepLength.get(start);
Iterator> iter = nextStep.entrySet().iterator();
while (iter.hasNext()) {
Entry entry = iter.next();
Integer key = entry.getKey();
//如果是起點到起點，不計算之間的步長
if (key == startNode) {
continue;
}
//起點到可達節點的距離
Integer value = entry.getValue() + step;
if ((!nextNode.contains(key)) && (!outNode.contains(key))) {
nextNode.add(key);
}
if (nodeStep.containsKey(key)) {
if (value < nodeStep.get(key).getNodeStep()) {
nodeStep.put(key, new PreNode(start, value));
}
} else {
nodeStep.put(key, new PreNode(start, value));
}
}
//將該節點移除
outNode.add(start);
//計算下一個節點
step();
}
}
代碼測試
對於上述代碼的測試，我們還是使用我們事例圖形中的例子，計算從節點1到節點5的最短距離。
/**
[email protected]:
*/
package com.lulei.distance.test;
import java.util.HashMap;
import com.lulei.distance.Distance;
import com.lulei.distance.bean.MinStep;
import com.lulei.distance.dijkstra.DistanceDijkstraImpl;
import com.lulei.util.JsonUtil;
public class DistanceTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
HashMap> stepLength = new HashMap>();
HashMap step1 = new HashMap();
stepLength.put(1, step1);
step1.put(6, 14);
step1.put(3, 9);
step1.put(2, 7);
HashMap step2 = new HashMap();
stepLength.put(2, step2);
step2.put(1, 7);
step2.put(3, 10);
step2.put(4, 15);
HashMap step3 = new HashMap();
stepLength.put(3, step3);
step3.put(1, 9);
step3.put(2, 10);
step3.put(4, 11);
step3.put(6, 2);
HashMap step4 = new HashMap();
stepLength.put(4, step4);
step4.put(2, 15);
step4.put(5, 5);
step4.put(3, 11);
HashMap step5 = new HashMap();
stepLength.put(5, step5);
step5.put(6, 9);
step5.put(4, 5);
HashMap step6 = new HashMap();
stepLength.put(6, step6);
step6.put(1, 14);
step6.put(5, 9);
step6.put(3, 2);
Distance distance = new DistanceDijkstraImpl();
MinStep step = distance.getMinStep(1, 5, stepLength);
System.out.println(JsonUtil.parseJson(step));
}
}
這裡組裝相鄰兩個節點之間的距離用了大量的代碼，我們看下輸出結果：
{"reachable":true,"minStep":20,"step":[1,3,6,5]}
最後的思考
最短路徑算法在現實生活中其實有很多的用處，比如迷宮解法、路徑規劃、路由尋址等等，這些問題看似很復雜，其實只需要做對應的轉化後還是可以用最基礎的算法解決的。
最近發現很多網站或者個人轉載博客，個人拒絕他人轉載，但是最起碼你給出我文章的出處，不會讓我認為自己辛辛苦苦寫的博客被別人剽竊。說到轉載問題，又需要提到現在的互聯網環境，有時候自己去找一篇博客，發現很難找到源作者或者最初的鏈接，一方面，自己寫博客不想在博文中添加自己的博客地址介紹影響博文的質量，另一方面博主有的時候對博文中的錯誤進行了修改，他人無法快速獲取該信息。
