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