note
JavaFan
That sounds like you're computing the smallest spanning tree. Which is *not* what Dijkstra's algorithm is doing. Given a smallest spanning tree, one can compute an approximation of the shortest hamiltonian path, which I think is at most a factor 2 off.
<p>
Dijkstra's algorithm in a nutshell:
<ol>
<li>Mark all nodes in the graph unvisited with distance infinite.
<li>Mark the start node unvisited with distance 0.
<li>Off all the unvisited nodes, pick the one (or one of) with smallest distance. Call this node X.
<li>For all unvisited neighbours of X, calculate their distance to the start node (which is the distance X has, plus the length of the edge between X and its neighbour). If said distance is less than the current distance stored at the neighbour, update the distance.
<li>Mark X as visited. If X is the destination node, you're done.
<li>Goto 3. (Hah! A Goto in Dijkstra's algorithm. The irony...)
</ol>
969487
969569