当查找最短路径时，面包优先搜索是如何工作的?

I've done some research, and I seem to be missing one small part of this algorithm. I understand how a Breadth-First Search works, but I don't understand how exactly it will get me to a specific path, as opposed to just telling me where each individual node can go. I guess the easiest way to explain my confusion is to provide an example:

我做了一些研究，我似乎漏掉了这个算法的一小部分。我知道广度优先搜索是如何工作的，但我不知道它将如何确切地使我到达一个特定的路径，而不是仅仅告诉我每个单独的节点可以去哪里。我想最简单的解释我的困惑的方法是提供一个例子:

So for instance, let's say I have a graph like this:

举个例子，我有一个这样的图

And my goal is to get from A to E (all edges are unweighted).

我的目标是从A到E(所有边都是无权的)

I start at A, because that's my origin. I queue A, followed by immediately dequeueing A and exploring it. This yields B and D, because A is connected to B and D. I thus queue both B and D.

从A开始，因为这是原点。我排了A的队，然后马上去排A的队，去探索它。这就产生了B和D，因为A连接到B和D，所以B和D我都排队。

I dequeue B and explore it, and find that it leads to A (already explored), and C, so I queue C. I then dequeue D, and find that it leads to E, my goal. I then dequeue C, and find that it also leads to E, my goal.

我将B排在队列中，探索它，发现它会导致A(已经探索过)和C，所以我将C排在队列中，然后将D排在队列中，发现它会导致E，我的目标。然后我将C排出队列，发现它也会导致E，我的目标。

I know logically that the fastest path is A->D->E, but I'm not sure how exactly the breadth-first search helps - how should I be recording paths such that when I finish, I can analyze the results and see that the shortest path is A->D->E?

我从逻辑上知道，最快的路径是A->D->E，但我不确定广度优先搜索究竟有什么帮助——我应该如何记录路径，以便当我结束时，我可以分析结果，看到最短路径是A->D->E?

Also, note that I'm not actually using a tree, so there are no "parent" nodes, only children.

另外，请注意，我实际上并没有使用树，所以没有“父”节点，只有子节点。

6 个解决方案

#1

Technically, Breadth-first search (BFS) by itself does not let you find the shortest path, simply because BFS is not looking for a shortest path: BFS describes a strategy for searching a graph, but it does not say that you must search for anything in particular.

从技术上讲，面包优先搜索(Breadth-first search, BFS)本身不会让您找到最短路径，这仅仅是因为BFS不寻找最短路径:BFS描述了一种搜索图的策略，但它并不表示您必须搜索任何特定的东西。

Dijkstra's algorithm adapts BFS to let you find single-source shortest paths.

Dijkstra的算法利用BFS找到单源最短路径。

In order to retrieve the shortest path from the origin to a node, you need to maintain two items for each node in the graph: its current shortest distance, and the preceding node in the shortest path. Initially all distances are set to infinity, and all predecessors are set to empty. In your example, you set A's distance to zero, and then proceed with the BFS. On each step you check if you can improve the distance of a descendant, i.e. the distance from the origin to the predecessor plus the length of the edge that you are exploring is less than the current best distance for the node in question. If you can improve the distance, set the new shortest path, and remember the predecessor through which that path has been acquired. When the BFS queue is empty, pick a node (in your example, it's E) and traverse its predecessors back to the origin. This would give you the shortest path.

为了从源到节点检索最短路径，您需要为图中的每个节点保留两个项目:它当前的最短距离，以及最短路径上的前一个节点。最初，所有的距离都设置为无穷大，所有的祖先都被设置为空。在您的示例中，您将A的距离设置为0，然后继续使用BFS。在每一步中，您都要检查是否可以改善一个后代的距离，即从原点到前一个节点的距离加上您正在探索的边缘的长度，小于当前所讨论的节点的最佳距离。如果可以改进距离，那么设置新的最短路径，并记住获得该路径的前任路径。当BFS队列为空时，选择一个节点(在您的示例中是E)并将其前身遍历到原点。这将给出最短路径。

If this sounds a bit confusing, wikipedia has a nice pseudocode section on the topic.

如果这听起来有点混乱的话，*有一个关于这个话题的伪代码部分。

#2

As pointed above, BFS can only be used to find shortest path in a graph if:

如上所述，如果:

1. There are no loops

   没有循环

2. All edges have same weight or no weight.

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

To find the shortest path, all you have to do is start from the source and perform a breadth first search and stop when you find your destination Node. The only additional thing you need to do is have an array previous[n] which will store the previous node for every node visited. The previous of source can be null.

