熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

JAVA編程語言程序開發技術Dijkstra

2013-11-23 19:02:01  來源: Java核心技術 

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

  Dijkstra一般的表述通常有兩種方式一種用永久和臨時標號方式一種是用OPEN CLOSE表方式

  用OPENCLOSE表的方式其采用的是貪心法的算法策略大概過程如下

  聲明兩個集合open和closeopen用於存儲未遍歷的節點close用來存儲已遍歷的節點

  初始階段將初始節點放入close其他所有節點放入open

  以初始節點為中心向外一層層遍歷獲取離指定節點最近的子節點放入close並從新計算路徑直至close包含所有子節點

  代碼實例如下

  Node對象用於封裝節點信息包括名字和子節點

  [java]

  public class Node {

  private String name;

  private Map<NodeInteger> child=new HashMap<NodeInteger>()

  public Node(String name){

  thisname=name;

  }

  public String getName() {

  return name;

  }

  public void setName(String name) {

  thisname = name;

  }

  public Map<Node Integer> getChild() {

  return child;

  }

  public void setChild(Map<Node Integer> child) {

  thischild = child;

  }

  }

  MapBuilder用於初始化數據源返回圖的起始節點

  [java]

  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

  nodeAgetChild()put(nodeB

  nodeAgetChild()put(nodeC

  nodeAgetChild()put(nodeD

  nodeAgetChild()put(nodeG

  nodeAgetChild()put(nodeF

  nodeBgetChild()put(nodeA

  nodeBgetChild()put(nodeF

  nodeBgetChild()put(nodeH

  nodeCgetChild()put(nodeA

  nodeCgetChild()put(nodeG

  nodeDgetChild()put(nodeA

  nodeDgetChild()put(nodeE

  nodeEgetChild()put(nodeD

  nodeEgetChild()put(nodeF

  nodeFgetChild()put(nodeE

  nodeFgetChild()put(nodeB

  nodeFgetChild()put(nodeA

  nodeGgetChild()put(nodeC

  nodeGgetChild()put(nodeA

  nodeGgetChild()put(nodeH

  nodeHgetChild()put(nodeB

  nodeHgetChild()put(nodeG

  openadd(nodeB)

  openadd(nodeC)

  openadd(nodeD)

  openadd(nodeE)

  openadd(nodeF)

  openadd(nodeG)

  openadd(nodeH)

  closeadd(nodeA)

  return nodeA;

  }

  }

  圖的結構如下圖所示

  

  Dijkstra對象用於計算起始節點到所有其他節點的最短路徑

  [java]

  public class Dijkstra {

  Set<Node> open=new HashSet<Node>()

  Set<Node> close=new HashSet<Node>()

  Map<StringInteger> path=new HashMap<StringInteger>()//封裝路徑距離

  Map<StringString> pathInfo=new HashMap<StringString>()//封裝路徑信息

  public Node init(){

  //初始路徑因沒有A>E這條路徑所以path(E)設置為IntegerMAX_VALUE

  pathput(B

  pathInfoput(B A>B

  pathput(C

  pathInfoput(C A>C

  pathput(D

  pathInfoput(D A>D

  pathput(E IntegerMAX_VALUE)

  pathInfoput(E A

  pathput(F

  pathInfoput(F A>F

  pathput(G

  pathInfoput(G A>G

  pathput(H IntegerMAX_VALUE)

  pathInfoput(H A

  //將初始節點放入close其他節點放入open

  Node start=new MapBuilder()build(openclose)

  return start;

  }

  public void computePath(Node start){

  Node nearest=getShortestPath(start)//取距離start節點最近的子節點放入close

  if(nearest==null){

  return;

  }

  closeadd(nearest)

  openremove(nearest)

  Map<NodeInteger> childs=nearestgetChild()

  for(Node child:childskeySet()){

  if(ntains(child)){//如果子節點在open中

  Integer newCompute=pathget(nearestgetName())+childsget(child)

  if(pathget(childgetName())>newCompute){//之前設置的距離大於新計算出來的距離

  pathput(childgetName() newCompute)

  pathInfoput(childgetName() pathInfoget(nearestgetName())+>+childgetName())

  }

  }

  }

  computePath(start)//重復執行自己確保所有子節點被遍歷

  computePath(nearest)//向外一層層遞歸直至所有頂點被遍歷

  }

  public void printPathInfo(){

  Set<MapEntry<String String》 pathInfos=pathInfoentrySet()

  for(MapEntry<String String> pathInfo:pathInfos){

  Systemoutprintln(pathInfogetKey()+:+pathInfogetValue())

  }

  }

  /**

  * 獲取與node最近的子節點

  */

  private Node getShortestPath(Node node){

  Node res=null;

  int minDis=IntegerMAX_VALUE;

  Map<NodeInteger> childs=nodegetChild()

  for(Node child:childskeySet()){

  if(ntains(child)){

  int distance=childsget(child)

  if(distance<minDis){

  minDis=distance;

  res=child;

  }

  }

  }

  return res;

  }

  }

  Main用於測試Dijkstra對象

  [java]

  public class Main {

  public static void main(String[] args) {

  Dijkstra test=new Dijkstra()

  Node start=testinit()

  putePath(start)

  testprintPathInfo()

  }

  }

  打印輸出如下

  D:A>D

  E:A>F>E

  F:A>F

  G:A>C>G

  B:A>B

  C:A>C

  H:A>B>H


From:http://tw.wingwit.com/Article/program/Java/hx/201311/26170.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.