Dijkstra算法

Dijkstra算法：用于计算图中某一点到其他各点的最短路径。关于Dijkstra算法的说明可以参考数据结构相关书籍。

       为Dijkstra算法设计的类：
       1. Node        节点类

       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.     // 节点编号  

9.     private String id;  

10.     // 从当前节点出发的边的信息列表  

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.     // 边的起始节点编号  

6.     private String startNodeID;  

7.     // 边的末尾节点编号  

8.     private String endNodeID;  

9.     // 边的权值  

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.     // 图中的节点列表  

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.     // 起始节点编号  

12.     private String startNodeID;  

13.     // 未被处理的节点集合  

14.     private List sourceNodeIDList = null;  

15.     // 已被处理的节点集合  

16.     private List desNodeIDList = null;  

17.   

18.     // '节点编号' 和  '起始节点与当前节点之间的最短路径' 的映射关系  

19.     private Map nodeidShortestRouteMapping = null;  

20.     // '节点编号' 和  '起始节点到当前节点之间的最短路径 的 上一跳节点编号' 的映射关系  

21.     private Map nodeidLastNodeidMapping = null;  

22.     // '节点编号' 和  '节点对象'的 映射关系  

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.                 // 起始节点到起始节点的最短路径长度为0  

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

40.             }  

41.             else {  

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

43.                 // 非起始节点到起始节点的最短路径长度为 '无穷大'  

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

45.             }  

46.             // 设置到节点最短路径的上一跳节点为'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.         //  遍历从当前节点出发的邻接节点  

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

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

81.             // 判断 '经过当前节点至邻接节点的距离' < '之前记录的从源节点出发到邻接节点的距离'  

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.         // 从未被处理过的节点集合中，取出权值最小的节点  

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) // 从未被处理过的节点集合中，取出最后一个节点  

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. }  

       最终执行结果

       ============= 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