Python implementation of bidirectional Dijkstra algorithm
Article directory
- Bidirectional Dijkstra algorithm Python implementation
-
- Introduction
- Advantages of Bidirectional Dijkstra Algorithm
- limitation
- Basic steps of the algorithm
-
- Termination condition
- The basic steps
- pseudocode
- Python implementation
- Comparison of two-way Dijkstra and one-way Dijkstra algorithms
Introduction
Bidirectional Dijkstra Algorithm is an algorithm used to find the shortest path between two vertices in a weighted graph. It is a variant of Dijkstra’s algorithm. The basic idea is: search from two directions simultaneously Start searching – perform Dijkstra’s algorithm search simultaneously from the starting point to the end point and from the end point to the starting point. If there is a path, then the search in the two directions will eventually meet and terminate at a certain point, and this path is the shortest distance path. In some cases, the bidirectional Dijkstra’s algorithm can reduce the search space size, thereby increasing the algorithm’s efficiency. There is also the idea of divide and conquer
Advantages of the two-way Dijkstra algorithm
Compared with Dijkstra’s algorithm, the bidirectional Dijkstra algorithm has more advantages in the following situations:
-
Large-scale graph search: If the size of the graph is large, the bidirectional Dijkstra algorithm is likely to be faster than Dijkstra’s algorithm.
-
Sparse graphs: In sparse graphs, the bidirectional Dijkstra algorithm is likely to be faster than Dijkstra’s algorithm.
The main reason is that bidirectional search can reduce a certain amount of search space. Searching from the end point and starting from the starting point is equivalent to pruning.
(I think this picture vividly explains why the bidirectional Dijkstra algorithm can reduce the search space, while the single-term Dijkstra algorithm will become more and more divergent in large-scale graphs)
Limitations
- Complexity: The bidirectional Dijkstra algorithm requires more complex data structures to keep track of search paths in both directions. The algorithm requires more time to maintain queues in both directions.
- Graphs with unequal weights and negative weights: For graphs with large differences in edge weights and negative weights, the two-way Dijkstra algorithm may not perform well.
- When the distance between the end point and the starting point is relatively close, the bidirectional Dijkstra algorithm may not be as good as the single Dijkstra algorithm.
But bidirectional Dijkstra still has the advantages of reducing the search space and searching the shortest path faster.
Basic steps of the algorithm
Termination condition
The most important thing about the two-way Dijkstra algorithm is the termination condition, when the algorithm should terminate, and how to determine the meeting point at which the algorithm should terminate. The two-way Dijkstra algorithm needs to maintain two queues, one is the queue from the starting point to the end point queue_from_start and queue_from_target, assuming:
t
o
p
f
top_f
topf? is the head element of the queue_from_start priority queue,
t
o
p
r
top_r
topr? is the head element of the queue_from_target priority queue,
μ
\mu
μ is used to record the path value formed by the meeting point, initialized
μ
=
∞
\mu = \infty
μ=∞. When performing path search, when there is an edge
(
u
,
v
)
(u,v)
(u,v) satisfies
u
u
u is in forward search, while
v
v
v In reverse search, if
d
f
(
u
)
+
c
(
u
,
v
)
+
d
r
(
v
)
< μ d_f(u) + c(u,v) + d_r(v) < \mu df?(u) + c(u,v) + dr?(v)<μ, then update μ \mu μ value.
Termination condition:
t
o
p
f
+
t
o
p
r
≥
μ
top_f + top_r \ge \mu
topf? + topr?≥μ
Basic steps
- Initialization: Add the starting point to the pending queue for forward search, and add the end point to the pending queue for reverse search.
- Iterative search: In each iteration, the algorithm processes the vertices in the forward and reverse queues to be processed respectively, and selects the vertex with the smallest current distance for expansion.
- Extend vertices: For the selected vertex, the algorithm updates the shortest path estimates of its adjacent vertices and adds these adjacent vertices to the corresponding set to be processed.
- Check for meeting: After each expansion, the algorithm checks whether the forward and reverse searches meet at a vertex. The encounter condition is usually to check whether a vertex appears in both the forward and reverse access lists.
- Path reconstruction: Once the search encounters, the algorithm uses forward and reverse path information to reconstruct the shortest path from the starting point to the end point.
- Termination condition: If the two searches meet somewhere in the middle, or the search in one direction cannot find new vertices for expansion, the algorithm terminates.
Pseudocode
Program structure:
function BidirectionalDijkstra(graph, start, end)
create priority queues queueFromStart, queueFromEnd
add start to queueFromStart with priority 0
add end to queueFromEnd with priority 0
create distance maps distanceFromStart, distanceFromEnd and set all distances to infinity
set distanceFromStart[start] to 0
set distanceFromEnd[end] to 0
create parent maps parentFromStart, parentFromEnd and set all parents to null
set parentFromStart[start] to start
set parentFromEnd[end] to end
while queueFromStart and queueFromEnd are not empty
nodeFromStart = extract minimum from queueFromStart
for each neighbor of nodeFromStart
if distance through nodeFromStart to neighbor is less than distanceFromStart[neighbor]
update distanceFromStart[neighbor]
update parentFromStart[neighbor]
add neighbor to queueFromStart with priority distanceFromStart[neighbor]
nodeFromEnd = extract minimum from queueFromEnd
for each neighbor of nodeFromEnd
if distance through nodeFromEnd to neighbor is less than distanceFromEnd[neighbor]
update distanceFromEnd[neighbor]
update parentFromEnd[neighbor]
add neighbor to queueFromEnd with priority distanceFromEnd[neighbor]
if any node v is in both queueFromStart and queueFromEnd
path = shortest path from start to v according to parentFromStart
path = path + reverse of shortest path from v to end according to parentFromEnd
return path
return no path
\t
Python implementation
def bidirectional_dijkstra_b(graph, start, target, i):
queue_from_start = []
hq.heappush(queue_from_start, (0.0, start))
distance_from_start = {<!-- -->node: float('infinity') for node in graph}
distance_from_start[start] = 0.0
parents_of_start = {<!-- -->start: None}
queue_from_target = []
hq.heappush(queue_from_target, (0.0, target))
distance_from_target = {<!-- -->node: float('infinity') for node in graph}
distance_from_target[target] = 0.0
parents_of_target = {<!-- -->target: None}
close_of_start = set() # Access the closed table
close_of_target = set() # Access the closed table
miu = math.inf
global node
node=None
while queue_from_start and queue_from_target:
if queue_from_start[0][0] + queue_from_target[0][0] >= miu:
return reverse_traversal(node, parents_of_start, parents_of_target)
cur_dist, cur_node = hq.heappop(queue_from_start)
close_of_start.add(cur_node)
for adjacent, weight in graph[cur_node].items():
if adjacent in close_of_start:
continue
distance = cur_dist + weight["weight"]
if distance < distance_from_start[adjacent]:
distance_from_start[adjacent] = distance
parents_of_start[adjacent] = cur_node
hq.heappush(queue_from_start, (distance, adjacent))
# Update miu value
if adjacent in close_of_target:
dist = distance + distance_from_target[adjacent]
if miu > dist:
miu = dist
node=adjacent
cur_dist, cur_node = hq.heappop(queue_from_target)
close_of_target.add(cur_node)
for adjacent, weight in graph[cur_node].items():
if adjacent in close_of_target:
continue
distance = cur_dist + weight["weight"]
if distance < distance_from_target[adjacent]:
distance_from_target[adjacent] = distance
parents_of_target[adjacent] = cur_node
hq.heappush(queue_from_target, (distance, adjacent))
if adjacent in close_of_start:
dist = distance + distance_from_start[adjacent]
if miu > dist:
miu = dist
node=adjacent
return []
Comparison of two-way Dijkstra and one-way Dijkstra algorithms
Two versions of the bidirectional Dijkstra algorithm have been written, mainly due to different control methods.
The standard for generating sparse graphs in experiments is,
e
=
n
?
log
?
n
e=n*\log{n}
e=n?logn
It can be seen that as the number of nodes and edges increases, the algorithm becomes more time-consuming. When the number of nodes = 50000 and the number of edges = 252959, the speed of Dijkstra’s algorithm is much higher than that of the two-way Dijkstra algorithm. algorithm.
From the above figure, when the number of nodes is on the order of 50,500, the second control flow Dijkstra algorithm is faster, but as the number of nodes increases, the first control flow is bidirectional. The pull algorithm is better. Speculative conclusion: The two-way Dijkstra algorithm contains the idea of divide and conquer. The more equal the number of explorations on both sides, the better.