每天一个算法-最短路径

最短路径算法

• Dijkstra
• Floyd

n vertexs named [0, … ,n] undirected gragh, get shorted path from 0 to every other vetex.

当所有边的权重为1的时候，dijkstra和BFS搜索路径相同

/**
 * get shortest path to ever other
 * @param matrix - matrix[i][j] means length between i and j, inf if not connected.
 * @param n - total vertex
 * @param s - start point
 * @return
 */
public static int[] Dijkstra(int[][] matrix, int n, int s){
   Set<Integer> visited = new HashSet<>();
   visited.add(s);
   while(visited.size() < n){
      int minIndex = -1;
      int minLength = Integer.MAX_VALUE;
      for (int i = 0; i < n; i++) {
         if(visited.contains(i))
            continue;
         if(matrix[s][i] < minLength){
            minLength = matrix[s][i];
            minIndex = i;
         }
      }
      visited.add(minIndex);
      for (int i = 0; i < n; i++) {
         if(matrix[minIndex][i] != Integer.MAX_VALUE) {
            matrix[s][i] = Math.min(matrix[s][i],
                  minLength + matrix[minIndex][i]);
         }
      }
   }
   return matrix[s];
}

public static void Floyd(int[][] matrix, int n){
   for (int i = 0; i < n; i++) { // first loop is to make shorter path
      for (int j = 0; j < n; j++) {
         for (int k = 0; k < n; k++) {
            int newLength = (matrix[j][i] == Integer.MAX_VALUE || 
                       	matrix[i][k] == Integer.MAX_VALUE) ? 
              			Integer.MAX_VALUE : matrix[j][i] + matrix[i][k];
            matrix[j][k] = Math.min(matrix[j][k], newLength);
         }
      }
   }
}