Dijkstra

Dijkstra 算法的步骤中没有考虑负权重的边。如果图中存在负权重的边，应该使用其他算法，如 [[笔记/笔记杂记/Bellman-Ford]] 算法

算法步骤

1. 初始化：创建一个距离数组 distance，用于记录从源节点到每个节点的距离，初始时将所有节点的距离设置为无穷大（表示不可达），将源节点的距离设置为0。同时创建一个集合  visited ，用于记录已经确定最短路径的节点。
2. 选择最近节点：从未确定最短路径的节点中选择一个距离最小的节点，将其标记为已访问，并更新该节点相邻节点的距离。初始时，选择源节点作为最近节点。
3. 更新距离：对于当前选定的最近节点，遍历其所有相邻节点。对于每个相邻节点，计算从源节点经过当前最近节点到达该相邻节点的距离。如果这个距离小于目前已知的最短路径距离，则更新该节点的距离。
4. 重复步骤2和步骤3，直到所有节点都被标记为已访问，或者所有节点的距离都被确定为最短路径。
5. 最短路径获取：根据最终计算得到的最短路径信息，可以通过回溯从目标节点向源节点遍历，获取最短路径

模板

private static final int INFINITY = Integer.MAX_VALUE;
/**
 * @param graph 邻接矩阵（节点间无边值为0）
 * @param s 源点
 * @return 源点s到其他点之间的距离（数组）
 */
int[] dijkstra(int[][] graph, int s) {
 int vertexCount = graph.length;
 int[] distance = new int[vertexCount];
 boolean[] visited = new boolean[vertexCount];
 for (int i = 0; i < vertexCount; i++) {
  distance[i] = INFINITY;
  visited[i] = false;
 }
 distance[s] = 0;

 while (true) {
  int v = findMinimumDistanceVertex(distance, visited);
  if(v == -1) break;
  
  visited[v] = true;
  for (int j = 0; j < vertexCount; j++) {
   if (!visited[j] 
    && graph[v][j] != 0 
    && distance[v] != INFINITY 
    && distance[v] + graph[v][j] < distance[j]) {

    distance[j] = distance[v] + graph[v][j];
   }
  }
 }
 return distance;
}
int findMinimumDistanceVertex(int[] distance, boolean[] visited) {
 int minDistance = INFINITY;
 int minDistanceVertex = -1;

 for (int i = 0; i < distance.length; i++) {
  if (!visited[i] && distance[i] < minDistance) {
   minDistance = distance[i];
   minDistanceVertex = i;
  }
 }

 return minDistanceVertex;
}