欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2019年01月17日 17:13:20   作者:jake_gogo  
這篇文章主要為大家詳細介紹了java實現(xiàn)dijkstra最短路徑尋路算法,具有一定的參考價值,感興趣的小伙伴們可以參考一下

【引用】迪杰斯特拉(Dijkstra)算法是典型最短路徑算法,用于計算一個節(jié)點到其他節(jié)點的最短路徑。 

它的主要特點是以起始點為中心向外層層擴展(廣度優(yōu)先搜索思想),直到擴展到終點為止。

基本思想

通過Dijkstra計算圖G中的最短路徑時,需要指定起點s(即從頂點s開始計算)。

此外,引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(以及相應的最短路徑長度),而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)。

初始時,S中只有起點s;U中是除s之外的頂點,并且U中頂點的路徑是"起點s到該頂點的路徑"。然后,從U中找出路徑最短的頂點,并將其加入到S中;接著,更新U中的頂點和頂點對應的路徑。 然后,再從U中找出路徑最短的頂點,并將其加入到S中;接著,更新U中的頂點和頂點對應的路徑。 ... 重復該操作,直到遍歷完所有頂點。

操作步驟

(1) 初始時,S只包含起點s;U包含除s外的其他頂點,且U中頂點的距離為"起點s到該頂點的距離"[例如,U中頂點v的距離為(s,v)的長度,然后s和v不相鄰,則v的距離為∞]。

(2) 從U中選出"距離最短的頂點k",并將頂點k加入到S中;同時,從U中移除頂點k。

(3) 更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離,是由于上一步中確定了k是求出最短路徑的頂點,從而可以利用k來更新其它頂點的距離;例如,(s,v)的距離可能大于(s,k)+(k,v)的距離。

(4) 重復步驟(2)和(3),直到遍歷完所有頂點。

得益于csdn另外一篇博客的算法,我對此做了一些改進。

構(gòu)建地圖:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
 
/**
 * 地圖
 * @author jake
 * @date 2014-7-26-下午10:40:10
 * @param <T> 節(jié)點主鍵
 */
public class Maps<T> {
 
 /**
 * 所有的節(jié)點集合
 * 節(jié)點Id - 節(jié)點
 */
 private Map<T, Node<T>> nodes = new HashMap<T, Node<T>>();
 
 /**
 * 地圖構(gòu)建器
 * 
 * @author jake
 * @date 2014-7-26-下午9:47:44
 */
 public static class MapBuilder<T> {
 
 /**
  * map實例
  */
 private Maps<T> map = new Maps<T>();
 
 /**
  * 構(gòu)造MapBuilder
  * 
  * @return MapBuilder
  */
 public MapBuilder<T> create() {
  return new MapBuilder<T>();
 }
 
 /**
  * 添加節(jié)點
  * 
  * @param node 節(jié)點
  * @return
  */
 public MapBuilder<T> addNode(Node<T> node) {
  map.nodes.put(node.getId(), node);
  return this;
 }
 
 /**
  * 添加路線
  * 
  * @param node1Id 節(jié)點Id
  * @param node2Id 節(jié)點Id
  * @param weight 權(quán)重
  * @return
  */
 public MapBuilder<T> addPath(T node1Id, T node2Id, int weight) {
  Node<T> node1 = map.nodes.get(node1Id);
  if (node1 == null) {
  throw new RuntimeException("無法找到節(jié)點:" + node1Id);
  }
 
  Node<T> node2 = map.nodes.get(node2Id);
  if (node2 == null) {
  throw new RuntimeException("無法找到節(jié)點:" + node2Id);
  }
 
  node1.getChilds().put(node2, weight);
  node2.getChilds().put(node1, weight);
  return this;
 }
 
 /**
  * 構(gòu)建map
  * @return map
  */
 public Maps<T> build() {
  return this.map;
 }
 
 }
 
 /**
 * 節(jié)點
 * 
 * @author jake
 * @date 2014-7-26-下午9:51:31
 * @param <T> 節(jié)點主鍵類型
 */
 public static class Node<T> {
 
 /**
  * 節(jié)點主鍵
  */
 private T id;
 
 /**
  * 節(jié)點聯(lián)通路徑
  * 相連節(jié)點 - 權(quán)重
  */
 private Map<Node<T>, Integer> childs = new HashMap<Node<T>, Integer>();
 
 /**
  * 構(gòu)造方法
  * @param id 節(jié)點主鍵
  */
 public Node(T id) {
  this.id = id;
 }
 
 /**
  * 獲取實例
  * @param id 主鍵
  * @return
  */
 public static <T> Node<T> valueOf(T id) {
  return new Node<T>(id);
 }
 
