How to perform Dijskras Algorithm by Ethr
If like me you're not too happy with Wikipedias explaination of how to do his algorithm here's a simple direct way of doing it.
You'll need some datastructure for storing graph information.
* Create an array for storing distances in. This will be the shortest distance from the start node to any other node.
* Select your start node
* Set its distance in the array to 0
* Create a set of all unvisited nodes
* While this set is unempty...
* Get the selected node and exam its neighbours. If the distance to the selected node + the distance to the neighbour is less than whats stored in the array, update the array
* Remove the selected node from the unvisted list
* Select a new node. This is the one with the shortest culumilative distance (from the start node) that hasn't been visited (i..e not in the unvisited node set)
* Return the array
And there you go a simple way of doing dijskras. I usually like to think of unconnected nodes as having infinite distance so this works quite well.
You'll need some datastructure for storing graph information.
* Create an array for storing distances in. This will be the shortest distance from the start node to any other node.
* Select your start node
* Set its distance in the array to 0
* Create a set of all unvisited nodes
* While this set is unempty...
* Get the selected node and exam its neighbours. If the distance to the selected node + the distance to the neighbour is less than whats stored in the array, update the array
* Remove the selected node from the unvisted list
* Select a new node. This is the one with the shortest culumilative distance (from the start node) that hasn't been visited (i..e not in the unvisited node set)
* Return the array
And there you go a simple way of doing dijskras. I usually like to think of unconnected nodes as having infinite distance so this works quite well.