Java Reference
In-Depth Information
/
**
Dijkstra'sshortest-paths:priorityqueueversion
*
/
staticvoidDijkstra(GraphG,ints,int[]D){
intv; //Thecurrentvertex
DijkElem[]E=newDijkElem[G.e()];//Heapforedges
E[0]=newDijkElem(s,0); //Initialvertex
MinHeap<DijkElem>H=newMinHeap<DijkElem>(E,1,G.e());
for(inti=0;i<G.n();i++) //Initializedistance
D[i]=Integer.MAXVALUE;
D[s]=0;
for(inti=0;i<G.n();i++){ //Foreachvertex
do{v=(H.removemin()).vertex();} //Getposition
while(G.getMark(v)==VISITED);
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))){//UpdateD
D[w]=D[v]+G.weight(v,w);
H.insert(newDijkElem(w,D[w]));
}
}
}
Figure11.18
An implementation for Dijkstra's algorithm using a priority queue.
values is that it will raise the number of elements in the heap from (jVj) to (jEj)
in the worst case. The time complexity is ((jVj + jEj) logjEj), because for each
edge we must reorder the heap. Because the objects stored on the heap need to
know both their vertex number and their distance, we create a simple class for the
purpose called
DijkElem
, as follows.
DijkElem
is quite similar to the
Edge
class used by the adjacency list representation.
classDijkElemimplementsComparable<DijkElem>{
privateintvertex;
privateintweight;
publicDijkElem(intinv,intinw)
{vertex=inv;weight=inw;}
publicDijkElem(){vertex=0;weight=0;}
publicintkey(){returnweight;}
publicintvertex(){returnvertex;}
publicintcompareTo(DijkElemthat){
if(weight<that.key())return-1;
elseif(weight==that.key())return0;
elsereturn1;
}
}
Figure 11.18 shows an implementation for Dijkstra's algorithm using the prior-
ity queue.
Using
MinVertex
to scan the vertex list for the minimum value is more ef-
ficient when the graph is dense, that is, when jEj approaches jVj
2
. Using a prior-
