java實(shí)現(xiàn)Dijkstra最短路徑算法
任務(wù)描述:在一個無向圖中,獲取起始節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑描述
Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法,用于計(jì)算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止。
Dijkstra一般的表述通常有兩種方式,一種用永久和臨時(shí)標(biāo)號方式,一種是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式,其采用的是貪心法的算法策略,大概過程如下:
1.聲明兩個集合,open和close,open用于存儲未遍歷的節(jié)點(diǎn),close用來存儲已遍歷的節(jié)點(diǎn)
2.初始階段,將初始節(jié)點(diǎn)放入close,其他所有節(jié)點(diǎn)放入open
3.以初始節(jié)點(diǎn)為中心向外一層層遍歷,獲取離指定節(jié)點(diǎn)最近的子節(jié)點(diǎn)放入close并從新計(jì)算路徑,直至close包含所有子節(jié)點(diǎn)
代碼實(shí)例如下:
Node對象用于封裝節(jié)點(diǎn)信息,包括名字和子節(jié)點(diǎn)
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é)點(diǎn)
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; } }
圖的結(jié)構(gòu)如下圖所示:
Dijkstra對象用于計(jì)算起始節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑
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)設(shè)置為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é)點(diǎn)放入close,其他節(jié)點(diǎn)放入open Node start=new MapBuilder().build(open,close); return start; } public void computePath(Node start){ Node nearest=getShortestPath(start);//取距離start節(jié)點(diǎn)最近的子節(jié)點(diǎn),放入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é)點(diǎn)在open中 Integer newCompute=path.get(nearest.getName())+childs.get(child); if(path.get(child.getName())>newCompute){//之前設(shè)置的距離大于新計(jì)算出來的距離 path.put(child.getName(), newCompute); pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName()); } } } computePath(start);//重復(fù)執(zhí)行自己,確保所有子節(jié)點(diǎn)被遍歷 computePath(nearest);//向外一層層遞歸,直至所有頂點(diǎn)被遍歷 } 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é)點(diǎn) */ 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)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
SpringBoot定時(shí)任務(wù)設(shè)計(jì)之時(shí)間輪案例原理詳解
這篇文章主要為大家介紹了SpringBoot定時(shí)任務(wù)設(shè)計(jì)之時(shí)間輪案例原理詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-10-10springboot實(shí)現(xiàn)string轉(zhuǎn)json json里面帶數(shù)組
這篇文章主要介紹了springboot實(shí)現(xiàn)string轉(zhuǎn)json json里面帶數(shù)組,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-06-06Spring boot 在idea中添加熱部署插件的圖文教程
這篇文章主要介紹了Spring boot 在idea中添加熱部署插件的圖文教程,本文通過圖文并茂的形式給大家展示具體步驟,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-10-10詳解Spring Data JPA動態(tài)條件查詢的寫法
本篇文章主要介紹了Spring Data JPA動態(tài)條件查詢的寫法 ,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-06-06通過實(shí)例了解JavaBean開發(fā)及使用過程解析
這篇文章主要介紹了通過實(shí)例了解JavaBean開發(fā)及使用過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08