查看原文
其他

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

蠢萌的小灰 程序员小灰 2022-06-18




—————  第二天  —————









如何遍历呢?


第一层,遍历顶点A:




第二层,遍历A的邻接顶点B和C:



第三层,遍历顶点B的邻接顶点D、E,遍历顶点C的邻接顶点F:



第四层,遍历顶点E的邻接顶点G,也就是目标节点:



由此得出,图中顶点A到G的(第一条)最短路径是A-B-E-G:





换句话说,就是寻找从A到G之间,权值之和最小的路径。





————————————







究竟什么是迪杰斯特拉算法?它是如何寻找图中顶点的最短路径呢?


这个算法的本质,是不断刷新起点与其他各个顶点之间的 “距离表”。


让我们来演示一下迪杰斯特拉的详细过程:


第1步,创建距离表。表中的Key是顶点名称,Value是从起点A到对应顶点的已知最短距离。但是,一开始我们并不知道A到其他顶点的最短距离是多少,Value默认是无限大:




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




第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。把这一信息刷新到表中:




接下来重复第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。把这一信息刷新到表中:




(在第6步,A到D的距离从8刷新到6,可以看出距离表所发挥的作用。距离表通过迭代刷新,用新路径长度取代旧路径长度,最终可以得到从起点到其他顶点的最短距离)


第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。把这一信息刷新到表中:




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


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



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


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



就这样,除终点以外的全部顶点都已经遍历完毕,距离表中存储的是从起点A到所有顶点的最短距离。显然,从A到G的最短距离是11。(路径:A-B-D-F-G)



按照上面的思路,我们来看一下代码实现:


  1. /**

  2. * Dijkstra最短路径算法

  3. */

  4. public static Map<Integer, Integer> dijkstra(Graph graph, int startIndex) {

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

  6. Map<Integer, Integer> distanceMap = new HashMap<Integer,Integer>();

  7. //记录遍历过的顶点

  8. Set<Integer> accessedSet = new HashSet<Integer> ();

  9. //图的顶点数量

  10. int size = graph.vertexes.length;

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

  12. for(int i=1; i<size; i++){

  13. distanceMap.put(i, Integer.MAX_VALUE);

  14. }

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

  16. accessedSet.add(0);

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

  18. for(Edge edge : edgesFromStart)

  19. {

  20. distanceMap.put(edge.index, edge.weight);

  21. }

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

  23. for(int i=1; i<size; i++)

  24. {

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

  26. int minDistanceFromStart = Integer.MAX_VALUE;

  27. int minDistanceIndex = -1;

  28. for(int j=1; j<size; j++)

  29. {

  30. if(!accessedSet.contains(j) && distanceMap.get(j) < minDistanceFromStart)

  31. {

  32. minDistanceFromStart = distanceMap.get(j);

  33. minDistanceIndex = j;

  34. }

  35. }

  36. if(minDistanceIndex == -1){

  37. break;

  38. }

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

  40. accessedSet.add(minDistanceIndex);

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

  42. {

  43. if(accessedSet.contains(edge.index)){

  44. continue;

  45. }

  46. int weight = edge.weight;

  47. int preDistance = distanceMap.get(edge.index);

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

  49. {

  50. distanceMap.put(edge.index, minDistanceFromStart + weight);

  51. }

  52. }

  53. }


  54. return distanceMap;

  55. }


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

  57. Graph graph = new Graph(7);

  58. initGraph(graph);

  59. Map<Integer, Integer> distanceMap = dijkstra(graph, 0);

  60. int distance = distanceMap.get(6);

  61. System.out.println(distance);

  62. }


  63. /**

  64. * 图的顶点

  65. */

  66. private static class Vertex {

  67. String data;

  68. Vertex(String data) {

  69. this.data = data;

  70. }

  71. }


  72. /**

  73. * 图的边

  74. */

  75. private static class Edge {

  76. int index;

  77. int weight;

  78. Edge(int index, int weight) {

  79. this.index = index;

  80. this.weight = weight;

  81. }

  82. }


  83. /**

  84. * 图

  85. */

  86. private static class Graph {

  87. private Vertex[] vertexes;

  88. private LinkedList<Edge> adj[];


  89. Graph(int size){

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

  91. vertexes = new Vertex[size];

  92. adj = new LinkedList[size];

  93. for(int i=0; i<adj.length; i++){

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

  95. }

  96. }

  97. }


  98. private static void initGraph(Graph graph){

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  126. }










—————END—————




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


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存