 /**
  * 是否有效
  * 用于動態(tài)變化節(jié)點的可用性
  * @return
  */
 public boolean validate() {
  return true;
 }
 
 
 public T getId() {
  return id;
 }
 
 public void setId(T id) {
  this.id = id;
 }
 
 public Map<Node<T>, Integer> getChilds() {
  return childs;
 }
 
 protected void setChilds(Map<Node<T>, Integer> childs) {
  this.childs = childs;
 }
 
 @Override
 public String toString() {
  StringBuilder sb = new StringBuilder();
  sb.append(this.id).append("[");
  for (Iterator<Entry<Node<T>, Integer>> it = childs.entrySet().iterator(); it.hasNext();) {
  Entry<Node<T>, Integer> next = it.next();
  sb.append(next.getKey().getId()).append("=").append(next.getValue());
  if (it.hasNext()) {
   sb.append(",");
  }
  }
  sb.append("]");
  return sb.toString();
 }
 
 }
 
 /**
 * 獲取地圖的無向圖節(jié)點
 * @return 節(jié)點Id - 節(jié)點
 */
 public Map<T, Node<T>> getNodes() {
 return nodes;
 }
 
}

開始尋路:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
 
import com.my9yu.sanguohun2.utils.dijkstra.Maps.MapBuilder;
 
/**
 * 迪杰斯特拉(Dijkstra)圖最短路徑搜索算法
 * <br/>每次開始新的搜索需要創(chuàng)建此類對象
 * @param <T> 節(jié)點的主鍵類型
 * @author jake
 * @date 2014-7-26-下午9:45:07
 */
public class MapSearcher<T> {
 
 /**
 * 最短路徑搜索結(jié)果類
 * @author jake
 * @date 2014-7-27-下午3:55:11
 * @param <T> 節(jié)點的主鍵類型
 */
 public static class SearchResult<T> {
 /**
  * 最短路徑結(jié)果
  */
 List<T> path;
 /**
  * 最短距離
  */
 Integer distance;
 
 /**
  * 獲取實例
  * @param path 最短路徑結(jié)果
  * @param distance 最短路徑距離
  * @return
  */
 protected static <T> SearchResult<T> valueOf(List<T> path, Integer distance) {
  SearchResult<T> r = new SearchResult<T>();
  r.path = path;
  r.distance = distance;
  return r;
 }
 
 public List<T> getPath() {
  return path;
 }
 public Integer getDistance() {
  return distance;
 }
 
 @Override
 public String toString() {
  StringBuffer sb = new StringBuffer();
  sb.append("path:");
  for(Iterator<T> it = this.path.iterator(); it.hasNext();) {
  sb.append(it.next());
  if(it.hasNext()) {
   sb.append("->");
  }
  }
  sb.append("\n").append("distance:").append(distance);
  return sb.toString();
 }
 
 }
 
 /**
 * 地圖對象
 */
 Maps<T> map;
 /**
 * 開始節(jié)點
 */
 Maps.Node<T> startNode;
 /**
 * 結(jié)束節(jié)點
 */
 Maps.Node<T> targetNode;
 /**
 * 開放的節(jié)點
 */
 Set<Maps.Node<T>> open = new HashSet<Maps.Node<T>>();
 /**
 * 關(guān)閉的節(jié)點
 */
 Set<Maps.Node<T>> close = new HashSet<Maps.Node<T>>();
 /**
 * 最短路徑距離
 */
 Map<Maps.Node<T>, Integer> path = new HashMap<Maps.Node<T>, Integer>();
 /**
 * 最短路徑
 */
 Map<T, List<T>> pathInfo = new HashMap<T, List<T>>();
 
