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.
Dijkstra's algorithm in a nutshell:
- Mark all nodes in the graph unvisited with distance infinite.
- Mark the start node unvisited with distance 0.
- Off all the unvisited nodes, pick the one (or one of) with smallest distance. Call this node X.
- 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.
- Mark X as visited. If X is the destination node, you're done.
- Goto 3. (Hah! A Goto in Dijkstra's algorithm. The irony...)
