Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - How do you use a Bidirectional BFS to find the shortest path?

How do you use a Bidirectional BFS to find the shortest path? Let's say there is a 6x6 grid. The start point is in (0,5) and the end point is in (4,1). What is the shortest path using bidirectional bfs? There are no path costs. And it is undirected.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

How does Bi-directional BFS work?

Simultaneously run two BFS's from both source and target vertices, terminating once a vertex common to both runs is discovered. This vertex will be halfway between the source and the target.

Why is it better than BFS?

Bi-directional BFS will yield much better results than simple BFS in most cases. Assume the distance between source and target is k, and the branching factor is B (every vertex has on average B edges).

  • BFS will traverse 1 + B + B^2 + ... + B^k vertices.
  • Bi-directional BFS will traverse 2 + 2B^2 + ... + 2B^(k/2) vertices.

For large B and k, the second is obviously much faster the the first.


In your case:

For simplicity I am going to assume that there are no obstacles in the matrix. Here is what happens:

iteration 0 (init):
front1 = { (0,5) }
front2 = { (4,1) }

iteration 1: 
front1 = { (0,4), (1,5) }
front2 = { (4,0), (4,2), (3,1), (5,1) }

iteration 2:
front1 = { (0,3), (1,4), (2,5) }
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) }

iteration 3:
front1 = { (0,2), (1,3), (2,4), (3,5) }
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), }

iteration 4:
front1 = { (0,1), (1,2), .... }
front2 = { (1,2) , .... }

Now, we have discovered that the fronts intersect at (1,2), together with the paths taken to get there from the source and target vertices:

path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2)
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2)

We now just need to reverse path 2 and append it to path 1 (removing one of the common intersecting vertices of course), to give us our complete path:

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...