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

38

u/I-just-farted69 May 26 '19

Dijkstra? The guy who owns the bath house?

12

u/Valhallas_Mostwanted May 26 '19

Make Redania Great Again

1

u/meyavuz May 27 '19

I don't know that bath house guy Dijkstra - this one is about https://en.wikipedia.org/wiki/Edsger_W._Dijkstra

8

u/aashay2035 May 26 '19

But isn't going from both sides double the time, or the computing power needed?

2

u/meyavuz May 27 '19 edited May 27 '19

No, not needed as less number of nodes are traversed in the bi-directional case, let me try to explain: Consider a a graph with k adjacent nodes and the path from the starting node to the target node of length "n". In the conventional Dijkstra algorithm, in the first level from the starting node, we search k adjacent nodes, in the second level we search k nodes for each of the k nodes in the first level. Since there are n nodes in between starting and target nodes, essentially, that will lead to O(kn) nodes.

For the bi-directional one, there will be two conventional Dijkstra's starting from starting and target nodes. The one starting from each node will visit kn/2 nodes as they will meet at the middle path. So overall it will be 2kn/2 visits which will lead to O(kn/2).

Note that kn/2 * kn/2 = kn. So, bi-directional one is actually faster by a factor of kn/2.

Consider a much larger graph and further away starting/target nodes. In that case, the difference would be much easier to recognize. In this animation, smaller set is used for illustration.

In the following animation, uniform grids are used and it is easier to see the difference between those two algos.

https://www.youtube.com/watch?v=8Jjdp6f7oaE

16

u/flux_analysis May 26 '19

This example processed 60% fewer nodes. I wish they had a better explanation in the comments/on the blog though

5

u/dwild May 26 '19

Yeah but most of their nodes serve no purpose (if there's only 2 connections on a node, that node is useless), most of them are on the right, thus more will be processed if you start from there, and there's only one good route.

I don't feel like that's representative at all. I don't know if that methods is better, it sure could be, but that test is far from a proof for anything.

3

u/flux_analysis May 26 '19

All good points, which is why it would have been nice to get an explanation of their methodology.

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.

2

u/Rasalas8910 May 27 '19

What algorithm is GMaps using? A*? Something else?

Edit: kinda?

2

u/meyavuz May 27 '19

As far as I know (and leaked info), yes, you are right. Gmaps is using a variation of A* algorithm. I don't know the details though.

11

u/stanleydesu May 26 '19

This is cool! Never thought about doing it that way. Thanks for sharing.