Graphs and paths - Data Structures and Problem Solving Using Java - page 557

repeat this process N times, where N is the number of unprocessed vertices
left in the graph. Among , there must be two identical vertices
(because there are N vertices but N + 1 A i 's). Tracing backward between those
identical A i and A j exhibits a cycle.

A 0 A 1 , , … , A N

We can implement the algorithm in linear time by placing all unprocessed
indegree 0 vertices on a queue. Initially, all vertices of indegree 0 are placed
on the queue. To find the next vertex in the topological order, we merely get
and remove the front item from the queue. When a vertex has its indegree
lowered to 0, it is placed on the queue. If the queue empties before all the ver-
tices have been topologically sorted, the graph has a cycle. The running time
is clearly linear, by the same reasoning used in the unweighted shortest-path
algorithm.

The running time is
linear if a queue is
used.

14.5.2 theory of the acyclic
shortest-path algorithm

An important application of topological sorting is its use in solving the shortest-
path problem for acyclic graphs. The idea is to have the eyeball visit vertices in
topological order.
This idea works because, when the eyeball visits vertex v , we are guaran-
teed that D v can no longer be lowered; by the topological ordering rule, it has
no incoming edges emanating from unvisited nodes. Figure 14.31 shows the
stages of the shortest-path algorithm, using topological ordering to guide the
vertex visitations. Note that the sequence of vertices visited is not the same as
in Dijkstra's algorithm. Also note that vertices visited by the eyeball prior to
its reaching the starting vertex are unreachable from the starting vertex and
have no influence on the distances of any vertex.

In an acyclic graph,
the eyeball merely
visits vertices in
topological order.

We do not need a priority queue. Instead, we need only to incorporate the
topological sort into the shortest-path computation. Thus we find that the
algorithm runs in linear time and works even with negative edge weights.

The result is a linear-
time algorithm even
with negative edge
weights.

14.5.3 java implementation

The implementation of the shortest-path algorithm for acyclic graphs is
shown in Figure 14.32. We use a queue to perform the topological sort and
maintain the indegree information in the scratch data member. Lines 15-18
compute the indegrees, and at lines 21-23 we place any indegree 0 vertices on
the queue.
We then repeatedly remove a vertex from the queue at line 28. Note that,
if the queue is empty, the for loop is terminated by the test at line 26. If the
loop terminates because of a cycle, this fact is reported at line 50. Otherwise,
the loop at line 30 steps through the adjacency list and a value of w is obtained

The implementa-
tion combines a
topological sort cal-
culation and a
shortest-path cal-
culation. The inde-
gree information
is stored in the
scratch data
member.