要找到最短路径，您只需从源开始执行广度优先搜索，然后在找到目标节点时停止。您需要做的惟一额外的事情是拥有一个之前的[n]数组，它将为访问的每个节点存储前一个节点。前一个源可以是空的。

To print the path, simple loop through the previous[] array from source till you reach destination and print the nodes. DFS can also be used to find the shortest path in a graph under similar conditions.

要打印路径，只需通过前面的[]数组从源到目标并打印节点。DFS还可以用于在类似条件下查找图中的最短路径。

However, if the graph is more complex, containing weighted edges and loops, then we need a more sophisticated version of BFS, i.e. Dijkstra's algorithm.

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

#3

From tutorial here

从这里的教程

"It has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node"

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

#4

I have wasted 3 days
ultimately solved a graph question
used for
finding shortest distance
using BFS

我浪费了3天最终解决了一个用BFS求最短距离的图形问题

Want to share the experience.

想要分享经验。

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

I have lost 3 days trying all above alternatives, verifying & re-verifying again and again above
they are not the issue.
(Try to spend time looking for other issues, if you dint find any issues with above 5).

我花了三天时间尝试以上所有的方案，反复验证和重新验证，以上这些都不是问题。(如果你没有发现以上5个问题，试着花时间去寻找其他的问题)。

---

More explanation from the comment below:

以下评论提供更多解释:

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

Assume above is your graph
graph goes downwards
For A, the adjacents are B & C
For B, the adjacents are D & E
For C, the adjacents are F & G

假设上面是A的图向下，B的邻接为B和C, C的邻接为D和E，邻接为F和G

say, start node is A

比如，开始节点是A

1. when you reach A, to, B & C the shortest distance to B & C from A is 1

   当你到达A，到，B和C时，从A到B和C的最短距离是1

2. when you reach D or E, thru B, the shortest distance to A & D is 2 (A->B->D)

   当你到达D或E，通过B，到A和D的最短距离是2 (A->B->D)

similarly, A->E is 2 (A->B->E)

同样，A->E等于2 (A->B->E)

also, A->F & A->G is 2

A->F和A->G是2

So, now instead of 1 distance between nodes, if it is 6, then just multiply the answer by 6
example,
if distance between each is 1, then A->E is 2 (A->B->E = 1+1)
if distance between each is 6, then A->E is 12 (A->B->E = 6+6)

那么，现在不是1个节点之间的距离，如果是6，那么只需将答案乘以6个例子，如果每个节点之间的距离是1，那么A->E就是2 (A->B-> = 1+1)如果每个节点之间的距离是6，那么A->E就是12 (A->B- bb5 E = 6+6)

yes, bfs may take any path
but we are calculating for all paths

是的，bfs可以选择任何路径，但是我们正在计算所有路径

if you have to go from A to Z, then we travel all paths from A to an intermediate I, and since there will be many paths we discard all but shortest path till I, then continue with shortest path ahead to next node J
again if there are multiple paths from I to J, we only take shortest one
example,
assume,
A -> I we have distance 5
(STEP) assume, I -> J we have multiple paths, of distances 7 & 8, since 7 is shortest
we take A -> J as 5 (A->I shortest) + 8 (shortest now) = 13
so A->J is now 13
we repeat now above (STEP) for J -> K and so on, till we get to Z

如果你从A到Z,然后我们所有路径从一个中间我旅行,因为会有许多路径我们抛弃所有,但直到我最短路径,然后继续前进到下一个节点的最短路径J再次从我到J如果有多条路径,我们只取最短的一个例子,假设,5 - >我我们有距离(步骤)假设,I - > J我们有多条路径,距离7和8的因为7是最短的，我们取A->J = 5 (A->I最短)+ 8(现在最短)= 13所以A->J现在是13我们在上面(步骤)对J -> K，等等，直到我们到达Z

Read this part, 2 or 3 times, and draw on paper, you will surely get what i am saying, best of luck

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

---

#5

Based on acheron55 answer I posted a possible implementation here.
Here is a brief summery of it:

基于acheron55的回答，我在这里发布了一个可能的实现。这里有一个简短的总结:

All you have to do, is to keep track of the path through which the target has been reached. A simple way to do it, is to push into the Queue the whole path used to reach a node, rather than the node itself.
The benefit of doing so is that when the target has been reached the queue holds the path used to reach it.
This is also applicable to cyclic graphs, where a node can have more than one parent.

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

#6

The following solution works for all the test cases.

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

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();
            }
        }
}