一张地图找离目标最近的点

[zprimy]

一张地图上有大量的点，给你一个目标点，如何在这些点中找到离目标点最近的点

[qjkobe]

佛洛依德

佛洛依德算法思路比较简单。复杂度O(n^3)

  static void floyd(int[][] matrix) {
    //佛洛依德就是给出中转点x，看m[i][x]+m[x][j]是不是小于m[i][j]，如果是的话就把这个作为m[i][j]
    for (int x = 0; x < matrix.length; x++) {
      for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
          if (matrix[i][x]!=Integer.MAX_VALUE && matrix[x][j]!= Integer.MAX_VALUE && matrix[i][x] + matrix[x][j] < matrix[i][j]) {
            matrix[i][j] = matrix[i][x] + matrix[x][j];
          }
        }
      }
    }
  }

  public static void main(String[] args) {
    //四个节点。邻接矩阵如下
    int[][] matrix = { { 0, 2, 6, 4 },
        { Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE },
        { 7, Integer.MAX_VALUE, 0, 1 },
        { 5, Integer.MAX_VALUE, 12, 0 } };
    floyd(matrix);
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix.length; j++) {
        System.out.print(matrix[i][j]+ " ");
      }
      System.out.println();
    }
  }

[qjkobe]

地杰斯特拉

这算法真不咋地。。没有弗洛伊德清晰。如果算所有点，复杂度和佛洛依德也是一样的。

  static void dijkstra(int[][] matrix, int index) {
    //这算法和佛洛依德差不多。。。甚至没有佛洛依德好。但是如果只是求一个点到其他点最短距离的话。这个好一些。
    int[] theShortestPath = new int[matrix.length];
    //theShortestPath[i]表示index到i的已经求出的最短路径。
    //1表示已解决
    int[] hasSolved = new int[matrix.length];
    for (int k = 0; k < matrix.length-1; k++) {
      //因为本来有a在里面。每次会选一个最小的。所以这个循环最多只走总数-1次
      int min = Integer.MAX_VALUE;
      int minIndex = 0;
      for (int i = 0; i < theShortestPath.length; i++) {
        //选出最近的未标记顶点
        if (i == index || hasSolved[i] == 1) {
          continue;
        }
        if (matrix[index][i] < min) {
          min = matrix[index][i];
          minIndex = i;
        }
      }
      hasSolved[minIndex] = 1;
      theShortestPath[minIndex] = min;
      for (int i = 0; i < theShortestPath.length; i++) {
        //不断更新未完成的
        if (i != index && matrix[index][minIndex] != Integer.MAX_VALUE && matrix[minIndex][i] != Integer.MAX_VALUE &&
            matrix[index][minIndex] + matrix[minIndex][i] < matrix[index][i]) {
          matrix[index][i] = matrix[index][minIndex] + matrix[minIndex][i];

        }
      }
    }
    for (int a : theShortestPath) {
      System.out.print(a + " ");
    }

  }

  public static void main(String[] args) {
    //四个节点。邻接矩阵如下
    int[][] matrix = { { 0, 2, 6, 4 },
        { Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE },
        { 7, Integer.MAX_VALUE, 0, 1 },
        { 5, Integer.MAX_VALUE, 12, 0 } };
    dijkstra(matrix, 1);
  }