Shortest path in 2d arrays

问题:

*...*..D
.G..*.....
**...**.
.S....*.
........
...G**..
........
.G..*...

Here is 2d array where
S- Source
D-Destination
G-Point must be visited
." . "Free paths
"*"Block Paths
Can you help me which would be the efficient algorithm to find the length of shortest pathi in java
Only Horizontal and Vertical movements are possiable

回答1:

To find the shortest distance from start point to all other points in the map, you can use a BFS. Sample code:

public void visit(String []map , Point start){
        int []x = {0,0,1,-1};//This represent 4 directions right, left, down , up
        int []y = {1,-1,0,0};
        LinkedList<Point> q = new LinkedList();
        q.add(start);
        int n = map.length;
        int m = map[0].length();
        int[][]dist = new int[n][m];
        for(int []a : dist){
            Arrays.fill(a,-1);
        }
        dist[start.x][start.y] = 0;
        while(!q.isEmpty()){
            Point p = q.removeFirst();
            for(int i = 0; i < 4; i++){
                int a = p.x + x[i];
                int b = p.y + y[i];
                if(a >= 0 && b >= 0 && a < n && b < m && dist[a][b] == -1 && map[a].charAt(b) != '*' ){
                    dist[a][b] = 1 + dist[p.x][p.y];
                    q.add(new Point(a,b));
                }
            }
        }
    }

The second path of the problem is actually a traveling salesman problem, so you need to convert from your original graph to a graph which only contains G,D and S points, with the weight of each edge in this graph is the shortest path between them in original path. From that onward, if the number of G is small (less than 17) you can use dynamic programming and bitmask to solve the problem.

回答2:

Here there are many algorithms like dijkstra or BFS but if you need to learn an path finding algorithm then i suggest the A* algorithm as it is quicker than dijkstra or BFS and can be easily implemented on a 2D matrix. As in case of must visit node you can try all sequences in which you visit the nodes for example say S->G1->G2->G3->D find the minimum for this path as min(S,G1)+min(S,G2)+min(G3,D). try all permutations of the G's and get the minimum of them all.

回答3:

This is a simple Breadth First search algorithm problem. This is called flood fill technique which is a type of Breadth First search algorithm. Read it from here. You can also learn the basic Breadth first algorithm from here. This could also be solved by other techniques like Dijkstra or Floyd warshal. But Breadth first search is easier to understand.