 /**
 * 初始化起始點
 * <br/>初始時,S只包含起點s;U包含除s外的其他頂點,且U中頂點的距離為"起點s到該頂點的距離"
 * [例如,U中頂點v的距離為(s,v)的長度,然后s和v不相鄰,則v的距離為∞]。
 * @param source 起始節(jié)點的Id
 * @param map 全局地圖
 * @param closeSet 已經(jīng)關(guān)閉的節(jié)點列表
 * @return
 */
 @SuppressWarnings("unchecked")
 public Maps.Node<T> init(T source, Maps<T> map, Set<T> closeSet) {
 
 Map<T, Maps.Node<T>> nodeMap = map.getNodes();
 Maps.Node<T> startNode = nodeMap.get(source);
 //將初始節(jié)點放到close
 close.add(startNode);
 //將其他節(jié)點放到open
 for(Maps.Node<T> node : nodeMap.values()) {
  if(!closeSet.contains(node.getId()) && !node.getId().equals(source)) {
  this.open.add(node);
  }
 }
 
 // 初始路徑
 T startNodeId = startNode.getId();
 for(Entry<Maps.Node<T>, Integer> entry : startNode.getChilds().entrySet()) {
  Maps.Node<T> node = entry.getKey();
  if(open.contains(node)) {
  T nodeId = node.getId();
  path.put(node, entry.getValue());
  pathInfo.put(nodeId, new ArrayList<T>(Arrays.asList(startNodeId, nodeId)));
  }
 }
 
 for(Maps.Node<T> node : nodeMap.values()) {
  if(open.contains(node) && !path.containsKey(node)) {
  path.put(node, Integer.MAX_VALUE);
  pathInfo.put(node.getId(), new ArrayList<T>(Arrays.asList(startNodeId)));
  }
 }
 this.startNode = startNode;
 this.map = map;
 return startNode;
 }
 
 
 /**
 * 遞歸Dijkstra
 * @param start 已經(jīng)選取的最近節(jié)點
 */
 protected void computePath(Maps.Node<T> start) {
 // 從U中選出"距離最短的頂點k",并將頂點k加入到S中;同時,從U中移除頂點k。
 Maps.Node<T> nearest = getShortestPath(start);
 if (nearest == null) {
  return;
 }
 //更新U中各個頂點到起點s的距離。
 //之所以更新U中頂點的距離,是由于上一步中確定了k是求出最短路徑的頂點,從而可以利用k來更新其它頂點的距離;
 //例如,(s,v)的距離可能大于(s,k)+(k,v)的距離。
 close.add(nearest);
 open.remove(nearest);
 //已經(jīng)找到結(jié)果
 if(nearest == this.targetNode) {
  return;
 }
 Map<Maps.Node<T>, Integer> childs = nearest.getChilds();
 for (Maps.Node<T> child : childs.keySet()) {
  if (open.contains(child)) {// 如果子節(jié)點在open中
  Integer newCompute = path.get(nearest) + childs.get(child);
  if (path.get(child) > newCompute) {// 之前設置的距離大于新計算出來的距離
   path.put(child, newCompute);
 
   List<T> path = new ArrayList<T>(pathInfo.get(nearest.getId()));
   path.add(child.getId());
   pathInfo.put(child.getId(), path);
  }
  }
 }
// computePath(start);// 重復執(zhí)行自己,確保所有子節(jié)點被遍歷
 computePath(nearest);// 向外一層層遞歸,直至所有頂點被遍歷
 }
 
 /**
 * 獲取與node最近的子節(jié)點
 */
 private Maps.Node<T> getShortestPath(Maps.Node<T> node) {
 Maps.Node<T> res = null;
 int minDis = Integer.MAX_VALUE;
 for (Maps.Node<T> entry : path.keySet()) {
  if (open.contains(entry)) {
  int distance = path.get(entry);
  if (distance < minDis) {
   minDis = distance;
   res = entry;
  }
  }
 }
 return res;
 }
 
 /**
 * 獲取到目標點的最短路徑
 * 
 * @param target
 *      目標點
 * @return
 */
 public SearchResult<T> getResult(T target) {
 Maps.Node<T> targetNode = this.map.getNodes().get(target);
 if(targetNode == null) {
  throw new RuntimeException("目標節(jié)點不存在!");
 }
 this.targetNode = targetNode;
 //開始計算
 this.computePath(startNode);
 return SearchResult.valueOf(pathInfo.get(target), path.get(targetNode));
 }
 
