Maps using Dijkstra's algo.

[Redrobes]

Came across this today in the tech news sites. Its a mapping algorithm based on Djikstras algorithm of visiting every node once thing. I thought it was interesting since it is basically optimising the paths for shortest distance which is not so dissimilar to mapping using economics which was also optimizing based on most profitable / least costly basis too which I had a go at a few years back. I am sure that there is some big reward to whomever cracks this nut !

https://github.com/ibaaj/dijkstra-cartography

Its github so go get that source and play with it.

[waldronate]

It's interesting from an artistic perspective (as was the parent discussion) in that it shows the shortest path from a place to a central location as well as the most-traveled ways into that central location. The original site references has some fun examples that are colored, as well. I'm just not so sure that it's answering an interesting technical question. Not for the sorts of things that I'm interested in, anyhow. This operation requires a preexisting transport network and identification of a central place. Probably just a lack of imagination on my part.

I'm much more into creating mapping stuff like rivers and roads (totally outside the context of this sort of thing, which focuses solely on traversing existing graphs). For that sort of thing, something like A* would probably be a better tool because for creating the paths in the first place, you're most likely to be traversing a gridded cost surface than an existing network. Start with flow paths for water, then flow paths for goods and people. Then population growth and so on. Top it all off with the ability to force things (drastic increase in cost function in an area due to drought or a new xenophobic race or decrease in cost due to adding a new lake or river) and you're at the classic god game. That's why we're going this, after all. Or maybe it's just me...

[Hai-Etlik]

Network analysis and cost path analysis are well established parts of GIS. "Where should we build the power line?" (Cost Path Analysis) and "Where should we place the ambulance stations to optimize response time?" (Network Analysis) are classic GIS homework assignments.


It's also similar to my river network generator, except my cost function involves a random component and I start with multiple points.