李采潭一级毛片高清中文字幕,亚洲欧洲久久精品,人人插人人舔,91视频专区,杨幂不雅视频bt,美女视频 新婚之夜,日本美女在线视频网站免费

技術(shù)中心

這里象征著我們的態(tài)度和能力

Dijkstra算法
作者:lx    來源:本站原創(chuàng)    發(fā)布時間:2015-03-03      瀏覽次數(shù):13832
分享到:

       Dijkstra算法:用于計算圖中某一點到其他各點的最短路徑。關(guān)于Dijkstra算法的說明可以參考數(shù)據(jù)結(jié)構(gòu)相關(guān)書籍。

       Dijkstra算法設(shè)計的類:
       1. Node        節(jié)點類

       2. Edge        邊類
       3. Graph       圖類
       4. Dijkstra     Dijkstra算法類

       Node類:

       Java代碼  

1. package com.sabrina.dijkstra;  

2.   

3. import java.util.ArrayList;  

4. import java.util.List;  

5.   

6. public class Node {  

7.   

8.     // 節(jié)點編號  

9.     private String id;  

10.     // 從當前節(jié)點出發(fā)的邊的信息列表  

11.     private List outEdges;  

12.      

13.     public Node(String id) {  

14.         this.id = id;  

15.         outEdges = new ArrayList();  

16.     }  

17.      

18.     public void addOutEdge(Edge edge) {  

19.         if(edge != null)  

20.             outEdges.add(edge);  

21.     }  

22.   

23.     public String getId() {  

24.         return id;  

25.     }  

26.   

27.     public void setId(String id) {  

28.         this.id = id;  

29.     }  

30.   

31.     public List getOutEdges() {  

32.         return outEdges;  

33.     }  

34.   

35.     public void setOutEdges(List outEdges) {  

36.         this.outEdges = outEdges;  

37.     }  

38. }  

 

       Edge類:

       Java代碼  

1. package com.sabrina.dijkstra;  

2.   

3. public class Edge {  

4.   

5.     // 邊的起始節(jié)點編號  

6.     private String startNodeID;  

7.     // 邊的末尾節(jié)點編號  

8.     private String endNodeID;  

9.     // 邊的權(quán)值  

10.     private double weight;  

11.      

12.     public String getStartNodeID() {  

13.         return startNodeID;  

14.     }  

15.     public void setStartNodeID(String startNodeID) {  

16.         this.startNodeID = startNodeID;  

17.     }  

18.     public String getEndNodeID() {  

19.         return endNodeID;  

20.     }  

21.     public void setEndNodeID(String endNodeID) {  

22.         this.endNodeID = endNodeID;  

23.     }  

24.     public double getWeight() {  

25.         return weight;  

26.     }  

27.     public void setWeight(double weight) {  

28.         this.weight = weight;  

29.     }  

30. }  

 

       Graph類:

 

       Java代碼  

1. package com.sabrina.dijkstra;  

2.   

3. import java.util.ArrayList;  

4. import java.util.List;  

5.   

6. public class Graph {  

7.   

8.     // 圖中的節(jié)點列表  

9.     public List nodeList = null;  

10.   

11.     public Graph() {  

12.         nodeList = new ArrayList();  

13.     }  

14.   

15.     public List getNodeList() {  

16.         return nodeList;  

17.     }  

18.   

19.     // initialize  

20.     public void init() {  

21.         // ************************ Node A ***********************  

22.         Node aNode = new Node("A");  

23.         nodeList.add(aNode);  

24.         // A -> B  

25.         Edge a2bEdge = new Edge();  

26.         a2bEdge.setStartNodeID(aNode.getId());  

27.         a2bEdge.setEndNodeID("B");  

28.         a2bEdge.setWeight(10);  

29.         aNode.addOutEdge(a2bEdge);  

30.         // A -> C  

31.         Edge a2cEdge = new Edge();  

32.         a2cEdge.setStartNodeID(aNode.getId());  

33.         a2cEdge.setEndNodeID("C");  

34.         a2cEdge.setWeight(20);  

35.         aNode.addOutEdge(a2cEdge);  

36.         // A -> E  

37.         Edge a2eEdge = new Edge();  

38.         a2eEdge.setStartNodeID(aNode.getId());  

39.         a2eEdge.setEndNodeID("E");  

40.         a2eEdge.setWeight(30);  

41.         aNode.addOutEdge(a2eEdge);  

42.   

43.         // ************************ Node B ***********************  

44.         Node bNode = new Node("B");  

45.         nodeList.add(bNode);  

46.         // B -> C  

47.         Edge b2cEdge = new Edge();  

48.         b2cEdge.setStartNodeID(bNode.getId());  

49.         b2cEdge.setEndNodeID("C");  

50.         b2cEdge.setWeight(5);  

51.         bNode.addOutEdge(b2cEdge);  

52.         // B -> E  

53.         Edge b2eEdge = new Edge();  

54.         b2eEdge.setStartNodeID(bNode.getId());  

55.         b2eEdge.setEndNodeID("E");  

56.         b2eEdge.setWeight(10);  

57.         bNode.addOutEdge(b2eEdge);  

58.   

59.         // ************************ Node C ***********************  

60.         Node cNode = new Node("C");  

61.         nodeList.add(cNode);  

62.         // C -> D  

63.         Edge c2dEdge = new Edge();  

64.         c2dEdge.setStartNodeID(cNode.getId());  

65.         c2dEdge.setEndNodeID("D");  

66.         c2dEdge.setWeight(30);  

67.         cNode.addOutEdge(c2dEdge);  

68.          

69.         // ************************ Node D ***********************  

70.         Node dNode = new Node("D");  

71.         nodeList.add(dNode);  

72.          

73.         // ************************ Node E ***********************  

74.         Node eNode = new Node("E");  

75.         nodeList.add(eNode);  

76.         // E -> D  

77.         Edge e2dEdge = new Edge();  

78.         e2dEdge.setStartNodeID(eNode.getId());  

79.         e2dEdge.setEndNodeID("D");  

80.         e2dEdge.setWeight(20);  

81.         eNode.addOutEdge(e2dEdge);  

82.          

83.     }  

84. }  

 

       Dijkstra類:

       Java代碼  

