Java Reference
In-Depth Information
pathCost =
cost of path to
endVertex
path.push(endVertex)
vertex = endVertex
while
(vertex
has a predecessor
)
{
vertex =
predecessor of
vertex
path.push(vertex)
}
return
pathCost
The origin of the cheapest path will be at the top of the stack
path
. At the bottom of the stack is the
destination vertex. The cost of the path is returned by the algorithm.
This algorithm is based on Dijkstra's algorithm, which finds the shortest paths from an origin
to all other vertices.
Question 10
Continue the trace begun in Figure 28-19 to find the shortest (cheapest) path
from vertex
A
to vertex
C
.
Question 11
Why do we place instances of
EntryPQ
into the priority queue, instead of
placing vertices?
28.25
The ADT graph is a bit different from other ADTs in that, once you create it, you do not add, remove,
or retrieve components. Instead, you use a graph to answer questions based on the relationships
among its vertices.
We will divide the graph operations into two Java interfaces. You use the operations in the first
interface to create the graph and to obtain basic information such as the number of vertices. The
second interface specifies operations such as the traversals and path searches that we discussed ear-
lier in this chapter. For convenience, we define a third interface,
GraphInterface
, that combines
the first two interfaces.
To make these interfaces as general as possible, we have them specify graphs that are either
directed or undirected, and weighted or unweighted. The first interface appears in Listing 28-1. The
generic type
T
represents the data type of the objects that label the graph's vertices.
LISTING 28-1
An interface of basic graph operations
package
GraphPackage;
/** An interface of methods providing basic operations for directed
and undirected graphs that are either weighted or unweighted. */
public interface
BasicGraphInterface<T>
{
/** Adds a given vertex to the graph.
@param vertexLabel an object that labels the new vertex and is
distinct from the labels of current vertices
@return true if the vertex is added, or false if not */
public boolean
addVertex(T vertexLabel);
