Dijkstra算法求最短路径(java)（转）

2023-01-01 11:22:05

原文链接：Dijkstra算法求最短路径(java)

任务描述：在一个无向图中，获取起始节点到所有其他节点的最短路径描述

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：
Node对象用于封装节点信息，包括名字和子节点

  1. public class Node {
  2. private String name;
  3. private Map<Node,Integer> child=new HashMap<Node,Integer>();
  4. public Node(String name){
  5. this.name=name;
  6. }
  7. public String getName() {
  8. return name;
  9. }
  10. public void setName(String name) {
  11. this.name = name;
  12. }
  13. public Map<Node, Integer> getChild() {
  14. return child;
  15. }
  16. public void setChild(Map<Node, Integer> child) {
  17. this.child = child;
  18. }
  19. }

MapBuilder用于初始化数据源，返回图的起始节点

  1. public class MapBuilder {
  2. public Node build(Set<Node> open, Set<Node> close){
  3. Node nodeA=new Node("A");
  4. Node nodeB=new Node("B");
  5. Node nodeC=new Node("C");
  6. Node nodeD=new Node("D");
  7. Node nodeE=new Node("E");
  8. Node nodeF=new Node("F");
  9. Node nodeG=new Node("G");
  10. Node nodeH=new Node("H");
  11. nodeA.getChild().put(nodeB, 1);
  12. nodeA.getChild().put(nodeC, 1);
  13. nodeA.getChild().put(nodeD, 4);
  14. nodeA.getChild().put(nodeG, 5);
  15. nodeA.getChild().put(nodeF, 2);
  16. nodeB.getChild().put(nodeA, 1);
  17. nodeB.getChild().put(nodeF, 2);
  18. nodeB.getChild().put(nodeH, 4);
  19. nodeC.getChild().put(nodeA, 1);
  20. nodeC.getChild().put(nodeG, 3);
  21. nodeD.getChild().put(nodeA, 4);
  22. nodeD.getChild().put(nodeE, 1);
  23. nodeE.getChild().put(nodeD, 1);
  24. nodeE.getChild().put(nodeF, 1);
  25. nodeF.getChild().put(nodeE, 1);
  26. nodeF.getChild().put(nodeB, 2);
  27. nodeF.getChild().put(nodeA, 2);
  28. nodeG.getChild().put(nodeC, 3);
  29. nodeG.getChild().put(nodeA, 5);
  30. nodeG.getChild().put(nodeH, 1);
  31. nodeH.getChild().put(nodeB, 4);
  32. nodeH.getChild().put(nodeG, 1);
  33. open.add(nodeB);
  34. open.add(nodeC);
  35. open.add(nodeD);
  36. open.add(nodeE);
  37. open.add(nodeF);
  38. open.add(nodeG);
  39. open.add(nodeH);
  40. close.add(nodeA);
  41. return nodeA;
  42. }
  43. }

图的结构如下图所示：
Dijkstra算法求最短路径(java)（转）

Dijkstra对象用于计算起始节点到所有其他节点的最短路径

  1. public class Dijkstra {
  2. Set<Node> open=new HashSet<Node>();
  3. Set<Node> close=new HashSet<Node>();
  4. Map<String,Integer> path=new HashMap<String,Integer>();//封装路径距离
  5. Map<String,String> pathInfo=new HashMap<String,String>();//封装路径信息
  6. public Node init(){
  7. //初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
  8. path.put("B", 1);
  9. pathInfo.put("B", "A->B");
  10. path.put("C", 1);
  11. pathInfo.put("C", "A->C");
  12. path.put("D", 4);
  13. pathInfo.put("D", "A->D");
  14. path.put("E", Integer.MAX_VALUE);
  15. pathInfo.put("E", "A");
  16. path.put("F", 2);
  17. pathInfo.put("F", "A->F");
  18. path.put("G", 5);
  19. pathInfo.put("G", "A->G");
  20. path.put("H", Integer.MAX_VALUE);
  21. pathInfo.put("H", "A");
  22. //将初始节点放入close,其他节点放入open
  23. Node start=new MapBuilder().build(open,close);
  24. return start;
  25. }
  26. public void computePath(Node start){
  27. Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
  28. if(nearest==null){
  29. return;
  30. }
  31. close.add(nearest);
  32. open.remove(nearest);
  33. Map<Node,Integer> childs=nearest.getChild();
  34. for(Node child:childs.keySet()){
  35. if(open.contains(child)){//如果子节点在open中
  36. Integer newCompute=path.get(nearest.getName())+childs.get(child);
  37. if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
  38. path.put(child.getName(), newCompute);
  39. pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
  40. }
  41. }
  42. }
  43. computePath(start);//重复执行自己,确保所有子节点被遍历
  44. computePath(nearest);//向外一层层递归,直至所有顶点被遍历
  45. }
  46. public void printPathInfo(){
  47. Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
  48. for(Map.Entry<String, String> pathInfo:pathInfos){
  49. System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
  50. }
  51. }
  52. /**
  53. * 获取与node最近的子节点
  54. */
  55. private Node getShortestPath(Node node){
  56. Node res=null;
  57. int minDis=Integer.MAX_VALUE;
  58. Map<Node,Integer> childs=node.getChild();
  59. for(Node child:childs.keySet()){
  60. if(open.contains(child)){
  61. int distance=childs.get(child);
  62. if(distance<minDis){
  63. minDis=distance;
  64. res=child;
  65. }
  66. }
  67. }
  68. return res;
  69. }
  70. }

Main用于测试Dijkstra对象

  1. public class Main {
  2. public static void main(String[] args) {
  3. Dijkstra test=new Dijkstra();
  4. Node start=test.init();
  5. test.computePath(start);
  6. test.printPathInfo();
  7. }
  8. }

打印输出如下：
D:A->D
E:A->F->E
F:A->F
G:A->C->G
B:A->B
C:A->C
H:A->B->H

 

参考链接：

上一篇：MDX示例：求解中位数、四分位数(median、quartile）


下一篇：_DataStructure_C_Impl:Dijkstra算法求最短路径