2d数组中的最短路径

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

这是2d数组在哪里
S-来源
d-目的地
必须访问G-Point
“。”自由路径
“*”阻止路径
你能帮助我，这是找到java中最短路径长度的有效算法
只能进行水平和垂直移动

Answer 1

要查找从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 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 = px + x[i]; int b = py + y[i]; if(a >= 0 && b >= 0 && a < n && b < m && dist[a][b] == -1 && map[a].charAt(b) != '*' ){ dist[a][b] = 1 + dist[px][py]; q.add(new Point(a,b)); } } } } 

问题的第二个路径实际上是旅行商问题 ，因此您需要将原始图表转换为only contains G,D and S points图表，此图表中每条边的weight是shortest path between them in original path的shortest path between them in original path 。 从那时起，如果G的数量很小（小于17），您可以使用dynamic programming and bitmask来解决问题。

Answer 2

这里有许多算法，如dijkstra或BFS，但是如果你需要学习路径寻找算法，那么我建议使用A *算法，因为它比dijkstra或BFS更快，并且可以在2D矩阵上轻松实现。 在必须访问节点的情况下，您可以尝试访问节点的所有序列，例如说S->G1->G2->G3->D找到此路径的最小值为min(S,G1)+min(S,G2)+min(G3,D) 。 尝试G's所有排列并获得最小值。

Answer 3

这是一个简单的广度优先搜索算法问题。 这称为泛洪填充技术，它是一种广度优先搜索算法。 从这里阅读。 您还可以从此处学习基本的宽度优先算法。 这也可以通过Dijkstra或Floyd warshal等其他技术来解决。 但广度优先搜索更容易理解。