1: // @author Frank M. Carrano, Timothy M. Henry
2: // @version 5.0
3: public int getShortestPath(T begin, T end, StackInterface<T> path)
4: {
5: resetVertices();
6: boolean done = false;
7: QueueInterface<VertexInterface<T>> vertexQueue = new LinkedQueue<>();
8: VertexInterface<T> originVertex = vertices.getValue(begin);
9: VertexInterface<T> endVertex = vertices.getValue(end);
10: originVertex.visit();
12: // Assertion: resetVertices() has executed setCost(0)
13: // and setPredecessor(null) for originVertex
15: vertexQueue.enqueue(originVertex);
16: while (!done && !vertexQueue.isEmpty())
17: {
18: VertexInterface<T> frontVertex = vertexQueue.dequeue();
19: Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborIterator();
20: while (!done && neighbors.hasNext())
21: {
22: VertexInterface<T> nextNeighbor = neighbors.next();
23: if (!nextNeighbor.isVisited())
24: {
25: nextNeighbor.visit();
26: nextNeighbor.setCost(1 + frontVertex.getCost());
27: nextNeighbor.setPredecessor(frontVertex);
28: vertexQueue.enqueue(nextNeighbor);
29: } // end if
31: if (nextNeighbor.equals(endVertex))
32: done = true;
33: } // end while
34: } // end while
36: // Traversal ends; construct shortest path
37: int pathLength = (int)endVertex.getCost();
38: path.push(endVertex.getLabel());
40: VertexInterface<T> vertex = endVertex;
41: while (vertex.hasPredecessor())
42: {
43: vertex = vertex.getPredecessor();
44: path.push(vertex.getLabel());
45: } // end while
47: return pathLength;
48: } // end getShortestPath