java實現(xiàn)Dijkstra最短路徑算法

更新時間：2020年05月27日 14:17:02 作者：javaman_chen

這篇文章主要為大家詳細介紹了java實現(xiàn)Dijkstra最短路徑算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

任務描述：在一個無向圖中，獲取起始節(jié)點到所有其他節(jié)點的最短路徑描述

Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是貪心法的算法策略，大概過程如下：

1.聲明兩個集合，open和close，open用于存儲未遍歷的節(jié)點，close用來存儲已遍歷的節(jié)點
2.初始階段，將初始節(jié)點放入close，其他所有節(jié)點放入open
3.以初始節(jié)點為中心向外一層層遍歷，獲取離指定節(jié)點最近的子節(jié)點放入close并從新計算路徑，直至close包含所有子節(jié)點

代碼實例如下：

Node對象用于封裝節(jié)點信息，包括名字和子節(jié)點

public class Node {
 private String name;
 private Map<Node,Integer> child=new HashMap<Node,Integer>();
 public Node(String name){
 this.name=name;
 }
 public String getName() {
 return name;
 }
 public void setName(String name) {
 this.name = name;
 }
 public Map<Node, Integer> getChild() {
 return child;
 }
 public void setChild(Map<Node, Integer> child) {
 this.child = child;
 }
}

MapBuilder用于初始化數(shù)據(jù)源，返回圖的起始節(jié)點

public class MapBuilder {
 public Node build(Set<Node> open, Set<Node> close){
 Node nodeA=new Node("A");
 Node nodeB=new Node("B");
 Node nodeC=new Node("C");
 Node nodeD=new Node("D");
 Node nodeE=new Node("E");
 Node nodeF=new Node("F");
 Node nodeG=new Node("G");
 Node nodeH=new Node("H");
 nodeA.getChild().put(nodeB, 1);
 nodeA.getChild().put(nodeC, 1);
 nodeA.getChild().put(nodeD, 4);
 nodeA.getChild().put(nodeG, 5);
 nodeA.getChild().put(nodeF, 2);
 nodeB.getChild().put(nodeA, 1);
 nodeB.getChild().put(nodeF, 2);
 nodeB.getChild().put(nodeH, 4);
 nodeC.getChild().put(nodeA, 1);
 nodeC.getChild().put(nodeG, 3);
 nodeD.getChild().put(nodeA, 4);
 nodeD.getChild().put(nodeE, 1);
 nodeE.getChild().put(nodeD, 1);
 nodeE.getChild().put(nodeF, 1);
 nodeF.getChild().put(nodeE, 1);
 nodeF.getChild().put(nodeB, 2);
 nodeF.getChild().put(nodeA, 2);
 nodeG.getChild().put(nodeC, 3);
 nodeG.getChild().put(nodeA, 5);
 nodeG.getChild().put(nodeH, 1);
 nodeH.getChild().put(nodeB, 4);
 nodeH.getChild().put(nodeG, 1);
 open.add(nodeB);
 open.add(nodeC);
 open.add(nodeD);
 open.add(nodeE);
 open.add(nodeF);
 open.add(nodeG);
 open.add(nodeH);
 close.add(nodeA);
 return nodeA;
 }
}

圖的結構如下圖所示：

Dijkstra對象用于計算起始節(jié)點到所有其他節(jié)點的最短路徑

