Debate

[darwinrlo]

False dilemma

[darwinrlo]

We are given a directed graph and a vertex from the graph. We are to compute for each vertex other than the vertex we were given the shortest distance to it from the given vertex along any path through the graph. We will call the vertex we were given the origin vertex.

To start off, assign a key to each vertex. For the origin vertex, the key is assigned to be 0. All other vertices are assigned a key of INF (for positive infinity).

Next, create an instance of a set that we will use to store vertices for which the key is equal to the shortest distance along any path to it from the origin vertex. We'll call this set the result set.

Then insert all vertices into a heap. A heap element consists of a key and a value. In this case, the key is the key of the vertex, assigned previously. And the value is the vertex itself.

Now everything is set up and we do the following until the heap is empty:

• Extract the minimum element from the heap. On the first loop iteration, this minimum element is simply the origin vertex.
  • Add the vertex corresponding to the heap element to the result set.
  • Update the keys for the newly finalized vertex's neighboring vertices that are still in the heap. These neighboring vertices are now in the frontier of the result set; that is, there are edges, called crossing edges, that originate from inside the result set and end at these vertices. Remove each such vertex from the heap, set its key to the shortest distance from the origin vertex to it through a crossing edge, and re-insert it into the heap.

Once the heap has been depleted, each vertex's key is now equal to the shortest distance along any path to it from the origin vertex.