英文:
How to get shortest path between two nodes with Breadth First Search?
问题
我正在复习我的算法和数据结构知识，想知道是否有人可以帮助我找出如何使用 BFS 找到两个节点之间的最短路径。
到目前为止，我有以下方法，它可以在图中返回最短路径：
private Node[] nodes;
public static int[] shortestPath(Node source){
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(source);
int[] distances = new int[totalNodes];
Arrays.fill(distances,-1);
distances[source] = 0;
while(!queue.isEmpty()){
Node node = queue.poll();
for (int neighbor: nodes[node].neighbor) {
if(distances[neighbor] == -1) {
distances[neighbor] += distances[distanceIndex] + 1;
queue.add(neighbor);
}
}
}
return distances;
}
我想知道如果我想要实现一个像这样的方法，该怎么写：
public static int[] shortestPath(Node source, Node destination){
// 在这里实现
}
非常感谢您的帮助，我是数据结构方面的新手，不太确定该如何处理这个问题。
英文:
I am brushing up my algorithm and data structure knowledge and was wondering if someone could help me figure out how to find the shortest path between two nodes with BFS.
So far I am have the following method, which returns the shortest parth in a graph:
private Node[] nodes;
public static int[] shortestPath(Node source){
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(source);
int[] distances = new int[totalNodes];
Arrays.fill(distances,-1);
distances[source] = 0;
while(!queue.isEmpty()){
Node node = queue.poll();
for (int neighbor: nodes[node].neighbor) {
if(distances[neighbor] == -1) {
distances[neighbor] += distances[distanceIndex] + 1;
queue.add(neighbor);
}
}
}
return distances;
}
}
I was wondering how would the solution look if I wanted to implement a method like this:
public static int[] shortestPath(Node source, Node destination){
//
}
Thanks in advance for the help, I am new to data structures and not sure how to go about it
答案1
得分: 1
private Node[] nodes;
public static int shortestPath(Node source, Node destination){
LinkedList
queue.add(source);
int[] distances = new int[totalNodes];
Arrays.fill(distances, -1);
distances[source] = 0;
while(!queue.isEmpty()){
Node node = queue.poll();
for (int neighbor : nodes[node].neighbor) {
if (distances[neighbor] == -1) {
distances[neighbor] += distances[node] + 1;
queue.add(neighbor);
if (neighbor == destination)
break;
}
}
}
return distances[destination];
}
英文:
private Node[] nodes;
public static int shortestPath(Node source, Node destination){
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(source);
int[] distances = new int[totalNodes];
Arrays.fill(distances,-1);
distances[source] = 0;
while(!queue.isEmpty()){
Node node = queue.poll();
for (int neighbor: nodes[node].neighbor) {
if(distances[neighbor] == -1) {
distances[neighbor] += distances[node] + 1;
queue.add(neighbor);
if(neighbor == destination)
break;
}
}
}
return distances[destination];
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论