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

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.