Java 迪杰斯特拉算法實現(xiàn)查找最短距離的實現(xiàn)
更新時間：2019年09月03日 14:40:39 作者：gmHappy
這篇文章主要介紹了Java 迪杰斯特拉算法實現(xiàn)查找最短距離的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
迪杰斯特拉算法
迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。具體的計算規(guī)則我們可以通過下圖進行查看。
通過這幅圖我們可以簡單的理解迪杰斯特拉算法算法的基礎思路，下面我們就通過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;// 是否可達
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;
// 起點、終點不在目標節(jié)點內(nèi)，返回不可達
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();
// 到達該節(jié)點的最小距離
int step = 0;
if (nodeStep.containsKey(start)) {
step = nodeStep.get(start).getNodeStep();
}
// 獲取該節(jié)點可達節(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;
}
// 起點到可達節(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()邏輯解析
這一步也就是迪杰斯特拉算法的核心部分，在計算的過程中，我們需要進行如下步驟：
1）判斷是否達到終止條件，如果達到終止條件，結(jié)束本次算法，如果沒有達到，執(zhí)行下一步；（終止條件：下一次需要計算的節(jié)點隊列沒有數(shù)據(jù)或已經(jīng)計算過的節(jié)點數(shù)等于節(jié)點總數(shù)）
2）獲取下一次計算的節(jié)點A；
3）從起點到各節(jié)點之間的最短距離map中獲取到達A點的最小距離L；
4）獲取A節(jié)點的可達節(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)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java在ElasticSearch中使用LocalDatetime類型
最近在開發(fā)一個搜索功能的需求的時候,遇到了LocalDatetime類型不能保存到ElasticSearch中的問題,這篇文章主要介紹了Java在ElasticSearch中使用LocalDatetime類型2023-10-10
下面小編就為大家?guī)硪黄狫ava基礎的幾道練習題(分享)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧，希望可以幫到你2021-07-07
下面小編就為大家?guī)硪黄綧yBatis源碼全面解析】MyBatis一二級緩存介紹。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要為大家詳細介紹了servlet實現(xiàn)文件上傳與下載功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-03-03
Spring實戰(zhàn)之協(xié)調(diào)作用域不同步的Bean操作示例
這篇文章主要介紹了Spring實戰(zhàn)之協(xié)調(diào)作用域不同步的Bean操作,結(jié)合實例形式分析了Spring協(xié)調(diào)作用域不同步的Bean相關(guān)配置及使用技巧,需要的朋友可以參考下2019-11-11
Java Socket編程心跳包創(chuàng)建實例解析
這篇文章主要介紹了Java Socket編程心跳包創(chuàng)建實例解析，具有一定借鑒價值,需要的朋友可以參考下2017-12-12
這篇文章主要介紹了Spring Boot打包部署和環(huán)境配置詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-05-05
以生成[10,20]隨機數(shù)為例，首先生成0-20的隨機數(shù)，然后對(20-10+1)取模得到[0-10]之間的隨機數(shù)，然后加上min=10，最后生成的是10-20的隨機數(shù)2013-09-09
spring boot整合Shiro實現(xiàn)單點登錄的示例代碼
本篇文章主要介紹了spring boot整合Shiro實現(xiàn)單點登錄的示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-01-01
這篇文章主要介紹了Spring MVC 攔截器實現(xiàn)登錄,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07