1. package com.sabrina.dijkstra;  

2.   

3. import java.util.ArrayList;  

4. import java.util.HashMap;  

5. import java.util.Iterator;  

6. import java.util.List;  

7. import java.util.Map;  

8.   

9. public class Dijkstra {  

10.   

11.     // 起始節(jié)點編號  

12.     private String startNodeID;  

13.     // 未被處理的節(jié)點集合  

14.     private List sourceNodeIDList = null;  

15.     // 已被處理的節(jié)點集合  

16.     private List desNodeIDList = null;  

17.   

18.     // 節(jié)點編號   起始節(jié)點與當前節(jié)點之間的最短路徑 的映射關(guān)系  

19.     private Map nodeidShortestRouteMapping = null;  

20.     // 節(jié)點編號   起始節(jié)點到當前節(jié)點之間的最短路徑  上一跳節(jié)點編號 的映射關(guān)系  

21.     private Map nodeidLastNodeidMapping = null;  

22.     // 節(jié)點編號   節(jié)點對象 映射關(guān)系  

23.     private Map idNodeMapping = null;  

24.      

25.     public Dijkstra(Graph graph, String startNodeID) {  

26.         this.startNodeID = startNodeID;  

27.          

28.         // 初始化  

29.         sourceNodeIDList = new ArrayList();  

30.         desNodeIDList = new ArrayList();  

31.         nodeidShortestRouteMapping = new HashMap();  

32.         nodeidLastNodeidMapping = new HashMap();  

33.         idNodeMapping = new HashMap();  

34.          

35.         for(Node node : graph.getNodeList()) {  

36.             if(node.getId().equals(startNodeID)) {  

37.                 desNodeIDList.add(startNodeID);  

38.                 // 起始節(jié)點到起始節(jié)點的最短路徑長度為0  

39.                 nodeidShortestRouteMapping.put(startNodeID, 0d);  

40.             }  

41.             else {  

42.                 sourceNodeIDList.add(node.getId());  

43.                 // 非起始節(jié)點到起始節(jié)點的最短路徑長度為 無窮大  

44.                 nodeidShortestRouteMapping.put(node.getId(), Double.MAX_VALUE);  

45.             }  

46.             // 設(shè)置到節(jié)點最短路徑的上一跳節(jié)點為null  

47.             nodeidLastNodeidMapping.put(node.getId(), null);  

48.             idNodeMapping.put(node.getId(), node);  

49.         }  

50.     }  

51.      

52.     public void start() {  

53.         Node nextNode = null;  

54.         Node currentNode = null;  

55.         String nextNodeID = "";  

56.         do {  

57.             if(nextNode == null) {  

58.                 currentNode = idNodeMapping.get(startNodeID);  

59.             }  

60.             else {  

61.                 currentNode = nextNode;  

62.             }  

63.             nextNodeID = getNextNode(currentNode);  

64.              

65.             nextNode = idNodeMapping.get(nextNodeID);  

66.             System.out.println("nextNode.id:" + nextNode.getId());  

67.              

68.             sourceNodeIDList.remove(nextNode.getId());  

69.             System.out.println("sourceNodeIDList:" + sourceNodeIDList.toString());  

70.         } while(sourceNodeIDList.size() > 0);  

71.     }  

72.      

73.      

74.     public String getNextNode(Node currentNode) {  

75.         System.out.println("============= currentNode.id: " + currentNode.getId() + " =============");  

76.         double shortestPath = Double.MAX_VALUE;  

77.         String nextNodeID = "";  

78.         //  遍歷從當前節(jié)點出發(fā)的鄰接節(jié)點  

79.         for(Edge nextEdge : currentNode.getOutEdges()) {  

80.             System.out.println("nextEdge.endNodeid:" + nextEdge.getEndNodeID());  

81.             // 判斷 經(jīng)過當前節(jié)點至鄰接節(jié)點的距離 < 之前記錄的從源節(jié)點出發(fā)到鄰接節(jié)點的距離  

82.             if((nextEdge.getWeight() + nodeidShortestRouteMapping.get(currentNode.getId()))  

83.                     < nodeidShortestRouteMapping.get(nextEdge.getEndNodeID())) {  

84.                 // 更新路由表  

85.                 nodeidShortestRouteMapping.put(nextEdge.getEndNodeID(),  

86.                         nextEdge.getWeight() + nodeidShortestRouteMapping.get(currentNode.getId()));  

87.                 nodeidLastNodeidMapping.put(nextEdge.getEndNodeID(),  

88.                         currentNode.getId());  

89.             }  

90.         }  

91.         // 從未被處理過的節(jié)點集合中,取出權(quán)值最小的節(jié)點  

92.         for(String nodeID : sourceNodeIDList) {  

93.             if(nodeidShortestRouteMapping.get(nodeID) < shortestPath) {  

94.                 shortestPath = nodeidShortestRouteMapping.get(nodeID);  

95.                 nextNodeID = nodeID;  

96.             }  

97.         }  

98.         if(sourceNodeIDList.size() == 1) // 從未被處理過的節(jié)點集合中,取出最后一個節(jié)點  

99.             return sourceNodeIDList.get(0);  

100.         return nextNodeID;  

101.     }  

102.      

103.      

104.     public Map getNodeidShortestRouteMapping() {  

105.         return nodeidShortestRouteMapping;  

106.     }  

107.   

108.     public Map getNodeidLastNodeidMapping() {  

109.         return nodeidLastNodeidMapping;  

110.     }  

111.   

112.     public static void main(String[] args) {  

113.         Graph graph = new Graph();  

114.         graph.init();  

115.          

116.         Dijkstra dijkstra = new Dijkstra(graph, "A");  

117.         dijkstra.start();  

118.   

119.         // 打印最終的路由表  

120.         Iterator it = dijkstra.getNodeidShortestRouteMapping().keySet().iterator();  

121.         while(it.hasNext()) {  

122.             String id = it.next();  

123.             System.out.println("nodeId: "  + id + ", shortest length: " + dijkstra.getNodeidShortestRouteMapping().get(id)  

124.                     + ", last nodeId: " + dijkstra.getNodeidLastNodeidMapping().get(id));  

125.         }  

126.     }  

127. }  

 

       最終執(zhí)行結(jié)果

       ============= currentNode.id: A =============
       nextEdge.endNodeid:B
       nextEdge.endNodeid:C
       nextEdge.endNodeid:E
       nextNode.id:B
       sourceNodeIDList:[C, D, E]
       ============= currentNode.id: B =============
       nextEdge.endNodeid:C
       nextEdge.endNodeid:E
       nextNode.id:C
       sourceNodeIDList:[D, E]
       ============= currentNode.id: C =============
       nextEdge.endNodeid:D
       nextNode.id:E
       sourceNodeIDList:[D]
       ============= currentNode.id: E =============
       nextEdge.endNodeid:D
       nextNode.id:D
       sourceNodeIDList:[]
       nodeId: D, shortest length: 40.0, last nodeId: E
       nodeId: E, shortest length: 20.0, last nodeId: B
       nodeId: A, shortest length: 0.0, last nodeId: null
       nodeId: B, shortest length: 10.0, last nodeId: A
       nodeId: C, shortest length: 15.0, last nodeId: B

 

