Java Reference
In-Depth Information
path problems in acyclic graphs
14.5
Recall that a directed acyclic graph has no cycles. This important class of
graphs simplifies the solution to the shortest-path problem. For instance, we
do not have to worry about negative-cost cycles because there are no cycles.
Thus we consider the following problem.
weighted single-source, shortest-path problem for acyclic graphs
Find the shortest path (measured by total cost) from a designated vertex S to
every vertex in an acyclic graph. Edge costs are unrestricted.
14.5.1 topological sorting
Before considering the shortest-path problem, let us examine a related
problem: a topological sort. A topological sort orders vertices in a directed
acyclic graph such that if there is a path from u to v , then v appears after u
in the ordering. For instance, a graph is typically used to represent the pre-
requisite requirement for courses at universities. An edge ( v , w ) indicates
that course v must be completed before course w may be attempted. A
topological order of the courses is any sequence that does not violate the
prerequisite requirements.
Clearly, a topological sort is not possible if a graph has a cycle because,
for two vertices v and w on the cycle, there is a path from v to w and w to v .
Thus any ordering of v and w would contradict one of the two paths. A graph
may have several topological orders, and in most cases, any legal ordering
will do.
In a simple algorithm for performing a topological sort we first find any
vertex v that has no incoming edges. Then we print the vertex and logically
remove it, along with its edges, from the graph. Finally, we apply the same
strategy to the rest of the graph. More formally, we say that the indegree of a
vertex v is the number of incoming edges ( u , v ).
A topological sort
orders vertices in a
directed acyclic
graph such that if
there is a path from u
to v , then v appears
after u in the order-
ing. A graph that has
a cycle cannot have
a topological order.
We compute the indegrees of all vertices in the graph. In practice, logically
remove means that we lower the count of incoming edges for each vertex adjacent
to v . Figure 14.30 shows the algorithm applied to an acyclic graph. The indegree
is computed for each vertex. Vertex V 2 has indegree 0, so it is first in the topologi-
cal order. If there were several vertices of indegree 0, we could choose any one of
them. When V 2 and its edges are removed from the graph, the indegrees of V 0 , V 3 ,
and V 5 are all decremented by 1. Now V 0 has indegree 0, so it is next in the topo-
logical order, and V 1 and V 3 have their indegrees lowered. The algorithm contin-
ues, and the remaining vertices are examined in the order V 1 , V 3 , V 4 , V 6 , and V 5 .
To reiterate, we do not physically delete edges from the graph; removing edges
just makes it easier to see how the indegree count is lowered.
The indegree of a
vertex is the num-
ber of incoming
edges. A topologi-
cal sort can be per-
formed in linear
time by repeatedly
and logically
removing vertices
that have no incom-
ing edges.
 
 
Search WWH ::




Custom Search