(
graph: dict,
v: str,
visited_forward: set,
visited_backward: set,
cst_fwd: dict,
cst_bwd: dict,
queue: PriorityQueue,
parent: dict,
shortest_distance: float,
)
| 17 | |
| 18 | |
| 19 | def pass_and_relaxation( |
| 20 | graph: dict, |
| 21 | v: str, |
| 22 | visited_forward: set, |
| 23 | visited_backward: set, |
| 24 | cst_fwd: dict, |
| 25 | cst_bwd: dict, |
| 26 | queue: PriorityQueue, |
| 27 | parent: dict, |
| 28 | shortest_distance: float, |
| 29 | ) -> float: |
| 30 | for nxt, d in graph[v]: |
| 31 | if nxt in visited_forward: |
| 32 | continue |
| 33 | old_cost_f = cst_fwd.get(nxt, np.inf) |
| 34 | new_cost_f = cst_fwd[v] + d |
| 35 | if new_cost_f < old_cost_f: |
| 36 | queue.put((new_cost_f, nxt)) |
| 37 | cst_fwd[nxt] = new_cost_f |
| 38 | parent[nxt] = v |
| 39 | if ( |
| 40 | nxt in visited_backward |
| 41 | and cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance |
| 42 | ): |
| 43 | shortest_distance = cst_fwd[v] + d + cst_bwd[nxt] |
| 44 | return shortest_distance |
| 45 | |
| 46 | |
| 47 | def bidirectional_dij( |
no test coverage detected