java 二维数组中的最短路径
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25395797/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Shortest path in 2d arrays
提问by user3952416
*...*..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
这是必须访问
S
- Source D-Destination
G-Point 的2d 数组
。”。“自由路径
“*”块路径
你能帮我看看这是在 java 中找到最短路径长度的有效算法吗
只有水平和垂直运动是可能的
采纳答案by Pham Trung
To find the shortest distance from startpoint to all other points in the map, you can use a BFS.
Sample code:
要找到从start点到地图中所有其他点的最短距离，您可以使用BFS。示例代码：
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 weightof 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 bitmaskto solve the problem.
这个问题的第二条路径实际上是一个旅行商问题，所以你需要从原始图形转换为图形其中only contains G,D and S points，与weight在此图中每条边的是shortest path between them in original path。从那以后，如果 G 的数量很小（小于 17），您可以使用它dynamic programming and bitmask来解决问题。
回答by Vikram Bhat
Here there are many algorithms like dijkstra or BFS but if you need to learn an path finding algorithm then i suggest the A* algorithmas 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->Dfind the minimum for this path as min(S,G1)+min(S,G2)+min(G3,D). try all permutations of the G'sand get the minimum of them all.
这里有许多算法，如 dijkstra 或 BFS，但如果您需要学习路径查找算法，那么我建议使用A* 算法，因为它比 dijkstra 或 BFS 更快，并且可以轻松地在 2D 矩阵上实现。在必须访问节点的情况下，您可以尝试访问节点的所有序列，例如说S->G1->G2->G3->D找到此路径的最小值为min(S,G1)+min(S,G2)+min(G3,D)。尝试所有的排列G's并得到它们中的最小值。
回答by Tahlil
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.
这是一个简单的广度优先搜索算法问题。这称为泛洪填充技术，它是一种广度优先搜索算法。从这里阅读。您还可以从这里学习基本的广度优先算法。这也可以通过其他技术解决，例如 Dijkstra 或 Floyd warshal。但是广度优先搜索更容易理解。
