graphs.bi_directional_dijkstra

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

Attributes

graph_bwd
graph_fwd

Functions

bidirectional_dij(→ int)	Bi-directional Dijkstra's algorithm.
pass_and_relaxation(→ float)

Module Contents

graphs.bi_directional_dijkstra.bidirectional_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

graphs.bi_directional_dijkstra.pass_and_relaxation(graph: dict, v: str, visited_forward: set, visited_backward: set, cst_fwd: dict, cst_bwd: dict, queue: queue.PriorityQueue, parent: dict, shortest_distance: float) → float

graphs.bi_directional_dijkstra.graph_bwd

graphs.bi_directional_dijkstra.graph_fwd