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

　　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