Satya's blog - Dijkstra's algorithm

In a game I play, there are maps. Movement costs differently per type of tile. Moving uses up action points. Players make maps of the sectors. I write an auto-mapper Firefox Extension. I now have a lot of map data in a database. I make pretty maps in HTML and as images using Imagemagick (in perl). Much goodness ensues.

"Hmm," I think, "why don't I write something that will calculate the path across the sectors for a of minimum action points, i.e. shortest path. Ah, Dijkstra's algorithm gives me shortest paths. After all, the relevant map data can be expressed as a graph." I used the data in the Dijkstra's algorithm Wikipedia article.

Well, Dijkstra's algorithm gave me distances from the start point. I struggled a bit, and eventually this site (PDF) showed me that I also need to track the "previous" vertex. Once I did that, I got the shortest, cheapest, route. Some more struggling with Javascript and I can generate shortest routes as much as I want, and their cost is shown to me.

That's right, I have implemented Dijkstra's algorithm in Javascript. I will post it soon.