Python/graphs/bi_directional_dijkstra.py at master · TheAlgorithms/Python · GitHub

Name: Python/graphs/bi_directional_dijkstra.py at master · TheAlgorithms/Python · GitHub
Rating: 4.8 (6702 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
"""
Bi-directional Dijkstra's algorithm.

A bi-directional approach is an efficient and
less time consuming optimization for Dijkstra's
searching algorithm

Reference: shorturl.at/exHM7
"""

# Author: Swayam Singh (https://github.com/practice404)

fromqueueimportPriorityQueue
fromtypingimportAny

importnumpyasnp


defpass_and_relaxation(
graph: dict,
v: str,
visited_forward: set,
visited_backward: set,
cst_fwd: dict,
cst_bwd: dict,
queue: PriorityQueue,
parent: dict,
shortest_distance: float,
) ->float:
fornxt, dingraph[v]:
ifnxtinvisited_forward:
continue
old_cost_f=cst_fwd.get(nxt, np.inf)
new_cost_f=cst_fwd[v] +d
ifnew_cost_f<old_cost_f:
queue.put((new_cost_f, nxt))
cst_fwd[nxt] =new_cost_f
parent[nxt] =v
if (
nxtinvisited_backward
andcst_fwd[v] +d+cst_bwd[nxt] <shortest_distance
 ):
shortest_distance=cst_fwd[v] +d+cst_bwd[nxt]
returnshortest_distance


defbidirectional_dij(
source: str, destination: str, graph_forward: dict, graph_backward: dict
) ->int:
"""
 Bi-directional Dijkstra's algorithm.

 Returns:
 shortest_path_distance (int): length of the shortest path.

 Warnings:
 If the destination is not reachable, function returns -1

 >>> bidirectional_dij("E", "F", graph_fwd, graph_bwd)
 3
 """
shortest_path_distance=-1

visited_forward=set()
visited_backward=set()
cst_fwd= {source: 0}
cst_bwd= {destination: 0}
parent_forward= {source: None}
parent_backward= {destination: None}
queue_forward: PriorityQueue[Any] =PriorityQueue()
queue_backward: PriorityQueue[Any] =PriorityQueue()

shortest_distance=np.inf

queue_forward.put((0, source))
queue_backward.put((0, destination))

ifsource==destination:
return0

whilenotqueue_forward.empty() andnotqueue_backward.empty():
_, v_fwd=queue_forward.get()
visited_forward.add(v_fwd)

_, v_bwd=queue_backward.get()
visited_backward.add(v_bwd)

shortest_distance=pass_and_relaxation(
graph_forward,
v_fwd,
visited_forward,
visited_backward,
cst_fwd,
cst_bwd,
queue_forward,
parent_forward,
shortest_distance,
 )

shortest_distance=pass_and_relaxation(
graph_backward,
v_bwd,
visited_backward,
visited_forward,
cst_bwd,
cst_fwd,
queue_backward,
parent_backward,
shortest_distance,
 )

ifcst_fwd[v_fwd] +cst_bwd[v_bwd] >=shortest_distance:
break

ifshortest_distance!=np.inf:
shortest_path_distance=shortest_distance
returnshortest_path_distance


graph_fwd= {
"B": [["C", 1]],
"C": [["D", 1]],
"D": [["F", 1]],
"E": [["B", 1], ["G", 2]],
"F": [],
"G": [["F", 1]],
}
graph_bwd= {
"B": [["E", 1]],
"C": [["B", 1]],
"D": [["C", 1]],
"F": [["D", 1], ["G", 1]],
"E": [[None, np.inf]],
"G": [["E", 2]],
}

if__name__=="__main__":
importdoctest

doctest.testmod()