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

We provide a simple test program that reads a graph from an input
file, prompts for a start vertex and a destination vertex, and then runs one
of the shortest-path algorithms. Figure 14.14 illustrates that to construct
the Graph object, we repeatedly read one line of input, assign the line to a
StringTokenizer object, parse that line, and call addEdge . Using a
StringTokenizer allows us to verify that every line has the three pieces cor-
responding to an edge.
Once the graph has been read, we repeatedly call processRequest , shown
in Figure 14.15. This version prompts for a starting and ending vertex and
then calls one of the shortest-path algorithms. This algorithm throws a
GraphException if, for instance, it is asked for a path between vertices that are
not in the graph. Thus processRequest catches any GraphException that might
be generated and prints an appropriate error message.

The Graph class is
easy to use.

unweighted shortest-path
problem

14.2

Recall that the unweighted path length measures the number of edges. In this
section we consider the problem of finding the shortest unweighted path
length between specified vertices.

The unweighted
path length mea-
sures the number
of edges on a path.

unweighted single-source, shortest-path problem
Find the shortest path (measured by number of edges) from a designated vertex S
to every vertex.

The unweighted shortest-path problem is a special case of the weighted
shortest-path problem (in which all weights are 1). Hence it should have a
more efficient solution than the weighted shortest-path problem. That
turns out to be true, although the algorithms for all the path problems are
similar.

All variations of the
shortest-path prob-
lem have similar
solutions.

14.2.1 theory

To solve the unweighted shortest-path problem, we use the graph previously shown
in Figure 14.1, with as the starting vertex S . For now, we are concerned with
finding the length of all shortest paths. Later, we maintain the corresponding paths.
We can see immediately that the shortest path from S to is a path of
length 0. This information yields the graph shown in Figure 14.16. Now we
can start looking for all vertices that are distance 1 from S . We can find them
by looking at the vertices adjacent to S . If we do so, we see that

V 2

V 2

V 0 and V 5 are

one edge away from S , as shown in Figure 14.17.