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

adj : This list of adjacent vertices is established when the graph is read.
None of the shortest-path algorithms changes the list. In the abstract,
Figure 14.4 shows that it is a list of Edge objects that each contain an
internal vertex number and edge cost. In reality, Figure 14.5 shows
that each Edge object contains a reference to a Vertex and an edge cost
and that the list is actually stored by using an ArrayList or LinkedList .

n

dist : The length of the shortest path (either weighted or unweighted,
depending on the algorithm) from the starting vertex to this vertex as
computed by the shortest-path algorithm.

n

prev : The previous vertex on the shortest path to this vertex, which
in the abstract (Figure 14.4) is an int but in reality (the code and
Figure 14.5) is a reference to a Vertex .

n

To be more specific, in Figures 14.4 and 14.5 the unshaded items are not
altered by any of the shortest-path calculations. They represent the input
graph and do not change unless the graph itself changes (perhaps by addition
or deletion of edges at some later point). The shaded items are computed by
the shortest-path algorithms. Prior to the calculation we can assume that they
are uninitialized. 1

The shortest-path algorithms are all single-source algorithms, which
begin at some starting point and compute the shortest paths from it to all ver-
tices. In this example the starting point is A , and by consulting the map we can
find its Vertex object. Note that the shortest-path algorithm declares that the
shortest path to A is 0 .
The prev data member allows us to print out the shortest path, not just its length.
For instance, by consulting the Vertex object for C , we see that the shortest path from
the starting vertex to C has a total cost of 76. Obviously, the last vertex on this path is
C . The vertex before C on this path is D , before D is E , before E is B , and before B is A —
the starting vertex. Thus, by tracing back through the prev data member, we can
construct the shortest path. Although this trace gives the path in reverse order, unre-
versing it is a simple matter. In the remainder of this section we describe how the
unshaded parts of all the Vertex objects are constructed and give the method that
prints out a shortest path, assuming that the dist and prev data members have been
computed. We discuss individually the algorithms used to fill in the shortest path.
Figure 14.6 shows the Edge class that represents the basic item placed
in the adjacency list. The Edge consists of a reference to a Vertex and the
edge cost. The Vertex class is shown in Figure 14.7. An additional member
named scratch is provided and has different uses in the various algorithms.

The shortest-path
algorithms are sin-
gle source algo-
rithms that compute
the shortest paths
from some starting
point to all vertices.

The prev member
can be used to
extract the actual
path.

The item in an adja-
cency list is a refer-
ence to the Vertex
object of the adja-
cent vertex and the
edge cost.

1. The computed information (shaded) could be separated into a separate class, with Vertex
maintaining a reference to it, making the code more reusable but more complex.