>>8907
I see what you mean, until a node is visited it's distance isn't finalized. It must be the nodes with more than one edge drawn had a node tentatively set as the shortest neighbor back to start in step 4, but was reassigned in a later iteration.
1 Mark all nodes unvisited and give them a distance of +INF.
2 Pick a root node to start, assigning it a distance of zero
3 Get a list of all the adjacent unvisited nodes of the current node
4 Compute the distance to each of these nodes as current node's distance + edge length. For a square grid like this diagonals are longer than cardinals to avoid zigzagging all over the place. If this distance is smaller than it's tentative current distance, replace it with the newly calculated distance.
5 Mark the current node as visited.
6 Find an unvisited node with the smallest travel distance less than +INF as the current node. If none exists the destination is unreachable, if this node is the destination return the path by recursively retrieving visited neighboring nodes with the lowest distance, otherwise set this as the current node and go to step 3.
If untraversable nodes exist they would be marked as visited at the start so they are never considered, or visited/unvisited status could be represented by presence in visited and unvisited sets and they would be placed in neither.
The parent node isn't necessary. Setting all these parent references would always be more computationally intensive than backtracking by evaluating neighbors on the way back unless the destination was adjacent to the start, the path nodes and their adjacent nodes are small compared to the number of nodes evaluated. A* might use parent node references since the number of nodes evaluated grows along a much narrower front generally toward the goal. I'll try implementing an animated demo like the pic was from tomorrow.