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
(
source: str, destination: str, graph_forward: dict, graph_backward: dict
)
| 45 | |
| 46 | |
| 47 | def bidirectional_dij( |
| 48 | source: str, destination: str, graph_forward: dict, graph_backward: dict |
| 49 | ) -> int: |
| 50 | """ |
| 51 | Bi-directional Dijkstra's algorithm. |
| 52 | |
| 53 | Returns: |
| 54 | shortest_path_distance (int): length of the shortest path. |
| 55 | |
| 56 | Warnings: |
| 57 | If the destination is not reachable, function returns -1 |
| 58 | |
| 59 | >>> bidirectional_dij("E", "F", graph_fwd, graph_bwd) |
| 60 | 3 |
| 61 | """ |
| 62 | shortest_path_distance = -1 |
| 63 | |
| 64 | visited_forward = set() |
| 65 | visited_backward = set() |
| 66 | cst_fwd = {source: 0} |
| 67 | cst_bwd = {destination: 0} |
| 68 | parent_forward = {source: None} |
| 69 | parent_backward = {destination: None} |
| 70 | queue_forward: PriorityQueue[Any] = PriorityQueue() |
| 71 | queue_backward: PriorityQueue[Any] = PriorityQueue() |
| 72 | |
| 73 | shortest_distance = np.inf |
| 74 | |
| 75 | queue_forward.put((0, source)) |
| 76 | queue_backward.put((0, destination)) |
| 77 | |
| 78 | if source == destination: |
| 79 | return 0 |
| 80 | |
| 81 | while not queue_forward.empty() and not queue_backward.empty(): |
| 82 | _, v_fwd = queue_forward.get() |
| 83 | visited_forward.add(v_fwd) |
| 84 | |
| 85 | _, v_bwd = queue_backward.get() |
| 86 | visited_backward.add(v_bwd) |
| 87 | |
| 88 | shortest_distance = pass_and_relaxation( |
| 89 | graph_forward, |
| 90 | v_fwd, |
| 91 | visited_forward, |
| 92 | visited_backward, |
| 93 | cst_fwd, |
| 94 | cst_bwd, |
| 95 | queue_forward, |
| 96 | parent_forward, |
| 97 | shortest_distance, |
| 98 | ) |
| 99 | |
| 100 | shortest_distance = pass_and_relaxation( |
| 101 | graph_backward, |
| 102 | v_bwd, |
| 103 | visited_backward, |
| 104 | visited_forward, |
nothing calls this directly
no test coverage detected