如何确定所有顶点到某一类型顶点的最短距离?

Question

我有一个表示地图的网格。我有代表海洋的节点，还有代表陆地的节点。我想用递归函数给每一个点分配一个距离。(所以我猜一个函数调用/岛)。

我现在有一个代码，它是:

public int searchOcean(int x, int y, boolean[] visited) {
if (x < 0 || x >= width || y < 0 || y >= height) {
return 1000;
}
Node current = this.get(x, y);
int index = current.getIndex(this);
if (visited[index]) {
return current.oceanDist;
}
visited[index] = true;
if (current.ocean) {
current.oceanDist=0;
return 0;
}
int r1 = searchOcean(x + 1, y, visited);
int r2 = searchOcean(x - 1, y, visited);
int r3 = searchOcean(x, y + 1, visited);
int r4 = searchOcean(x, y - 1, visited);
int min = Math.min(Math.min(r1, r2), Math.min(r3 , r4))+1;
current.oceanDist = min;
return min;
}

问题是，它并没有真正工作，我想主要是因为我不知道如何处理已经访问过的节点。

Answer 1

您需要Dijkstra算法https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Loop A over nodes that are land
Apply Dijkstra
Loop B over nodes that are land
add distance ( given by Dijkstra ) from A to B to results.

或更好(删除对Dijkstra的不必要调用)

construct empty D to store distances between every pair of land nodes
loop A over every land node
loop B over every land node
if A-B NOT saved into D
apply Dijkstra with source A
loop C over land nodes
save distance A-C into D
break out of loop B

D是由有序节点对a,B键控的距离映射。即A->B和B->A给出相同的距离