Dijkstra

Dijkstra 作用：dijkstra 常用来求解 单源最短路径问题

单源最短路径问题：从某个固定源点出发，求其到所有其他顶点的最短路径

---

符号定义：

• 将顶点分为两类集合，即已经“收集”的顶点 S = {源点 src + 已经确定了最短路径的顶点 vi} 和 “未被收集”进 S 集合的顶点集合 T

• 定义数组 dist[i] 表示：从源点 src 到顶点 i 的最短路径长度

  • 结论：真正的最短路径必须只经过 S 中的顶点（用的是反证法，证明方法看 zju 陈越姥姥）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jDkyNEKh-1631883531830)(data/dijkstra.png)]

Dijkstra 算法步骤：

1. 初始化

   dist 中初始值为 INF，但是 dist[src] = 0

   visited 初始化均为 false

   邻接矩阵 graph[i][j] 中没有边的顶点之间，初始化 INF

   public static final int INF = Integer.MAX_VALUE / 2; // 不能定义为 Integer.MAX_VALUE
   
   int[][] graph = new int[vertexSize][vertexSize];
   // graph 初始化
   for (int i = 0; i < vertexSize; i++) {
       for (int j = 0; j < vertexSize; j++) {
           graph[i][j] = INF;
       }
   }
   
   boolean[] visited = new boolean[vertexSize]; // 标记数组（标记当前节点是否访问过，即当前节点是否被 “收集” 进 S）
   int[] dist = new int[vertexSize]; // dist[i] 表示当前从 src 到顶点 i 的最短距离
   // 初始化
   Arrays.fill(dist, INF);
   Arrays.fill(visited, false);
   dist[src] = 0;
   // 这里暂时还不能“收集”源点 src，而是在 for 第一次启动时 “收集”
   

   Note：

   这里 INF 不能赋值为 Integer.MAX_VALUE；否则 dijkstra 中更新最短路径时, int 会向上溢出

   INF 应该赋值为 Integer.MAX_VALUE / 2（为了防止没有边连接的 dist[minVertex]+graph[minVertex][j]造成 int上溢）或者⭐️ 如果 INF 应该赋值为 Integer.MAX_VALUE 的话，两数相加之前都要判断 grapg[i][j] 是否为 INF 来防止造成 int 上溢

2. 找未被“收集”顶点集 T 中 dist 最小的顶点 minVertex

   即，选择一个 与 “源点 src” 所在的顶点集合 S相连 && 未被收集 && 相连边权重最小的顶点 minVertex

   注意，这里第一个 minVertex 就是 源点 src 本身；而不是，与 src有相连边 && 权重最小的顶点

   • visited[j] == false 表示顶点 j 未被收录进入 S