如何确定所有顶点距某种类型顶点的最短距离？

Question

我有一个代表地图的网格。我有海洋节点，也有陆地节点。我想使用递归函数为它们中的每一个分配一个距离。（所以我猜一个函数 call/island）。

我目前有一个代码，是这样的：

    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 给出相同的距离。

如何确定所有顶点距某种类型顶点的最短距离？

How can I determine the shortest distance from a certain type of vertex for all vertices?

java

recursion

graph-theory

distance

flood-fill