5 ms·

Using Dijkstra's algorithm to draw maps

161 points by JasonNils 11y ago

elcapitan 11y ago
Isn't that actually an example for graph centrality (betweenness)? https://en.wikipedia.org/wiki/Centrality https://en.wikipedia.org/wiki/Centrality
- 14113 11y ago
  Yes - one of the classical ways of computing betweeness centrality is to calculate the number of shortest paths passing through each edge. In this case however, he's only computing the shortest paths to/from a single vertex.
tocklime 11y ago
This is actually really useful - you have a map of 'what is the fastest way home from anywhere in the city?' On moving to a new city, getting a map like this and memorising a few of the arteries would help loads with familiarization.
- sitkack 11y ago
  This isn't exactly what the OP has, what you are looking for is a transit time heat map. http://www.transitheatmap.com/index.html http://www.transitheatmap.com/index.html http://project.wnyc.org/transit-time/#40.72280,-73.95464,12,669 http://project.wnyc.org/transit-time/#40.72280,-73.95464,12,...
  - nostrebored 11y ago
    If you are busing... Sure the argument can be made that this doesn't take into account light-timers for walking, but if you're greedily selecting for shortest distance, this is exactly what you want when walking.
    - dsp1234 11y ago
      If you are busing... Transit heat maps are generally used for autos and buses, but could just as easily be made for walking. You'd just code the average wait time for timers into the heat map algorithm.
jilljennV 11y ago
So much fun! We made a similar visualization in Python, using Dijkstra's algorithm to find shortest paths in Paris: http://nbviewer.jupyter.org/github/jilljenn/tryalgo/blob/master/examples/TryAlgo%20Maps%20in%20Paris.ipynb http://nbviewer.jupyter.org/github/jilljenn/tryalgo/blob/mas... Also for trying different greedy routing algorithms. Folium helps a lot: http://nbviewer.jupyter.org/github/jilljenn/128algos/blob/master/TryAlgo%20in%20Paris.ipynb http://nbviewer.jupyter.org/github/jilljenn/128algos/blob/ma... Disclaimer: I'm a co-author of the tryalgo package.
coroutines 11y ago
You cannot mention Dijkstra's algorithm without linking: http://www.redblobgames.com/pathfinding/ http://www.redblobgames.com/pathfinding/ http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction.... :-)
- testpass 11y ago
  Graph theory has been one of the most difficult topics I've had to grasp at university. This is awesome! Thanks for sharing.
MarcosDione 11y ago
very nice! related to this: http://www.imagico.de/map/water_generalize1_en.php http://www.imagico.de/map/water_generalize1_en.php also: it's shame how it treats the transpacific plane routes...
coredog64 11y ago
Nitpick: I don't think the world flights to Paris map is correct. It shows flights from Noumea, New Caledonia going through Australia. The shorter route is through Seoul.
Bedon292 11y ago
Very interesting. How are the roads weighted in this? Meaning is there any travel time involved? Or is it just length? It would be interesting to play with different weighting and see if it changes.
- karussell 11y ago
  Should be time in all cases (if default settings of the routing engines are used)
yalogin 11y ago
This is awesome. I wanted to something like this for a long time but never got around to it.
karussell 11y ago
The roads to rome is indeed not open source although the tools are: http://roadstorome.moovellab.com/about http://roadstorome.moovellab.com/about I was also playing around with this and GraphHopper as well: https://graphhopper.com/blog/2016/01/19/alternative-roads-to-rome/ https://graphhopper.com/blog/2016/01/19/alternative-roads-to... Using some simple modification of the MiniUIGraph tool which you can find here: https://gist.github.com/karussell/768e828a01f71ac7f46c https://gist.github.com/karussell/768e828a01f71ac7f46c BTW: If you have questions related to GraphHopper feel free to ask them :) BTW2: Funny how this visualization side-project got more stars in a few hours then one of the used routing engines in 4 years. Bad marketing ;) ?

161 points by JasonNils 11y ago

Isn't that actually an example for graph centrality (betweenness)? https://en.wikipedia.org/wiki/Centrality https://en.wikipedia.org/wiki/Centrality

14113 11y ago
Yes - one of the classical ways of computing betweeness centrality is to calculate the number of shortest paths passing through each edge. In this case however, he's only computing the shortest paths to/from a single vertex.

tocklime 11y ago

This is actually really useful - you have a map of 'what is the fastest way home from anywhere in the city?' On moving to a new city, getting a map like this and memorising a few of the arteries would help loads with familiarization.

sitkack 11y ago
This isn't exactly what the OP has, what you are looking for is a transit time heat map. http://www.transitheatmap.com/index.html http://www.transitheatmap.com/index.html http://project.wnyc.org/transit-time/#40.72280,-73.95464,12,669 http://project.wnyc.org/transit-time/#40.72280,-73.95464,12,...
- nostrebored 11y ago
  If you are busing... Sure the argument can be made that this doesn't take into account light-timers for walking, but if you're greedily selecting for shortest distance, this is exactly what you want when walking.
  - dsp1234 11y ago
    If you are busing... Transit heat maps are generally used for autos and buses, but could just as easily be made for walking. You'd just code the average wait time for timers into the heat map algorithm.

jilljennV 11y ago

So much fun! We made a similar visualization in Python, using Dijkstra's algorithm to find shortest paths in Paris: http://nbviewer.jupyter.org/github/jilljenn/tryalgo/blob/master/examples/TryAlgo%20Maps%20in%20Paris.ipynb http://nbviewer.jupyter.org/github/jilljenn/tryalgo/blob/mas... Also for trying different greedy routing algorithms. Folium helps a lot: http://nbviewer.jupyter.org/github/jilljenn/128algos/blob/master/TryAlgo%20in%20Paris.ipynb http://nbviewer.jupyter.org/github/jilljenn/128algos/blob/ma... Disclaimer: I'm a co-author of the tryalgo package.

coroutines 11y ago

You cannot mention Dijkstra's algorithm without linking: http://www.redblobgames.com/pathfinding/ http://www.redblobgames.com/pathfinding/ http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction.... :-)

testpass 11y ago
Graph theory has been one of the most difficult topics I've had to grasp at university. This is awesome! Thanks for sharing.

MarcosDione 11y ago

very nice! related to this: http://www.imagico.de/map/water_generalize1_en.php http://www.imagico.de/map/water_generalize1_en.php also: it's shame how it treats the transpacific plane routes...

coredog64 11y ago

Nitpick: I don't think the world flights to Paris map is correct. It shows flights from Noumea, New Caledonia going through Australia. The shorter route is through Seoul.

Bedon292 11y ago

Very interesting. How are the roads weighted in this? Meaning is there any travel time involved? Or is it just length? It would be interesting to play with different weighting and see if it changes.

karussell 11y ago
Should be time in all cases (if default settings of the routing engines are used)

yalogin 11y ago

This is awesome. I wanted to something like this for a long time but never got around to it.

karussell 11y ago

The roads to rome is indeed not open source although the tools are: http://roadstorome.moovellab.com/about http://roadstorome.moovellab.com/about I was also playing around with this and GraphHopper as well: https://graphhopper.com/blog/2016/01/19/alternative-roads-to-rome/ https://graphhopper.com/blog/2016/01/19/alternative-roads-to... Using some simple modification of the MiniUIGraph tool which you can find here: https://gist.github.com/karussell/768e828a01f71ac7f46c https://gist.github.com/karussell/768e828a01f71ac7f46c BTW: If you have questions related to GraphHopper feel free to ask them :) BTW2: Funny how this visualization side-project got more stars in a few hours then one of the used routing engines in 4 years. Bad marketing ;) ?