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
