漫画:Dijkstra 算法的优化

蠢萌的小灰 梦见 2019-04-23

在上一篇漫画中,小灰介绍了单源最短路径算法 Dijkstra,没看过的小伙伴可以看下:

漫画:图的 “最短路径” 问题


漫画中我们遗留了一个问题:

如何求得最短路径的详细节点,而不仅仅是距离?


在本篇中,我们将会给与解答。







我们仍然以下面这个带权图为例,找出从顶点A到顶点G的最短距离。





详细过程如下:


第1步,创建距离表和前置顶点表。

距离表的Key是顶点名称,Value是从起点A到对应顶点的已知最短距离,默认为无穷大;前置顶点表的Key是顶点名称,Value是从起点A到对应顶点的已知最短路径的前置定点。



第2步,遍历起点A,找到起点A的邻接顶点B和C。从A到B的距离是5,从A到C的距离是2。把这一信息刷新到距离表当中。

同时,顶点B、C的前置顶点都是A,顶点A在邻接表中下标是0,所以把前置顶点表的B、C值更新为0:




第3步,从距离表中找到从A出发距离最短的点,也就是顶点C。


第4步,遍历顶点C,找到顶点C的邻接顶点D和F(A已经遍历过,不需要考虑)。从C到D的距离是6,所以A到D的距离是2+6=8;从C到F的距离是8,所以从A到F的距离是2+8=10。把这一信息刷新到表中。

同时,顶点D、F的前置顶点都是C,顶点C在邻接表中下标是2,所以把前置顶点表的D、F值更新为2:




接下来重复第3步、第4步所做的操作:


第5步,也就是第3步的重复,从距离表中找到从A出发距离最短的点(C已经遍历过,不需要考虑),也就是顶点B。


第6步,也就是第4步的重复,遍历顶点B,找到顶点B的邻接顶点D和E(A已经遍历过,不需要考虑)。从B到D的距离是1,所以A到D的距离是5+1=6,小于距离表中的8;从B到E的距离是6,所以从A到E的距离是5+6=11。把这一信息刷新到表中。

同时,顶点D、E的前置顶点都是B,顶点B在邻接表中下标是1,所以把前置顶点表的D、E值更新为1:




第7步,从距离表中找到从A出发距离最短的点(B和C不用考虑),也就是顶点D。


第8步,遍历顶点D,找到顶点D的邻接顶点E和F。从D到E的距离是1,所以A到E的距离是6+1=7,小于距离表中的11;从D到F的距离是2,所以从A到F的距离是6+2=8小于距离表中的10。把这一信息刷新到表中。

同时,顶点E、F的前置顶点都是D,顶点D在邻接表中下标是3,所以把前置顶点表的E、F值更新为3:




第9步,从距离表中找到从A出发距离最短的点,也就是顶点E。


第10步,遍历顶点E,找到顶点E的邻接顶点G。从E到G的距离是7,所以A到G的距离是7+7=14。把这一信息刷新到表中。

同时,顶点G的前置顶点是E,顶点E在邻接表中下标是4,所以把前置顶点表的G值更新为4:




第11步,从距离表中找到从A出发距离最短的点,也就是顶点F。


第12步,遍历顶点F,找到顶点F的邻接顶点G。从F到G的距离是3,所以A到G的距离是8+3=11,小于距离表中的14。把这一信息刷新到表中:




就这样,除终点以外的全部顶点都已经遍历完毕,距离表中存储的是从起点A到所有顶点的最短距离,而前置定点存储的是从起点A到所有顶点最短路径的前置顶点。






如何把前置顶点表“翻译”成图的最短路径呢?我们可以使用回溯法,自后向前回溯:


第1步,找到图的终点G,它是最短路径的终点:




第2步,通过前置定点表找到顶点G对应的前置下标5,在顶点数组中找到下标5对应的顶点F,它是顶点G的前置顶点:




第3步,通过前置定点表找到顶点F对应的前置下标3,在顶点数组中找到下标3对应的顶点D,它是顶点F的前置顶点:




第4步,通过前置定点表找到顶点D对应的前置下标1,在顶点数组中找到下标1对应的顶点B,它是顶点D的前置顶点:



第5步,通过前置定点表找到顶点B对应的前置下标0,在顶点数组中找到下标0对应的顶点A,它是顶点B的前置顶点:


