求无向图中指定点到点之前最短路径

求无向图中任意两点之间最短距离

使用 Floyd 算法实现。Floyd 算法是动态规划思想的一种体现，既然用到动态规划，那么就需要找到状态转移方程。
在本例中，假设求 1 ->2 之间的最短距离，很容易得到 f(2) = min{f(3)+1,f(5)+1}
推出转移方程就是 f(d) = min(f(0)>0->f(0)+1…f(d-1)>0->f(d-1)+1)

JAVA 编码实现

 public static void main(String[] args) {int[][] maps = {{0, 0, 0, 0, 0, 0},
            {0, 0, 0, 1, 1, 0},
            {0, 0, 0, 1, 0, 1},
            {0, 1, 1, 0, 0, 1},
            {0, 1, 0, 0, 0, 1},
            {0, 0, 1, 1, 1, 0}
    };


    int shortDistance = shortDistance(maps, 1, 2);
    System.out.println("最短路径:" + shortDistance);
  }

  public static int shortDistance(int[][] maps, int x, int y) {int min = maps[x][y];
    if (min == 0) {for (int i = 1; i < maps[y].length; i++) {if (maps[x][i] == 1) {int tmp = shortDistance(maps, x, i);
          if (tmp + 1 < min || min == 0) {min = tmp + 1;}
        }
      }
    }
    return min;
  }