public class Dijkstra {
 Set<Node> open=new HashSet<Node>();
 Set<Node> close=new HashSet<Node>();
 Map<String,Integer> path=new HashMap<String,Integer>();//封裝路徑距離
 Map<String,String> pathInfo=new HashMap<String,String>();//封裝路徑信息
 public Node init(){
 //初始路徑,因沒有A->E這條路徑,所以path(E)設置為Integer.MAX_VALUE
 path.put("B", 1);
 pathInfo.put("B", "A->B");
 path.put("C", 1);
 pathInfo.put("C", "A->C");
 path.put("D", 4);
 pathInfo.put("D", "A->D");
 path.put("E", Integer.MAX_VALUE);
 pathInfo.put("E", "A");
 path.put("F", 2);
 pathInfo.put("F", "A->F");
 path.put("G", 5);
 pathInfo.put("G", "A->G");
 path.put("H", Integer.MAX_VALUE);
 pathInfo.put("H", "A");
 //將初始節(jié)點放入close,其他節(jié)點放入open
 Node start=new MapBuilder().build(open,close);
 return start;
 }
 public void computePath(Node start){
 Node nearest=getShortestPath(start);//取距離start節(jié)點最近的子節(jié)點,放入close
 if(nearest==null){
 return;
 }
 close.add(nearest);
 open.remove(nearest);
 Map<Node,Integer> childs=nearest.getChild();
 for(Node child:childs.keySet()){
 if(open.contains(child)){//如果子節(jié)點在open中
 Integer newCompute=path.get(nearest.getName())+childs.get(child);
 if(path.get(child.getName())>newCompute){//之前設置的距離大于新計算出來的距離
  path.put(child.getName(), newCompute);
  pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
 }
 }
 }
 computePath(start);//重復執(zhí)行自己,確保所有子節(jié)點被遍歷
 computePath(nearest);//向外一層層遞歸,直至所有頂點被遍歷
 }
 public void printPathInfo(){
 Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
 for(Map.Entry<String, String> pathInfo:pathInfos){
 System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
 }
 }
 /**
 * 獲取與node最近的子節(jié)點
 */
 private Node getShortestPath(Node node){
 Node res=null;
 int minDis=Integer.MAX_VALUE;
 Map<Node,Integer> childs=node.getChild();
 for(Node child:childs.keySet()){
 if(open.contains(child)){
 int distance=childs.get(child);
 if(distance<minDis){
  minDis=distance;
  res=child;
 }
 }
 }
 return res;
 }
}

Main用于測試Dijkstra對象

public class Main {
 public static void main(String[] args) {
 Dijkstra test=new Dijkstra();
 Node start=test.init();
 test.computePath(start);
 test.printPathInfo();
 }
}

打印輸出如下：

D:A->D
E:A->F->E
F:A->F
G:A->C->G
B:A->B
C:A->C
H:A->B->H

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

Java中編譯期異常和運行期異常的區(qū)別解析
Java中的異常分為運行期異常（RuntimeException）和編譯期異常（CheckedException）,前者不強制處理,后者必須顯式處理,本文介紹Java中編譯期異常和運行期異常的區(qū)別,感興趣的朋友一起看看吧
2025-02-02
淺談Java線程間通信方式
這篇文章主要為大家詳細介紹了Java線程間的通信方式，以代碼結合文字的方式來討論線程間的通信，感興趣的朋友可以參考一下
2021-11-11
關于ArrayList初始創(chuàng)建設定長度問題
在使用ArrayList時,初始化長度并不等同于直接設定數(shù)組大小,如通過構造函數(shù)指定長度,僅僅是在內(nèi)部開辟了相應的存儲空間,并不會改變ArrayList的實際元素個數(shù),即size屬性仍然為0,因此,嘗試直接訪問未實際添加元素的位置會引發(fā)異常
2024-11-11
Spring?Boot指標監(jiān)控及日志管理示例詳解
Spring Boot Actuator可以幫助程序員監(jiān)控和管理SpringBoot應用，比如健康檢查、內(nèi)存使用情況統(tǒng)計、線程使用情況統(tǒng)計等，這篇文章主要介紹了Spring?Boot指標監(jiān)控及日志管理,需要的朋友可以參考下
2023-11-11
輕松掌握Java命令模式
這篇文章主要幫助大家輕松掌握Java命令模式,具有一定的參考價值，感興趣的小伙伴們可以參考一下
2016-09-09
Java程序快速合并多個Word(docx)文檔
這篇文章主要為大家介紹了如何使用Java程序快速合并多個Word(docx)文檔實現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2023-05-05
Jenkin郵件收發(fā)實現(xiàn)原理及過程詳解
這篇文章主要介紹了Jenkin郵件收發(fā)實現(xiàn)原理及過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-09-09
spring boot打包成war包的頁面如何存放
這篇文章主要介紹了spring boot打包成war包的頁面該放到哪里，很多朋友對這個問題都很疑惑，今天小編給大家分享一篇教程,需要的朋友可以參考下
2019-11-11
在Java中自由塊的執(zhí)行順序
java中的自由塊分為靜態(tài)的自由塊和非靜態(tài)的自由塊。非靜態(tài)自由塊的執(zhí)行時間是：在執(zhí)行構造函數(shù)之前。靜態(tài)自由塊的執(zhí)行時間是：class文件加載時執(zhí)行。
2013-04-04
Java構造函數(shù)與普通函數(shù)用法詳解
本篇文章給大家詳細講述了Java構造函數(shù)與普通函數(shù)用法以及相關知識點，對此有興趣的朋友可以參考學習下。
2018-03-03