Java Reference
In-Depth Information
Note:
In an unweighted graph, the shortest path between two given vertices has the shortest
length—that is, it has the fewest edges. The algorithm to find this path is based on a breadth-
first traversal. If several paths have the same shortest length, the algorithm will find only one
of them
.
28.19
The algorithm.
The following algorithm finds the shortest path in an unweighted graph between
the vertices
originVertex
and
endVertex
. Like the breath-first traversal in Segment 28.12, the
algorithm uses a queue to hold the vertices as they are visited. It then uses the given, initially empty
stack
path
to construct the shortest path.
Algorithm
getShortestPath(originVertex, endVertex, path)
done =
false
vertexQueue =
a new queue to hold vertices as they are visited
Mark
originVertex
as visited
vertexQueue.enqueue(originVertex)
while
(!done && !vertexQueue.isEmpty())
{
frontVertex = vertexQueue.dequeue()
while
(!done && frontVertex
has a neighbor
)
{
nextNeighbor =
next neighbor of
frontVertex
if
(nextNeighbor
is not visited
)
{
Mark
nextNeighbor
as visited
Set the length of the path to
nextNeighbor
to 1 + length of path to
frontVertex
Set the predecessor of
nextNeighbor
to
frontVertex
vertexQueue.enqueue(nextNeighbor)
}
if
(nextNeighbor
equals
endVertex)
done =
true
}
}
//
traversal ends - construct shortest path
pathLength =
length of path to
endVertex
path.push(endVertex)
vertex = endVertex
while
(vertex
has a predecessor
)
{
vertex =
predecessor of
vertex
path.push(vertex)
}
return
pathLength
When the algorithm ends, the stack
path
contains the vertices along the shortest path, with the
origin at the top of the stack. The value returned is the length of this shortest path.
28.20
Tracing the algorithm.
Figure 28-17 traces the steps that the algorithm takes to produce the
path information shown in Figure 28-16a for the unweighted graph in Figure 28-15a. After
adding the origin—vertex
A
—to the queue, we visit the origin's three neighbors—
B
,
D
, and
E
—and enqueue them.
