Dijkstra’s shortest path algorithm

问题:

The following is algorithm summary given to us by our professor.

What is the parent of a node in a graph as referred to in step 3? I'm a little confused as I though that the nodes only had neighbors and doesn't have a parent?

My second question is about step 3, "pick up the index’th record in stack." Since a stack only allows you to view the top, I'm not sure what it means by picking up the index'th record?

Dijkstra’s shortest path:

Step 0: if s == d, stop.
Step 1: current node c= s, c.length = 0, stack.push (c, its length, and parent). 
        If u is the source s then no need for parent.
Step 2: min = 0, hop = infinite, index = 1
Step 3: pick up the index’th record in stack, say node u, its length u.length, 
        and its parent w.
Step 4: find a neighbor of u in the table of neighbors, say v, such that v is 
        not found in any item in stack and <u,v> +u.length< hop. 
Step 5: if such a neighbor is found, hop=min=u.length + <u,v> and record_node = v
Step 6: go to step 4 until all the neighbors of u have been tried (all can be 
        found in stack).
Step 7: index ++, go to step 3 until all the nodes have been tried (found in 
        stack).
Step 8: c = record_node, c.length = min, stack_push(c, c.length, u). If c == d 
        stop the entire process and goes to step 9 for data collection, 
        otherwise go to step 2.
Step 9: (t, d.length, and t.parent) = (d, d.length, and d.parent) in stack, 
        keep searching on (t.parent, t.parent.length, t.parent.parent), 
        until t.parent = s.

回答1:

In a graph, nodes only have neighbors, but while running Dijkstra's algorithm you build a "tree" describing the shortest path from the starting node to all the nodes in the original graph.

at the beginning of the algorithm run, all the nodes have their predecessor node set to null, and on each iteration a parent is set to the node leading to the shortest path.

Have a look at this Visualization of Dijkstra's Algorithm and notice that the result of the algorithm is in fact a sub-tree of the graph.

Hope that answers your question :)

回答2:

Maybe this applet can help you.

I strongly recommend simply looking around on the internet for better explanations of the algorithm. It's the most used algorithm for navigation software nowadays - every major navigation company uses it (and probably the small ones as well). It's also used as a pathfinding algorithm in games.

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/dijkstra.html

回答3:

Parent refers to the node on the path one step before the nodes you are currently examining. In other words: A path is a directed graph where each node has an order of 2 (that is, it is connected by edges to two other nodes) except for the first and the last node. The parent of a node is the predecessor of that node.

About the stack: Probably this is not a real stack but just a structure where you push nodes onto; you can then index all nodes on this structure, not just the one on the top. But I agree, stack is not a good choice of words.