仅返回实际最短路径中的顶点

每个顶点必须具有特定的路径字段。这样，您可以跟踪所选的路径，因此可以找到较短的路径。我将使用String数组，就像您使用Boolean数组来存储访问的顶点一样。

public String findPath(int v, int w) {    Queue<Integer> q = new linkedList<Integer>();    boolean[] visited = new boolean[g.numVertices()];    String[] pathTo = new String[g.numVertices()];    q.add(v);    pathTo[v] = v+" ";    while(q.peek() != null) {        if(runBFS(q.poll(),w,visited,q,pathTo))        break;    }    return pathTo[w];}private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {    if(visited[v]) {    }    else if(v == w)        return true;     }    else {        visited[v] = true;        VertexIterator vi = g.adjacentVertices(v);        while(vi.hasNext()) { int nextVertex = vi.next(); pathTo[nextVertex] = pathTo[v] + nextVertex + " "; q.add(nextVertex);        }    }    return false;}