Returning only the vertices in the actual shortest

问题:

I know the title is a bit messy, but I don't know how to explain it better.

What I'm trying to do:

Using a graph found in a text file, find and print the shortest path (minimum amount of vertices) from vertex A to vertex B.

Note: using breadth-first search, not Dijkstra's.

What I've got:

A working algorithm that applies BFS on the graph, but no good way of actually printing out the shortest path.

I'm having a hard time distinguishing a vertex in the shortest path from one that is simply run through the algorithm, but not in the shortest path.

For example: Find the shortest path between 0 and 4. 0 connects to 1,2 and 3. 1 connects to 4. My path turns out to be [0,1,2,3,4] instead of [0,1,4].

I haven't been able to find any threads asking the same question, or any walk-through of BFS that includes this, so I'm not sure if I'm making this out to be way harder than it is?

Edit: code for those who may be interested (not sure at all if I'm avoiding circles?)

Edit 2: Changed the way I store my path to a Stack.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

Some explanation of variables and methods:

v = vertex of origin

w = target vertex

g = graph

vi = a normal iterator that iterates over the neighbours of v

Thanks for reading!

回答1:

You will have to have specific path field for each vertex. That way you can keep track of the paths you've chosen, hence the short path found. I will use an String array, just like you used the Boolean array for storing visited vertices.

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;
}

回答2:

Another compact (space-wise) solution that us assistants have suggested and doesn't use O(n^2) storage space is to have each node store only which node it came from. This can be done by changing the visited-list to an integer array (int[] visited).

step 1: initialize visited list, so that every element is '-1', or "unvisited"

step 2: mark the first node as visited by itself visited[v] = v;

Do a BFS (like you do, with the following modifications:)

when moving from v -> v_next:

if(visited[v_next] == -1)
{
  visited[v_next] = v;
  q.put(v_next);
}
// else skip it, it's already been visited

This way, if w is reachable, visited[w] will store which node it came from, from that node, you can backtrack all the way back to v and finally print them in the opposite order. (This is done either using a stack or a recursive print method.)

Hope that makes sense. :)

回答3:

When you store a vertex in the BFS queue, you also need to store a copy of the path through which it has been reached, so that it will be available once that vertex is dequeued. As it is now, your code does not keep any kind of path information on the queued vertices - it only keeps a list of the nodes it visits.

You could, for example, use a separate queue that will be processed in parallel, in which you will store the current path, and then restore it once you dequeue the next vertex to search.

回答4:

You need to push your current node onto a stack, and only print the whole stack out once you reach the destination.