在寻找最短路径时，广度优先搜索是如何工作的？

小开

最佳答案

从技术上来说，广度优先搜索本身并不能让你找到最短的路径，仅仅是因为 BFS 并没有寻找最短的路径: BFS 描述了一种搜索图的策略，但是它并没有说你必须搜索任何特定的东西。

Dijkstra 的算法适应 BFS，让您找到单源最短路径。

为了检索从原点到节点的最短路径，您需要为图中的每个节点维护两个项: 其当前最短距离和最短路径中的前一个节点。最初，所有的距离都被设置为无穷远，所有的前辈都被设置为空。在您的示例中，您将 A 的距离设置为零，然后继续执行 BFS。在每个步骤中检查是否可以提高子代的距离，即从原点到前辈的距离加上正在探索的边缘的长度小于当前节点的最佳距离。如果可以改进距离，请设置新的最短路径，并记住获取该路径的前置路径。当 BFS 队列为空时，选择一个节点(在您的示例中，它是 E)并将其前身遍历回原点。这样你就能找到最短的路径。

如果这听起来有点令人困惑，维基百科有一个关于这个主题的不错的伪代码段伪代码段。

小开

来自教程在这里

它有一个非常有用的性质，如果一个图的所有边都没有加权(或权重相同) ，那么第一次访问一个节点时，从源节点到该节点的最短路径就是

小开

如上所述，BFS 可以用只有在以下情况下找到图中的最短路径:

没有循环
所有的边都有相同的重量或没有重量。

要找到最短的路径，你所要做的就是从源头开始，执行一个广度优先搜索，当你找到目的地节点时就停止。您需要做的唯一附加事情是使用一个前面的[ n ]数组，该数组将存储所访问的每个节点的前一个节点。源的前一个可以为空。

要打印路径，只需从源代码循环前面的[]数组，直到到达目的地并打印节点。在类似的条件下，DFS 也可以用来寻找图中的最短路径。

然而，如果图更复杂，包含加权边和循环，那么我们需要一个更复杂的 BFS 版本，即 Dijkstra 的算法。

小开

我浪费了三天时间
最终解决了一个图形问题
用于
寻找最短的距离
使用 BFS

想要分享经验。

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges


#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)


#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path


#3
It does not matter what queue you use
deque/queue(c++) or
your own queue implementation (in c language)
A circular queue is unnecessary


#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.


#5
Wikipedia BFS will work, and is sufficient.
https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

我已经失去了3天尝试以上所有的选择，验证和重新验证一次又一次以上
他们不是问题。
(如果你找不到以上5个问题，试着花时间寻找其他问题)。

更多解释 来自下面的评论:

      A
/  \
B       C
/\       /\
D  E     F  G

假设上面是你的图表
图表向下
对于 A 来说，相邻的是 B & C
B 的邻居是 D & E
C 是 F & G

比如，开始节点是 A

当你到达 A，B & C 时，从 A 到 B & C 的最短距离是1
当你到达 D 或 E，通过 B，到 A & D 的最短距离是2(A-> B-> D)

类似地，A-> E 是2(A-> B-> E)

A-> F & A-> G 是2

所以，现在节点之间的距离不是1，如果是6，那么就把答案乘以6
例如,
如果两者之间的距离为1，则 A-> E 为2(A-> B-> E = 1 + 1)
如果两者之间的距离为6，则 A-> E 为12(A-> B-> E = 6 + 6)

是的，好朋友可以采取任何方式
但我们正在计算所有的路径

如果你必须从 A 到 Z，那么我们从 A 到一个中间 I 遍历所有的路径，因为有许多路径，我们放弃所有的路径，除了最短的路径，直到 I，然后继续用最短的路径前进到下一个节点 J
如果从 I 到 J 有多条路径，我们只选择最短的一条
例如,
假设,
A-> I 我们有距离5
(步骤)假设，I-> J 我们有多条路径，距离7 & 8，因为7是最短的
我们取 A-> J 为5(A-> I 最短) + 8(现在最短) = 13
所以 A-> J 现在13岁了
我们现在对 J-> K 重复上面的步骤(STEP) ，以此类推，直到我们到达 Z

读这一部分，2或3次，并画在纸上，你一定会得到我所说的，祝你好运

小开

下面的解决方案适用于所有测试用例。

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;


public class Solution {


public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);


int testCases = sc.nextInt();


