溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
迪杰斯特拉算法
迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。具體的計算規則我們可以通過下圖進行查看。
通過這幅圖我們可以簡單的理解迪杰斯特拉算法算法的基礎思路，下面我們就通過JAVA來實現這個算法。
算法實現
在迪杰斯特拉算法中我們需要保存從起點開始到每一個節點最短步長，這也是圖中需要比較得出的步長，同時我們還需要存儲該步長下的前一個節點是哪個，這樣我們就可以通過終點一個一個往前推到起點，這樣就出來了完整的最優路徑。
每一個節點的最優前一節點
public class PreNode {
private String preNodeName;//最優的前一個節點
private int nodeStep;// 起點到前一個節點的步長+前一個節點本身的步長
public PreNode(String preNodeName, int nodeStep) {
this.preNodeName = preNodeName;
this.nodeStep = nodeStep;
}
public String getPreNodeName() {
return preNodeName;
}
public void setPreNodeName(String preNodeName) {
this.preNodeName = preNodeName;
}
public int getNodeStep() {
return nodeStep;
}
public void setNodeStep(int nodeStep) {
this.nodeStep = nodeStep;
}
}
定義返回的數據結構
package dijkstra;
import java.util.List;
public class MinStep {
private boolean reachable;// 是否可達
private int minStep;// 最短步長
private List<String> 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<String> getStep() {
return step;
}
public void setStep(List<String> step) {
this.step = step;
}
}
定義接口
package dijkstra;
import java.util.HashMap;
public interface Distance {
public static final MinStep UNREACHABLE = new MinStep(false, -1);
/**
* @param start
* @param end
* @param stepLength
* @return
* @Description: 起點到終點的最短路徑
*/
public MinStep getMinStep(String start, String end, final HashMap<String, HashMap<String, Integer>> stepLength);
}
功能實現
package dijkstra;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;
public class DistanceDijkstraImpl implements Distance {
// 圖中相鄰兩個節點的距離
private HashMap<String, HashMap<String, Integer>> stepLength;
// 非獨立節點個數
private int nodeNum;
// 移除節點
private HashSet<String> outNode;
// 起點到各點的步長，key為目的節點，value為到目的節點的步長
private HashMap<String, PreNode> nodeStep;
// 下一次計算的節點
private LinkedList<String> nextNode;
// 起點、終點
private String startNode;
private String endNode;
/**
* @param start
* @param end
* @param stepLength
* @return
* @Description: start 到 end 的最短距離
*/
public MinStep getMinStep(String start, String end, final HashMap<String, HashMap<String, Integer>> 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<String> step = new LinkedList<String>();
minStep.setStep(step);
// 先將終點添加到路徑第一位中
String tempNode = endNode;
step.addFirst(tempNode);
// 再將所經過的節點添加到路徑第一位中
while (nodeStep.containsKey(tempNode)) {
PreNode preNode = nodeStep.get(tempNode);
String preNodeName = preNode.getPreNodeName();
// System.out.println(preNodeName + " " + preNode.getNodeStep());
step.addFirst(preNodeName);
tempNode = preNodeName;
}
return minStep;
}
/**
* @param start
* @Description: 初始化屬性
*/
private void initProperty(String start, String end) {
outNode = new HashSet<String>();
nodeStep = new HashMap<String, PreNode>();
nextNode = new LinkedList<String>();
nextNode.add(start);
startNode = start;
endNode = end;
}
/**
* @param end
* @Description:
*/
private void step() {
if (nextNode == null || nextNode.size() < 1) {
return;
}
if (outNode.size() == nodeNum) {
return;
}
// 獲取下一個計算節點
String start = nextNode.removeFirst();
// 到達該節點的最小距離
int step = 0;
if (nodeStep.containsKey(start)) {
step = nodeStep.get(start).getNodeStep();
}
// 獲取該節點可達節點
HashMap<String, Integer> nextStep = stepLength.get(start);
Iterator<Entry<String, Integer>> iter = nextStep.entrySet().iterator();
while (iter.hasNext()) {
Entry<String, Integer> entry = iter.next();
String key = entry.getKey();
// 如果是起點到起點，不計算之間的步長
if (key.equals(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();
}
}
step()邏輯解析
這一步也就是迪杰斯特拉算法的核心部分，在計算的過程中，我們需要進行如下步驟：
1）判斷是否達到終止條件，如果達到終止條件，結束本次算法，如果沒有達到，執行下一步；（終止條件：下一次需要計算的節點隊列沒有數據或已經計算過的節點數等于節點總數）
2）獲取下一次計算的節點A；
3）從起點到各節點之間的最短距離map中獲取到達A點的最小距離L；
4）獲取A節點的可達節點B，計算從起點先到A再到B是否優于已有的其他方式到B，如果優于，則更新B節點，否則不更新；
5）判斷B是否是已經移除的節點，如果不是移除的節點，把B添加到下一次需要計算的節點隊列中，否則不做操作；
6）判斷A節點是否還有除B以外的其他節點，如果有，執行第4）步，否則執行下一步；
7）將A節點從下一次需要計算的節點中移除添加到已經計算過的節點中；
8）執行第一步。
Demo運行
import java.util.HashMap;
import com.alibaba.fastjson.JSONObject;
public class DistanceTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
HashMap<String, HashMap<String, Integer>> stepLength = new HashMap<String, HashMap<String, Integer>>();
HashMap<String, Integer> step1 = new HashMap<String, Integer>();
stepLength.put("1", step1);
step1.put("2", 2);
HashMap<String, Integer> step2 = new HashMap<String, Integer>();
stepLength.put("2", step2);
step2.put("1", 2);
step2.put("3", 1);
HashMap<String, Integer> step3 = new HashMap<String, Integer>();
stepLength.put("3", step3);
step3.put("2", 1);
step3.put("4", 1);
step3.put("9", 1);
HashMap<String, Integer> step4 = new HashMap<String, Integer>();
stepLength.put("4", step4);
step4.put("5", 1);
step4.put("3", 1);
HashMap<String, Integer> step5 = new HashMap<String, Integer>();
stepLength.put("5", step5);
step5.put("4", 1);
HashMap<String, Integer> step6 = new HashMap<String, Integer>();
stepLength.put("6", step6);
step6.put("9", 1);
HashMap<String, Integer> step7 = new HashMap<String, Integer>();
stepLength.put("7", step7);
step7.put("10", 1);
HashMap<String, Integer> step8 = new HashMap<String, Integer>();
stepLength.put("8", step8);
step8.put("11", 3);
HashMap<String, Integer> step9 = new HashMap<String, Integer>();
stepLength.put("9", step9);
step9.put("3", 1);
step9.put("6", 1);
step9.put("10", 1);
HashMap<String, Integer> step10 = new HashMap<String, Integer>();
stepLength.put("10", step10);
step10.put("9", 1);
step10.put("7", 1);
step10.put("11", 1);
HashMap<String, Integer> step11 = new HashMap<String, Integer>();
stepLength.put("11", step11);
step11.put("8", 3);
step11.put("10", 1);
System.out.println(JSONObject.toJSON(stepLength));
Distance distance = new DistanceDijkstraImpl();
MinStep step = distance.getMinStep("1", "5", stepLength);
System.out.println(JSONObject.toJSON(step));
step = distance.getMinStep("1", "8", stepLength);
System.out.println(JSONObject.toJSON(step));
step = distance.getMinStep("8", "1", stepLength);
System.out.println(JSONObject.toJSON(step));
step = distance.getMinStep("11", "7", stepLength);
System.out.println(JSONObject.toJSON(step));
step = distance.getMinStep("10", "8", stepLength);
System.out.println(JSONObject.toJSON(step));
}
}
{“11”:{“8”:1,“10”:1},“1”:{“2”:2},“2”:{“1”:2,“3”:1},“3”:{“4”:1,“9”:1,“2”:1},“4”:{“5”:1,“3”:1},“5”:{“4”:1},“6”:{“9”:1},“7”:{“10”:1},“8”:{“11”:1},“9”:{“6”:1,“3”:1,“10”:1},“10”:{“11”:1,“9”:1,“7”:1}}
{“minStep”:5,“step”:[“1”,“2”,“3”,“4”,“5”],“reachable”:true}
{“minStep”:7,“step”:[“1”,“2”,“3”,“9”,“10”,“11”,“8”],“reachable”:true}
{“minStep”:7,“step”:[“8”,“11”,“10”,“9”,“3”,“2”,“1”],“reachable”:true}
{“minStep”:2,“step”:[“11”,“10”,“7”],“reachable”:true}
{“minStep”:2,“step”:[“10”,“11”,“8”],“reachable”:true}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
