Java Reference
In-Depth Information
public
int
getShortestPath(T begin, T end, StackInterface<T> path)
{
resetVertices();
boolean
done =
false
;
QueueInterface<VertexInterface<T>> vertexQueue =
new
LinkedQueue<VertexInterface<T>>();
VertexInterface<T> originVertex = vertices.getValue(begin);
VertexInterface<T> endVertex = vertices.getValue(end);
originVertex.visit();
// Assertion: resetVertices() has executed setCost(0)
// and setPredecessor(null) for originVertex
vertexQueue.enqueue(originVertex);
while
(!done && !vertexQueue.isEmpty())
{
VertexInterface<T> frontVertex = vertexQueue.dequeue();
Iterator<VertexInterface<T>> neighbors =
frontVertex.getNeighborIterator();
while
(!done && neighbors.hasNext())
{
VertexInterface<T> nextNeighbor = neighbors.next();
if
(!nextNeighbor.isVisited())
{
nextNeighbor.visit();
nextNeighbor.setCost(1 + frontVertex.getCost());
nextNeighbor.setPredecessor(frontVertex);
vertexQueue.enqueue(nextNeighbor);
}
// end if
if
(nextNeighbor.equals(endVertex))
done =
true
;
}
// end while
}
// end while
// traversal ends; construct shortest path
int
pathLength = (
int
)endVertex.getCost();
path.push(endVertex.getLabel());
VertexInterface<T> vertex = endVertex;
while
(vertex.hasPredecessor())
{
vertex = vertex.getPredecessor();
path.push(vertex.getLabel());
}
// end while
return
pathLength;
}
// end getShortestPath
The implementation of the method
getCheapestPath
for a weighted graph is left as an exercise.
Question 6
Write Java statements that display the vertices in the shortest path from
vertex
A
to vertex
C
for the graph that you created in Question 4. Also, display the length
of this path.
