Repository files navigation

Dijkstra’s algorithm: Dijkstra’s is shortest path algorithm, whichfollows greedy based approach to determine the shortest path from asingle source weight graph ((G)), where the weight of each edge from(u) to (v) is non-negative i.e. (w(u,v) \geq 0). Initially, sourcevertex is assigned a cost of 0 and all other vertex assigned with(\infty) cost. To find the shortest path, Dijkstra’s picks theunvisited vertex with the lowest cost, then calculated the cost fromsource to each unvisited neighbour vertex. Time complexity forDijkstra’s Algorithm is (O(n^2))

Bidirectional Dijkstra algorithm:
1. Alternate between forward traversal from (source) node andbackward traversal from (target) node
2. Calculate (d_f(v)) distance for forward traversal
3. Calculate (d_b(v)) distance for backward traversal
4. Stop when (Q_f) and (Q_b) queues are empty
5. After traversal end, find node (u) with min value of(d_f(u) + d_b(u)) 6. Find shortest path from (source) to (u) andfrom (u) to (target), combine both paths to get final shortest pathin a graph

Running time for finding shortest path between two points can beimproved by implemented bidirectional search along with Dijkstraalgorithm i.e. executing Dijkstra algorithm from both directions (fromsource node to target node and vice versa) simultaneously. For ahomogeneous graph Bidirectional Dijkstra approach has runtime of(O(2*(n/2)^2)), i.e. 2 times faster.

Consider that we have to find the shortest path between Dublin and Corkcity, then Bidirectional Dijkstra algorithm will start exploring pathsfrom both cities at same time and algorithm will stop traversing whenboth paths meet i.e. when a node is scanned from both directions.However, if Dijkstra has been used here then it will take more time tofind the shortest path, as algorithm will start traversing from a sourcenode (i.e. Dublin city) and stop when it reaches target node (i.e. Corkcity)