Think of what would happen if you "spill water" in the source vertex s. Water would start spreading simultaneously along the edges emanating from S. Let the amount of time it takes a water drop to cross an edge be proportional to its weight (that is - interpret the edge weights as "distances" and assume drops move at a constant speed). Then, for each vertex, the information you would like to have is "when did water first arrive here and where did it come from".
This is what Dijkstra's algorithm simulates. Think of the (continuous) water flow processs I described and consider the events of type "water gets to a certain vertex for the first time". These events can be ordered by their time of occurrence. There are |V| such events (assuming the graph is connected). Each iteration of Dijkstra's algorithm celebrates one such event. Ordering the vertices by the number of the iteration where they where extracted from Q and added to S is the same as ordering them by the "time when water first arrived".
> i=Infinity // Infinity is just an object, so we can copy it to a variable called "i" for easy typing
« Older Hooray a new friend! | Our Fair City Newer »
This thread has been archived and is closed to new comments