shortest path -- Dijkstra's algorithm help~~

[wildplace]

so..i found this on wikipedia
but i dont really get what dist, previous, alt mean in here..

1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity ;              // Unknown distance function from source to v
 4          previous[v] := undefined ;         // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                    // Distance from source to source
 7      Q := the set of all nodes in Graph ;
        // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                 // The main loop
 9          u := vertex in Q with smallest dist[] ;
10          if dist[u] = infinity:
11              break ;                        // all remaining vertices are inaccessible from source
12          end if ;
13          remove u from Q ;
14          for each neighbor v of u:         // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:             // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19              end if ;
20          end for ;
21      end while ;
22      return dist[] ;
23  end Dijkstra.

[mike_2000_17]

dist: This is an array that stores the estimate of the distance to the source (through the "optimal" path) for every vertex in the graph. This is a quantity you want to minimize all the time, i.e., this is a shortest-path algorithm.

previous: This is an array that stores, for each vertex v, which vertex would have been visited just before vertex v if you were following the shortest-path (found so far) from the source to vertex v. In other words, at the end, if you want to know optimal path, you just follow the "previous" vertex, then again and again until you reach the source.

In this implementation, I assume that "alt" is short for "alternative route". Basically, at each vertex that you look at (vertex u in this case), you check if any of the neighbors would be better off coming from u than what they current hold as their best distance estimate (dist[v]) and associated predecessor (previous[v]). "alt" is just the addition of the distance estimate of the current vertex u and the distance to travel to the neighbor vertex v. If that distance is smaller than v's current shortest-distance estimate, then u becomes the new predecessor of v and "alt" becomes its new distance estimate.

Initially, you set all distance estimates to infinity and all predecessors to "undefined" (or "none"). Then, by giving a distance of 0 to the source vertex (because it is obviously at zero distance to itself), you guarantee that this will be the first vertex to be looked at. "Q" in this algorithm is a priority-queue, meaning that it "orders" the vertices according to minimum distance estimate.

For example, at the first iteration, the source vertex will be looked at, then it will update the distance estimate of all its neighbors (because they were initially infinite). At this point, the source node is "closed" (considered as being explored) and the next iteration will continue with whichever updated neighbors had the lowest distance estimate. It will then update its neighbors, and so on, the shortest-path propagates until all accessible nodes have been visited (which you can tell by the fact that if your vertex with the lowest distance estimate has a distance of infinity, it means that there never were an explored vertex capable of reaching this one, and thus, the algorithm can stop there).