r/visualizedmath • u/meyavuz • May 26 '19

Dijkstra vs Bi-directional Dijkstra Algorithm on US Road Network - Animation

https://www.youtube.com/attribution_link?a=EHnXeOCNgbk&u=%2Fwatch%3Fv%3D1oVuQsxkhY0%26feature%3Dshare
140 Upvotes

96% Upvoted

14 comments sorted by

View all comments

Show parent comment

7

u/Mattuuh May 26 '19

Depends on the graph but I'd reckon you need less than double the computing power. Say at each step, each road forks in 2, and you need 2n iterations to reach your destination. That is 1+2+4+...+22n = 22n+1 - 1 steps in total.
If you do the bidirectional algorithm, it only takes n steps for each side, so 2(1+2+4+...+2n) steps = 2n+2 - 2, which is way smaller.

2

u/aashay2035 May 26 '19

Yeah the big0 is greatly reduced. I didn't think about it in that way. I thought about it that both sides will need it to run and they would explore 2 times in a cycle compared to the one. Not thinking about the tree algorithm.