Difficulty implementing BFS for traversal of graph

Question

I have an adjacency matrix adj which is defined below:

0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 
1 0 0 0 1 0 1 0 0 
0 0 0 1 0 1 0 0 0 
0 0 1 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 

I'm wracking my head around designing a BFS algorithm to traverse the graph given a starting position and an ending position.

My best attempt does yield a series of moves, but not the shortest.

boolean[] pass = new boolean[9]; //if a move has been done, don't redo it
int s = 0; //starting position
int e = 2; //ending position
int[][] matrix; //the adjacency matrix previous defined

public List<Integer> BFS(int[][] matrix, int s) {
    List<Integer> paths = new LinkedList();
    List<Integer> shortest = new LinkedList();
    pass[s] = true; //starting position has been indexed
    paths.add(0,s); //insert part of path to front of list
    while (paths.isEmpty() == false) {
        int element = paths.get(0); //peek at first element
        shortest.add(element); //add it to shortest path
        int node = paths.remove(0); //remove from path
        if (element == e) { //if we've reached the end
            return shortest; //hopefully found shortest path
        } else {
            for (int i = 0; i < 9; i++) {
                //if adjacent element hasn't been indexed
                if (pass[i] == false && matrix[node][i] == 1) {
                    pass[i] = true;
                    paths.add(0,i);
                }
            }
        }
    }
    return null;
}

Printing the returned List yields:

[0, 3, 6, 4, 5, 8, 2]

When the actual result should be:

[0, 3, 4, 5, 2]

It seems to me the path it's taking is something like:

[0, 3, 6, backtrack to 3, 4, 5, 8, backtrack to 5, 2]

What is wrong with my algorithm? How do I find the shortest path given a start and end point?

Here's an IDEone to illustrate.

Answer 1

You don't extract the shortest path correctly. You are adding every node you process to the shortest path.

If you want to use BFS to find the shortest path, you have to keep track of the shortest path to every intermediate node by storing "back edges" and only in the end you can put them together to find the shortest path.

For every node that you add to the queue, store the node that made you arrive at this node as "back edge":

if (pass[i] == false && matrix[node][i] == 1) {
    pass[i] = true;
    paths.add(0,i);

    // Add this:
    back[i] = node;
}

Then once your traversal is finished, you can use those references to find the full path by going those "back edges" backwards from the end node. It will lead you (backwards) to the start node on the shortest path:

int node = e;
while (node != s) {
    shortest.add(0, node);
    node = back[node];
}
shortest.add(0, s);

Update:

Thanks to your comment I just realized that there is an additional problem with your code. You are adding new nodes to the front of the list and process them from the front, too. So you have effectively a stack, not a queue. That makes your algorithm effectively a Depth-first search (DFS) instead of a Breadth-first search (BFS). The DFS will give you a correct path from s to e, but not necessarily the shortest one.

In order to treat your list paths (which should better be named queue, btw.) as queue instead of stack, you have to read and write from opposite ends, e.g. to add to the back (instead of the front) change your list adding line

paths.add(0, i);

to

paths.add(i);