 /**
 * 打印出所有點的最短路徑
 */
 public void printPathInfo() {
 Set<Map.Entry<T, List<T>>> pathInfos = pathInfo.entrySet();
 for (Map.Entry<T, List<T>> pathInfo : pathInfos) {
  System.out.println(pathInfo.getKey() + ":" + pathInfo.getValue());
 }
 }
 
 
 /**
 * 測試方法
 */
 @org.junit.Test
 public void test() {
 
 MapBuilder<String> mapBuilder = new Maps.MapBuilder<String>().create();
 //構(gòu)建節(jié)點
 mapBuilder.addNode(Maps.Node.valueOf("A"));
 mapBuilder.addNode(Maps.Node.valueOf("B"));
 mapBuilder.addNode(Maps.Node.valueOf("C"));
 mapBuilder.addNode(Maps.Node.valueOf("D"));
 mapBuilder.addNode(Maps.Node.valueOf("E"));
 mapBuilder.addNode(Maps.Node.valueOf("F"));
 mapBuilder.addNode(Maps.Node.valueOf("G"));
 mapBuilder.addNode(Maps.Node.valueOf("H"));
 mapBuilder.addNode(Maps.Node.valueOf("I"));
 //構(gòu)建路徑
 mapBuilder.addPath("A", "B", 1);
 mapBuilder.addPath("A", "F", 2);
 mapBuilder.addPath("A", "D", 4);
 mapBuilder.addPath("A", "C", 1);
 mapBuilder.addPath("A", "G", 5);
 mapBuilder.addPath("C", "G", 3);
 mapBuilder.addPath("G", "H", 1);
 mapBuilder.addPath("H", "B", 4);
 mapBuilder.addPath("B", "F", 2);
 mapBuilder.addPath("E", "F", 1);
 mapBuilder.addPath("D", "E", 1);
 mapBuilder.addPath("H", "I", 1);
 mapBuilder.addPath("C", "I", 1);
 
 //構(gòu)建全局Map
 Maps<String> map = mapBuilder.build();
 
 //創(chuàng)建路徑搜索器(每次搜索都需要創(chuàng)建新的MapSearcher)
 MapSearcher<String> searcher = new MapSearcher<String>();
 //創(chuàng)建關(guān)閉節(jié)點集合
 Set<String> closeNodeIdsSet = new HashSet<String>();
 closeNodeIdsSet.add("C");
 //設置初始節(jié)點
 searcher.init("A", map, closeNodeIdsSet);
 //獲取結(jié)果
 SearchResult<String> result = searcher.getResult("G");
 System.out.println(result);
 //test.printPathInfo();
 }
 
}

根據(jù)算法的原理可知,getShortestPath是獲取open集合里面目前更新的距離離起始點最短路徑的節(jié)點?;趶V度優(yōu)先原則,可以避免路徑權(quán)重不均導致錯尋的情況。

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

相關(guān)文章

  • Java基于JDBC連接數(shù)據(jù)庫及顯示數(shù)據(jù)操作示例

    Java基于JDBC連接數(shù)據(jù)庫及顯示數(shù)據(jù)操作示例

    這篇文章主要介紹了Java基于JDBC連接數(shù)據(jù)庫及顯示數(shù)據(jù)操作,結(jié)合實例形式分析了Java使用jdbc進行mysql數(shù)據(jù)庫連接與數(shù)據(jù)讀取、顯示等相關(guān)操作技巧,需要的朋友可以參考下
    2018-06-06
  • JSP代碼實現(xiàn) 金字塔(倒置)示例

    JSP代碼實現(xiàn) 金字塔(倒置)示例

    這篇文章主要介紹了JSP代碼實現(xiàn) 金字塔(倒置)示例,需要的朋友可以參考下
    2014-02-02
  • Java中的ReadWriteLock讀寫鎖詳解

    Java中的ReadWriteLock讀寫鎖詳解

    這篇文章主要介紹了Java中的ReadWriteLock讀寫鎖詳解,ReadWriteLock也是一個接口,提供了readLock和writeLock兩種鎖的操作機制,一個資源可以被多個線程同時讀,或者被一個線程寫,但是不能同時存在讀和寫線程,需要的朋友可以參考下
    2023-12-12
  • Springboot 自定義校驗代碼實例

    Springboot 自定義校驗代碼實例

    這篇文章主要介紹了Springboot 自定義校驗代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-11-11
  • java用arraycopy實現(xiàn)多擊事件

    java用arraycopy實現(xiàn)多擊事件

    這篇文章主要介紹了java用arraycopy實現(xiàn)多擊事件的多種方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-11-11
  • Java容器類源碼詳解 Deque與ArrayDeque

    Java容器類源碼詳解 Deque與ArrayDeque

    這篇文章主要介紹了Java容器類源碼詳解 Deque與ArrayDeque,Deque 接口繼承自 Queue接口,但 Deque 支持同時從兩端添加或移除元素,因此又被成為雙端隊列。,需要的朋友可以參考下
    2019-06-06
  • 使用Post方法模擬登陸爬取網(wǎng)頁的實現(xiàn)方法

    使用Post方法模擬登陸爬取網(wǎng)頁的實現(xiàn)方法

    下面小編就為大家?guī)硪黄褂肞ost方法模擬登陸爬取網(wǎng)頁的實現(xiàn)方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-03-03
  • 淺談Java變量賦值運算符及相關(guān)實例

    淺談Java變量賦值運算符及相關(guān)實例

    這篇文章主要介紹了Java賦值運算符的一些知識,需要的朋友可以參考下。
    2017-09-09
  • java異或加密算法

    java異或加密算法

    這篇文章主要介紹了java異或加密算法,有需要的朋友可以參考一下
    2013-12-12
  • Java下載文件的4種方式總結(jié)

    Java下載文件的4種方式總結(jié)

    這篇文章主要給大家總結(jié)介紹了關(guān)于Java下載文件的4種方式,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-01-01

最新評論