4000-880-989
(24小時熱線)
聯(lián)系客服
微信公眾號

官方公眾號

小程序

?2008-2022 CORPORATION ALL Rights Reserved. 昆明奧遠科技有限公司版權(quán)所有 滇ICP備09003328號-1 滇公網(wǎng)安備 53011102000818號 增值電信業(yè)務(wù)經(jīng)營許可證號:滇B2-20110045
昆明那家網(wǎng)絡(luò)公司好,新媒體運營,網(wǎng)站優(yōu)化,網(wǎng)絡(luò)推廣,網(wǎng)站建設(shè),網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,網(wǎng)站推廣,云南網(wǎng)站公司,昆明新媒體公司,云南網(wǎng)紅主播,昆明SEO公司,昆明網(wǎng)站建設(shè),昆明網(wǎng)絡(luò)推廣,昆明網(wǎng)站優(yōu)化,昆明網(wǎng)站推廣,紅河網(wǎng)站建設(shè),大理網(wǎng)絡(luò)公司,曲靖網(wǎng)絡(luò)公司,麗江網(wǎng)站設(shè)計,昭通網(wǎng)絡(luò)公司,保山大數(shù)據(jù)服務(wù),智慧高速建設(shè),智慧校園服務(wù),云南IDC服務(wù)商,網(wǎng)絡(luò)安全測評,等保測評,網(wǎng)站關(guān)鍵詞排名優(yōu)化服務(wù),服務(wù)客戶盡超2000余家,一切盡在奧遠科技,服務(wù)電話:13888956730