Java Reference
In-Depth Information
staticvoidtopsort(GraphG){//Topologicalsort:Queue
Queue<Integer>Q=newAQueue<Integer>(G.n());
int[]Count=newint[G.n()];
intv;
for(v=0;v<G.n();v++)Count[v]=0;//Initialize
for(v=0;v<G.n();v++) //Processeveryedge
for(intw=G.first(v);w<G.n();w=G.next(v,w))
Count[w]++; //Addtov2'sprereqcount
for(v=0;v<G.n();v++) //InitializeQueue
if(Count[v]==0) //Vhasnoprerequisites
Q.enqueue(v);
while(Q.length()>0){ //Processthevertices
v=Q.dequeue().intValue();
printout(v); //PreVisitforVertexV
for(intw=G.first(v);w<G.n();w=G.next(v,w)){
Count[w]--; //Onelessprerequisite
if(Count[w]==0) //Thisvertexisnowfree
Q.enqueue(w);
}
}
}
Figure11.15
A queue-based topological sort algorithm.
real numbers. These numbers represent the distance (or other cost metric, such as
travel time) between two vertices. These labels may be called weights, costs, or
distances, depending on the application. Given such a graph, a typical problem
is to find the total length of the shortest path between two specified vertices. This
is not a trivial problem, because the shortest path may not be along the edge (if
any) connecting two vertices, but rather may be along a path involving one or more
intermediate vertices. For example, in Figure 11.16, the cost of the path from A to
B to D is 15. The cost of the edge directly from A to D is 20. The cost of the path
from A to C to B to D is 10. Thus, the shortest path from A to D is 10 (not along
the edge connecting A to D). We use the notation d(A, D) = 10 to indicate that the
shortest distance from A to D is 10. In Figure 11.16, there is no path from E to B, so
we set d(E, B) = 1. We define w(A, D) = 20 to be the weight of edge (A, D), that
is, the weight of the direct connection from A to D. Because there is no edge from
E to B, w(E, B) = 1. Note that w(D, A) = 1 because the graph of Figure 11.16
is directed. We assume that all weights are positive.
11.4.1
Single-Source Shortest Paths
This section presents an algorithm to solve the single-source shortest-paths prob-
lem. Given Vertex S in Graph G, find a shortest path from S to every other vertex
in G. We might want only the shortest path between two vertices, S and T. How-
ever in the worst case, while finding the shortest path from S to T, we might find
the shortest paths from S to every other vertex as well. So there is no better alg-
