(Dijkstra 算法)有权有向图求一个点到其它所有点最短路径

围巾🧣 2020年04月14日 607次浏览

思想

Dijkstra算法其实是贪婪算法,贪婪算法一般分阶段求解一个问题,在每个阶段它都把出现的当作是最好的去处理。

Dijkstra算法按阶段进行,正像无权最短路径算法一样。

  1. 在每个阶段,Dijkstra 算法选择一个顶点v,它在所有 unknown 顶点中具有最小的dv。同时算法声明从s到v的最短路径是 known 的。
  2. 阶段的其余部分由dw值的更新工作组成。

image.png

image.png


若顶点v能提供一条更短路径,则我们本质上降低了dw的值。当dw的新值dv+cvw是一个改进的值时我们就置dw=dv+cvw。

  • 举个例子,s起始点是v1,v是v7,w是v6。之前到达v6是走v1->v4->v6。
  • 现在走v1->v4->v7->v6时,dv+cvw=5+1,dw是1+8。由于dv+cvw<dw,所以v6的dw改为6,上一个路径变成走v7。

步骤

  1. 定义邻接表、初始化距离
  2. 定义一个变量看是否所有点已经know
  3. 有未知的点就循环处理
    1. 找最小距离且未知顶点
    2. 设置点为已经know,后面如果是已经know,不再改变距离路径
    3. 更新当前点指向的点的距离,路径
    4. 检测isAllKnow

代码

  1. import java.util.ArrayList;
  2. import java.util.List;

  3. public class WeightedGraph {
  4. private static final int INFINITY = 999999999;

  5. static void printPath(Vertex v) {
  6. if (v.path != null) {
  7. printPath(v.path);
  8. System.out.println("到");
  9. }
  10. System.out.println(v);
  11. }

  12. /**
  13. * 把邻接矩阵转邻接表
  14. *
  15. * @param matrix 图的邻接矩阵,点从0开始
  16. */
  17. private static List<Vertex> adjMatrix2List(int[][] matrix) {
  18. //1. 定义点的列表,要初始化好入度,指向的点,值
  19. List<Vertex> vertexList = new ArrayList<>();

  20. //2. 遍历每一个点,找其所有adjVertex
  21. for (int i = 0; i < matrix.length; i++) {
  22. int[] edges = matrix[i];
  23. Vertex vertex = new Vertex(i);
  24. // example: {0,0,3,4,9}
  25. for (int j = 0; j < edges.length; j++) {
  26. //i点有指向这个j点
  27. if (edges[j] != 0) {
  28. AdjV adjV = new AdjV(j);
  29. adjV.weight = edges[j];
  30. vertex.adj.add(adjV);
  31. }
  32. }
  33. vertexList.add(vertex);
  34. }

  35. return vertexList;
  36. }

  37. public static void dijkstra(int[][] matrix, int s) {
  38. // 1. 定义邻接表、初始化距离
  39. List<Vertex> vertexList = adjMatrix2List(matrix);
  40. int i = 1;
  41. for (Vertex v :
  42. vertexList) {
  43. v.dist = INFINITY;
  44. v.known = false;
  45. }

  46. vertexList.get(s).dist = 0;

  47. // 2. 定义一个变量看是否所有点已经know
  48. boolean isAllVKnow = false;

  49. // 3. 有未知的点就循环处理
  50. while (!isAllVKnow) {

  51. // 1. 找最小距离且未知顶点
  52. Vertex v = null;
  53. int minDist = INFINITY;
  54. for (Vertex vertex :
  55. vertexList) {
  56. if (vertex.dist < minDist && !vertex.known) {
  57. v = vertex;
  58. minDist = vertex.dist;
  59. }
  60. }

  61. // 2. 设置点为已经know,后面如果是已经know,不再改变距离路径
  62. v.known = true;

  63. // 3. 更新当前点指向的点的距离,路径
  64. for (AdjV adjV : v.adj) {
  65. Vertex w = vertexList.get(adjV.v);
  66. if (!w.known) { // 点是不知道的
  67. int cvw = adjV.weight;

  68. // 更短就更新值和路径
  69. if (v.dist + cvw < w.dist) {
  70. w.dist = v.dist + cvw;
  71. w.path = v;
  72. }
  73. }
  74. }

  75. // 4. 检测isAllKnow
  76. isAllVKnow = true;
  77. for (Vertex vertex : vertexList) {
  78. if (!vertex.known) {
  79. isAllVKnow = false;
  80. break;
  81. }
  82. }
  83. }

  84. // 打印看看
  85. for (Vertex v :
  86. vertexList) {
  87. System.out.println("这时打印的点是: v" + (v.value) + ", 距离:" + v.dist);
  88. printPath(v);
  89. }

  90. }


  91. private static class Vertex {
  92. public List<AdjV> adj;
  93. public boolean known;
  94. public int dist;
  95. public Vertex path;
  96. public int value;

  97. public Vertex(int value) {
  98. this.adj = new ArrayList<>();
  99. this.known = false;
  100. this.path = null;
  101. this.value = value;
  102. }

  103. @Override
  104. public String toString() {
  105. return "Vertex{" +
  106. "value=" + value +
  107. ", dist=" + dist +
  108. ", path=" + path +
  109. '}';
  110. }
  111. }

  112. /**
  113. * 存指向的点的序号
  114. * 和权重
  115. */
  116. private static class AdjV {
  117. int v;// 几号点
  118. int weight;

  119. public AdjV(int v) {
  120. this.v = v;
  121. }
  122. }
  123. }

测试

  1. public class Main {
  2. public static void main(String[] args) {

  3. int[][] matrix = {
  4. {0, 2, 0, 1, 0, 0, 0,},
  5. {0, 0, 0, 3, 10, 0, 0,},
  6. {1, 0, 0, 0, 0, 5, 0,},
  7. {0, 0, 2, 0, 2, 8, 4,},
  8. {0, 0, 0, 0, 0, 0, 6,},
  9. {0, 0, 0, 0, 0, 0, 0,},
  10. {0, 0, 0, 0, 0, 1, 0,},
  11. };
  12. WeightedGraph.dijkstra(matrix, 0);
  13. }
  14. }

打印出来的点从v0开始,点的序号是value