Java 迪杰斯特拉算法實現(xiàn)查找最短距離的實現(xiàn)
更新時間：2019年09月03日 14:40:39 作者：gmHappy
這篇文章主要介紹了Java 迪杰斯特拉算法實現(xiàn)查找最短距離的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
迪杰斯特拉算法
迪杰斯特拉算法是由荷蘭計算機科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。具體的計算規(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í)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java 連接Access數(shù)據(jù)庫的兩種方式
這篇文章主要介紹了Java 連接Access數(shù)據(jù)庫的兩種方式,本文著重講解使用JDBC連接操作Access數(shù)據(jù)庫,需要的朋友可以參考下2015-06-06
工廠模式，是一種實例化對象的方式，只要輸入需要實例化對象的名字，就可以通過工廠對象的相應(yīng)工廠函數(shù)來制造你需要的對象2023-02-02
這篇文章主要介紹了Java線程的新建和就緒狀態(tài),結(jié)合實例形式分析了java線程的創(chuàng)建、調(diào)用等相關(guān)操作技巧,需要的朋友可以參考下2019-09-09
mybatis如何設(shè)置useGeneratedKeys=true
這篇文章主要介紹了mybatis如何設(shè)置useGeneratedKeys=true，具有很好的參考價值，希望對大家有所幫助。2022-01-01
這篇文章主要介紹了Java中MinIO的常用操作示例,MinIO 是一款基于Go語言發(fā)開的高性能、分布式的對象存儲系統(tǒng),客戶端支持Java,Net,Python,Javacript, Golang語言,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)圓形碰撞檢測，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
本篇文章給大家分享Spring Boot 實現(xiàn)圖片上傳并回顯功能，文中通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-07-07
這篇文章主要為大家介紹了java接口性能優(yōu)化技巧示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
這篇文章主要介紹了Java中前端傳參含有“+”“=”等特殊字符處理,比如“+”如果不經(jīng)過處理，傳到Java后臺之后，就變成空格了，“=”就直接沒了，本文對這一問題給大家詳細(xì)講解，需要的朋友可以參考下2023-10-10
對Java的面對對象編程中對象和引用以及內(nèi)部類的理解
這篇文章主要介紹了對Java的面對對象編程中對象和引用以及內(nèi)部類的理解,需要的朋友可以參考下2016-01-01