*...*..D
.G..*.....
**...**.
.S....*.
........
...G**..
........
.G..*...
这里是2d数组,其中
S-源
d -目的
g -点必须访问
。"。"自由路径
"*"块路径
你能帮我找到java中最短路径长度的有效算法吗
只有水平和垂直移动是可能的
要找到从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));
}
}
}
}
这个问题的第二条路径实际上是一个旅行推销员问题,所以你需要从你的原始图转换成一个only contains G,D and S points
的图,这个图中每条边的weight
是shortest path between them in original path
。从那以后,如果G的数量很小(小于17),您可以使用dynamic programming and bitmask
来解决这个问题。
这里有许多算法,如dijkstra或BFS,但如果你需要学习寻径算法,那么我建议A*算法,因为它比dijkstra或BFS更快,可以很容易地在2D矩阵上实现。在必须访问节点的情况下,您可以尝试访问节点的所有序列,例如S->G1->G2->G3->D
,找到该路径的最小值min(S,G1)+min(S,G2)+min(G3,D)
。尝试G's
的所有排列并得到它们中的最小值
这是一个简单的广度优先搜索算法问题。这被称为洪水填充技术,这是一种宽度优先搜索算法。从这里开始阅读。您还可以从这里学习基本的广度优先算法。这也可以通过Dijkstra或Floyd warshal等其他技术来解决。但广度优先的搜索更容易理解。