溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
迪杰斯特拉算法
迪杰斯特拉算法是由荷蘭計算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。具體的計算規(guī)則我們可以通過下圖進(jìn)行查看。
通過這幅圖我們可以簡單的理解迪杰斯特拉算法算法的基礎(chǔ)思路，下面我們就通過JAVA來實現(xiàn)這個算法。
算法實現(xiàn)
在迪杰斯特拉算法中我們需要保存從起點開始到每一個節(jié)點最短步長，這也是圖中需要比較得出的步長，同時我們還需要存儲該步長下的前一個節(jié)點是哪個，這樣我們就可以通過終點一個一個往前推到起點，這樣就出來了完整的最優(yōu)路徑。
每一個節(jié)點的最優(yōu)前一節(jié)點
public class PreNode {
private String preNodeName;//最優(yōu)的前一個節(jié)點
private int nodeStep;// 起點到前一個節(jié)點的步長+前一個節(jié)點本身的步長
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;
}
}
定義返回的數(shù)據(jù)結(jié)構(gòu)
package dijkstra;
import java.util.List;
public class MinStep {
private boolean reachable;// 是否可達(dá)
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);
}
功能實現(xiàn)
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 {
// 圖中相鄰兩個節(jié)點的距離
private HashMap<String, HashMap<String, Integer>> stepLength;
// 非獨立節(jié)點個數(shù)
private int nodeNum;
// 移除節(jié)點
private HashSet<String> outNode;
// 起點到各點的步長，key為目的節(jié)點，value為到目的節(jié)點的步長
private HashMap<String, PreNode> nodeStep;
// 下一次計算的節(jié)點
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;
// 起點、終點不在目標(biāo)節(jié)點內(nèi)，返回不可達(dá)
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);
// 再將所經(jīng)過的節(jié)點添加到路徑第一位中
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;
}
// 獲取下一個計算節(jié)點
String start = nextNode.removeFirst();
// 到達(dá)該節(jié)點的最小距離
int step = 0;
if (nodeStep.containsKey(start)) {
step = nodeStep.get(start).getNodeStep();
}
// 獲取該節(jié)點可達(dá)節(jié)點
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;
}
// 起點到可達(dá)節(jié)點的距離
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));
}
}
// 將該節(jié)點移除
outNode.add(start);
// 計算下一個節(jié)點
step();
}
}
step()邏輯解析
這一步也就是迪杰斯特拉算法的核心部分，在計算的過程中，我們需要進(jìn)行如下步驟：
1）判斷是否達(dá)到終止條件，如果達(dá)到終止條件，結(jié)束本次算法，如果沒有達(dá)到，執(zhí)行下一步；（終止條件：下一次需要計算的節(jié)點隊列沒有數(shù)據(jù)或已經(jīng)計算過的節(jié)點數(shù)等于節(jié)點總數(shù)）
2）獲取下一次計算的節(jié)點A；
3）從起點到各節(jié)點之間的最短距離map中獲取到達(dá)A點的最小距離L；
4）獲取A節(jié)點的可達(dá)節(jié)點B，計算從起點先到A再到B是否優(yōu)于已有的其他方式到B，如果優(yōu)于，則更新B節(jié)點，否則不更新；
5）判斷B是否是已經(jīng)移除的節(jié)點，如果不是移除的節(jié)點，把B添加到下一次需要計算的節(jié)點隊列中，否則不做操作；
6）判斷A節(jié)點是否還有除B以外的其他節(jié)點，如果有，執(zhí)行第4）步，否則執(zhí)行下一步；
7）將A節(jié)點從下一次需要計算的節(jié)點中移除添加到已經(jīng)計算過的節(jié)點中；
8）執(zhí)行第一步。
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}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