for (int i = 0; i < testCases; i++)
{
int totalNodes = sc.nextInt();
int totalEdges = sc.nextInt();


Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();


for (int j = 0; j < totalEdges; j++)
{
int src = sc.nextInt();
int dest = sc.nextInt();


if (adjacencyList.get(src) == null)
{
List<Integer> neighbours = new ArrayList<Integer>();
neighbours.add(dest);
adjacencyList.put(src, neighbours);
} else
{
List<Integer> neighbours = adjacencyList.get(src);
neighbours.add(dest);
adjacencyList.put(src, neighbours);
}




if (adjacencyList.get(dest) == null)
{
List<Integer> neighbours = new ArrayList<Integer>();
neighbours.add(src);
adjacencyList.put(dest, neighbours);
} else
{
List<Integer> neighbours = adjacencyList.get(dest);
neighbours.add(src);
adjacencyList.put(dest, neighbours);
}
}


int start = sc.nextInt();


Queue<Integer> queue = new LinkedList<>();


queue.add(start);


int[] costs = new int[totalNodes + 1];


Arrays.fill(costs, 0);


costs[start] = 0;


Map<String, Integer> visited = new HashMap<String, Integer>();


while (!queue.isEmpty())
{
int node = queue.remove();


if(visited.get(node +"") != null)
{
continue;
}


visited.put(node + "", 1);


int nodeCost = costs[node];


List<Integer> children = adjacencyList.get(node);


if (children != null)
{
for (Integer child : children)
{
int total = nodeCost + 6;
String key = child + "";


if (visited.get(key) == null)
{
queue.add(child);


if (costs[child] == 0)
{
costs[child] = total;
} else if (costs[child] > total)
{
costs[child] = total;
}
}
}
}
}


for (int k = 1; k <= totalNodes; k++)
{
if (k == start)
{
continue;
}


System.out.print(costs[k] == 0 ? -1 : costs[k]);
System.out.print(" ");
}
System.out.println();
}
}
}

小开

基于阿克伦55回答我发布了一个可能的实现给你。
下面是一个简短的总结: < br/>

你所要做的就是跟踪目标到达的路径。一个简单的方法是将到达节点的整个路径推入 Queue，而不是节点本身。
这样做的好处是，当到达目标时，队列保存了用于到达目标的路径。
这也适用于循环图，其中一个节点可以有多个父节点。

小开

在一段时间的闲置之后访问这个帖子，但是考虑到我没有看到一个完整的答案，这里是我的两点建议。

在无权图中，广度优先搜索总是能找到最短路径，图可以是循环的，也可以是非循环的。

请参见下面的伪代码。这个伪代码假设您正在使用一个队列来实现 BFS。它还假设您可以将顶点标记为访问过的，并且每个顶点存储一个距离参数，该参数被初始化为无穷大。

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
if the start vertex is the end vertex, return 0
push the start vertex on the queue
while(queue is not empty)
dequeue one vertex (we’ll call it x) off of the queue
if x is not marked as visited:
mark it as visited
for all of the unmarked children of x:
set their distance values to be the distance of x + 1
if the value of x is the value of the end vertex:
return the distance of x
otherwise enqueue it to the queue
if here: there is no path connecting the vertices

请注意，这种方法不适用于加权图——有关这一点，请参阅 Dijkstra 的算法。

小开

关于 BFS 如何计算最短路径的一个很好的解释，伴随着我所知道的最有效的简单 BFS 算法和工作代码，在下面的同行评议论文中提供:

Https://queue.acm.org/detail.cfm?id=3424304

本文介绍了 BFS 如何计算每个顶点父指针表示的最短路径树，以及如何从父指针中恢复任意两个顶点之间的特定最短路径。BFS 的解释有三种形式: 散文、伪代码和一个工作的 C 程序。

本文还介绍了“高效 BFS”(E-BFS) ，它是经典教科书 BFS 的一个简单变体，提高了它的效率。在渐近分析中，运行时间从 θ (V + E)提高到 Ω (V)。换句话说: 经典的 BFS 总是在与顶点数加边数成正比的时间内运行，而 E-BFS 有时在与单独的顶点数成正比的时间内运行，它可以小得多。在实践中，E-BFS 可以更快，这取决于输入图。E-BFS 有时比传统的 BFS 没有优势，但它从来没有慢得多。

值得注意的是，尽管其简单，E-BFS 似乎并不广为人知。