Java Reference
In-Depth Information
//Computeshortestpathdistancesfroms,storetheminD
staticvoidDijkstra(GraphG,ints,int[]D){
for(inti=0;i<G.n();i++) //Initialize
D[i]=Integer.MAXVALUE;
D[s]=0;
for(inti=0;i<G.n();i++){//Processthevertices
intv=minVertex(G,D); //Findnext-closestvertex
G.setMark(v,VISITED);
if(D[v]==Integer.MAXVALUE)return;//Unreachable
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(D[w]>(D[v]+G.weight(v,w)))
D[w]=D[v]+G.weight(v,w);
}
}
Figure11.17
An implementation for Dijkstra's algorithm.
tialized to the value
INFINITE
. Vertices are processed in order of distance from
S. Whenever a vertex V is processed, D(X) is updated for every neighbor X of V.
Figure 11.17 shows an implementation for Dijkstra's algorithm. At the end, array D
will contain the shortest distance values.
There are two reasonable solutions to the key issue of finding the unvisited
vertex with minimum distance value during each pass through the main
for
loop.
The first method is simply to scan through the list of jVj vertices searching for the
minimum value, as follows:
staticintminVertex(GraphG,int[]D){
intv=0;//Initializevtoanyunvisitedvertex;
for(inti=0;i<G.n();i++)
if(G.getMark(i)==UNVISITED){v=i;break;}
for(inti=0;i<G.n();i++)//Nowfindsmallestvalue
if((G.getMark(i)==UNVISITED)&&(D[i]<D[v]))
v=i;
returnv;
}
Because this scan is done jVj times, and because each edge requires a constant-
time update to D, the total cost for this approach is (jVj
2
+ jEj) = (jVj
2
),
because jEj is in O(jVj
2
).
The second method is to store unprocessed vertices in a min-heap ordered by
distance values. The next-closest vertex can be found in the heap in (logjVj)
time. Every time we modify D(X), we could reorder X in the heap by deleting
and reinserting it. This is an example of a priority queue with priority update, as
described in Section 5.5. To implement true priority updating, we would need to
store with each vertex its array index within the heap. A simpler approach is to
add the new (smaller) distance value for a given vertex as a new record in the heap.
The smallest value for a given vertex currently in the heap will be found first, and
greater distance values found later will be ignored because the vertex will already
be marked as
VISITED
. The only disadvantage to repeatedly inserting distance