如此一来,我们把前置顶点表(0,0,1,3,3,5)转化成了最短路径(A-B-D-F-G)。




  1. /**

  2. * Dijkstra最短路径算法

  3. */

  4. public static int[] dijkstra(Graph graph, int startIndex) {


  5. //图的顶点数量

  6. int size = graph.vertexes.length;

  7. //创建距离表,存储从起点到每一个顶点的临时距离

  8. int[] distances = new int[size];

  9. //创建前置定点表,存储从起点到每一个顶点的已知最短路径的前置节点

  10. int[] prevs = new int[size];

  11. //记录顶点遍历状态

  12. boolean[] access = new boolean[size];


  13. //初始化最短路径表,到达每个顶点的路径代价默认为无穷大

  14. for(int i=0; i

  15. distances[i] = Integer.MAX_VALUE;

  16. }

  17. //遍历起点,刷新距离表

  18. access[0] = true;

  19. List<Edge> edgesFromStart = graph.adj[startIndex];

  20. for(Edge edge : edgesFromStart)

  21. {

  22. distances[edge.index] = edge.weight;

  23. prevs[edge.index] = 0;

  24. }

  25. //主循环,重复 遍历最短距离顶点和刷新距离表 的操作

  26. for(int i=1; i

  27. {

  28. //寻找最短距离顶点

  29. int minDistanceFromStart = Integer.MAX_VALUE;

  30. int minDistanceIndex = -1;

  31. for(int j=1; j

  32. {

  33. if(!access[j] && distances[j] < minDistanceFromStart)

  34. {

  35. minDistanceFromStart = distances[j];

  36. minDistanceIndex = j;

  37. }

  38. }

  39. if(minDistanceIndex == -1){

  40. break;

  41. }

  42. //遍历顶点,刷新距离表

  43. access[minDistanceIndex] = true;

  44. for(Edge edge : graph.adj[minDistanceIndex])

  45. {

  46. if(access[edge.index]){

  47. continue;

  48. }

  49. int weight = edge.weight;

  50. int preDistance = distances[edge.index];

  51. if(weight != Integer.MAX_VALUE && (minDistanceFromStart+ weight < preDistance))

  52. {

  53. distances[edge.index] = minDistanceFromStart + weight;

  54. prevs[edge.index] = minDistanceIndex;

  55. }

  56. }

  57. }


  58. return prevs;

  59. }


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

  61. Graph graph = new Graph(7);

  62. initGraph(graph);

  63. int[] prevs = dijkstra(graph, 0);

  64. printPrevs(graph.vertexes, prevs, graph.vertexes.length-1);

  65. }


  66. private static void printPrevs(Vertex[] vertexes, int[] prev, int i){

  67. if(i>0){

  68. printPrevs(vertexes, prev, prev[i]);

  69. }

  70. System.out.println(vertexes[i].data);

  71. }


  72. /**

  73. * 图的顶点

  74. */

  75. private static class Vertex {

  76. String data;

  77. Vertex(String data) {

  78. this.data = data;

  79. }

  80. }


  81. /**

  82. * 图的边

  83. */

  84. private static class Edge {

  85. int index;

  86. int weight;

  87. Edge(int index, int weight) {

  88. this.index = index;

  89. this.weight = weight;

  90. }

  91. }


  92. /**

  93. * 图

  94. */

  95. private static class Graph {

  96. private Vertex[] vertexes;

  97. private LinkedList<Edge> adj[];


  98. Graph(int size){

  99. //初始化顶点和邻接矩阵

  100. vertexes = new Vertex[size];

  101. adj = new LinkedList[size];

  102. for(int i=0; i

  103. adj[i] = new LinkedList<Edge>();

  104. }

  105. }

  106. }


  107. private static void initGraph(Graph graph){

  108. graph.vertexes[0] = new Vertex("A");

  109. graph.vertexes[1] = new Vertex("B");

  110. graph.vertexes[2] = new Vertex("C");

  111. graph.vertexes[3] = new Vertex("D");

  112. graph.vertexes[4] = new Vertex("E");

  113. graph.vertexes[5] = new Vertex("F");

  114. graph.vertexes[6] = new Vertex("G");


  115. graph.adj[0].add(new Edge(1, 5));

  116. graph.adj[0].add(new Edge(2, 2));

  117. graph.adj[1].add(new Edge(0, 5));

  118. graph.adj[1].add(new Edge(3, 1));

  119. graph.adj[1].add(new Edge(4, 6));

  120. graph.adj[2].add(new Edge(0, 2));

  121. graph.adj[2].add(new Edge(3, 6));

  122. graph.adj[2].add(new Edge(5, 8));

  123. graph.adj[3].add(new Edge(1, 1));

  124. graph.adj[3].add(new Edge(2, 6));

  125. graph.adj[3].add(new Edge(4, 1));

  126. graph.adj[3].add(new Edge(5, 2));

  127. graph.adj[4].add(new Edge(1, 6));

  128. graph.adj[4].add(new Edge(3, 1));

  129. graph.adj[4].add(new Edge(6, 7));

  130. graph.adj[5].add(new Edge(2, 8));

  131. graph.adj[5].add(new Edge(3, 2));

  132. graph.adj[5].add(new Edge(6, 3));

  133. graph.adj[6].add(new Edge(4, 7));

  134. graph.adj[6].add(new Edge(5, 3));

  135. }


代码中,距离表和前置顶点表都是采用数组存储,这样比较方便。

输出最短路径的时候,代码中采用了递归的方式进行回溯。



—————END—————




喜欢本文的朋友们,欢迎长按下图关注公众号程序员小灰,收看更多精彩内容


文章已于修改
    已同步到看一看

    发送中

    本站仅按申请收录文章,版权归原作者所有
    如若侵权,请联系本站删除
    觉得不错,分享给更多人看到
    梦见 热门文章:

    漫画:编程其实是文科    阅读/点赞 : 1108/17

    我是一个线程    阅读/点赞 : 693/22

    漫画:三分钟了解敏捷开发    阅读/点赞 : 644/17

    漫画:什么是中间人攻击    阅读/点赞 : 613/16

    我是一个Java class    阅读/点赞 : 552/10

    网贷遇雷潮,投资者如何避雷?    阅读/点赞 : 0/0