def bidir_dijkstra(nodes: list[Node], src_id: int, dst_id: int, hff=(lambda _: 0.0), hfb=(lambda _: 0.0), consistent: bool=True) -> list[int]:
    '\n    bidirectionnal dijkstra, we search from both start => end\n    and end => start using two iterators.\n    hff and hfb are optional heuristics\n    for respectively the forward and backward iterators\n    (for later bidir A*)\n    '
    forward = dijkstra_iterator(nodes, src_id, hf=hff)
    backward = dijkstra_iterator(nodes, dst_id, hf=hfb)
    shortest = sys.maxsize
    forward_node = backward_node = None
    f = []
    b = []
    for (idx, (ctx_forward, ctx_backward)) in enumerate(zip(forward, backward)):
        if any(((x.node is None) for x in (ctx_forward, ctx_backward))):
            return ([], [], (f, b))
        f.append(ctx_forward.node)
        b.append(ctx_backward.node)
        if (forward_node and ((not consistent) or (sum(((x.distances[x.node.id] - hf(x.node)) for (x, hf) in ((ctx_forward, hff), (ctx_backward, hfb)))) >= shortest))):
            forward_path = build_shortest_path(ctx_forward.previous, forward_node.id, src_id)
            backward_path = build_shortest_path(ctx_backward.previous, backward_node.id, dst_id)[::(- 1)]
            path = (forward_path + backward_path)
            return (shortest, path, (f, b))
        else:
            for ((ctx, hf), (ctx2, hf2)) in permutations(((ctx_forward, hff), (ctx_backward, hfb)), 2):
                for (n, d) in ctx.node.neighbours.items():
                    if (n in ctx2.visited_nodes):
                        distance = ((((ctx.distances[ctx.node.id] + ctx2.distances[n]) + d) - hf(ctx.node)) - hf2(nodes[n]))
                        if (distance < shortest):
                            shortest = distance
                            forward_node = (ctx.node if (ctx is ctx_forward) else nodes[n])
                            backward_node = (ctx.node if (ctx is ctx_backward) else nodes[n])
                            print(f'Iter_{idx}: contact between {forward_node}->{backward_node} with d={shortest}')
bidirectionnal dijkstra, we search from both start => end
and end => start using two iterators.
hff and hfb are optional heuristics
for respectively the forward and backward iterators
(for later bidir A*)
def bidir_dijkstra(nodes: list[Node], src_id: int, dst_id: int, hff=(lambda _: 0.0), hfb=(lambda _: 0.0), consistent: bool=True) -> list[int]:
    '\n    bidirectionnal dijkstra, we search from both start => end\n    and end => start using two iterators.\n    hff and hfb are optional heuristics\n    for respectively the forward and backward iterators\n    (for later bidir A*)\n    '
    forward = dijkstra_iterator(nodes, src_id, hf=hff)
    backward = dijkstra_iterator(nodes, dst_id, hf=hfb)
    shortest = sys.maxsize
    forward_node = backward_node = None
    f = []
    b = []
    for (idx, (ctx_forward, ctx_backward)) in enumerate(zip(forward, backward)):
        if any(((x.node is None) for x in (ctx_forward, ctx_backward))):
            return ([], [], (f, b))
        f.append(ctx_forward.node)
        b.append(ctx_backward.node)
        if (forward_node and ((not consistent) or (sum(((x.distances[x.node.id] - hf(x.node)) for (x, hf) in ((ctx_forward, hff), (ctx_backward, hfb)))) >= shortest))):
            forward_path = build_shortest_path(ctx_forward.previous, forward_node.id, src_id)
            backward_path = build_shortest_path(ctx_backward.previous, backward_node.id, dst_id)[::(- 1)]
            path = (forward_path + backward_path)
            return (shortest, path, (f, b))
        else:
            for ((ctx, hf), (ctx2, hf2)) in permutations(((ctx_forward, hff), (ctx_backward, hfb)), 2):
                for (n, d) in ctx.node.neighbours.items():
                    if (n in ctx2.visited_nodes):
                        distance = ((((ctx.distances[ctx.node.id] + ctx2.distances[n]) + d) - hf(ctx.node)) - hf2(nodes[n]))
                        if (distance < shortest):
                            shortest = distance
                            forward_node = (ctx.node if (ctx is ctx_forward) else nodes[n])
                            backward_node = (ctx.node if (ctx is ctx_backward) else nodes[n])
                            print(f'Iter_{idx}: contact between {forward_node}->{backward_node} with d={shortest}')