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

Question

I have a grid that represents a map. I have nodes that are ocean, and I have nodes that are land. I would like to assign a distance to every one of them using a recursive function. (So I guess one function call/island).

I have a code currently, which is this:

    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;
    }

The problem is, that it doesnt really work, I think mainly because I dont know how to handle the nodes that are already visited.

Answer 1

You want the Dijkstra algorithm 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.

or better ( remove un-needed calls to 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 is a map of distances keyed by the ordered node pair A,B. That is A->B and B->A give the same distance.