How does a Breadth-First Search work when looking

问题:

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).

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.

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.

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?

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

回答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.

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

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.

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.

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.

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.

回答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

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).

---

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

say, start node is A

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

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

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

also, A->F & A->G is 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)

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

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

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

---

回答5:

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

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