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