java 点到点最短路径_【算法】求无向图中指定点到点之前最短路径

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

在本例中，假设求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;

}