Returning only the vertices in the actual shortest path

Question

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!

How is your graph represented in your code? How do you avoid circles? There are quite a few questions like this that would be best answered by you posting some of your code... — thkala, Mar 28 '11 at 18:45
I've added some code. If there is any missing info about the graph let me know. — bjrnt, Mar 28 '11 at 18:57
I think I am missing a few things here. For one, aren't `String` objects in Java immutable? What good does changing `path` in `runBFS` do? — thkala, Mar 28 '11 at 19:36
You're absolutely right, my bad. I have however changed it from String to Stack now and will make the appropriate changes in the code. — bjrnt, Mar 28 '11 at 19:46

jCoder · Accepted Answer · 2011-03-28T20:10:01.410

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

Exactly what I needed, thanks a lot! Great solution, I think my problem was that I was only interested in the path from X to Y, and nothing else. — bjrnt, Mar 28 '11 at 20:08

score 6 · Answer 2 · answered Mar 31 '11 at 15:20

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. :)

score 3 · Answer 3 · answered Mar 28 '11 at 20:09

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.

This helpful explanation was very helpful. See [here](https://stackoverflow.com/a/48260217/3992939) my implementation — c0der, Jan 15 '18 at 09:49

score 1 · Answer 4 · answered Mar 28 '11 at 18:45

1

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

answered Mar 28 '11 at 18:45

regularfry

3,248
2
21
27

This returned the exact same result as my previous method, could you please be a little bit more elaborate? – bjrnt Mar 28 '11 at 19:11
Were you popping it back off when you backed up? – regularfry Apr 04 '11 at 08:31

Returning only the vertices in the actual shortest path

4 Answers4

Linked