Breadth First Search fails to find destination that does exist

Question

So I have been working on a Breadth First Search to get a path given a starting and ending node. However in some cases it seems to fail and not get the path, which I know is possible since a Depth First Search and visual inspection shows that it should exist.

I have an Adjacency Matrix:

     1       2       3       4       5       6       7       8

 1   0       20      25      20      0       0       0       0
 2   20      0       5       0       30      0       0       0
 3   25      5       0       13      8       21      0       0
 4   20      0       13      0       0       17      0       0
 5   0       30      8       0       0       33      0       0
 6   0       0       21      17      33      0       0       0
 7   0       0       0       0       0       0       0       10
 8   0       0       0       0       0       0       10      0

Which has a graph as follows:

This is my function:

void Network::BFS(int src, int dest, vector<bool>& visited, vector<int>& path) {
    // The Queue is the core for the BFS.
    queue<int> Queue;
    // Mark current node as visited.
    visited[src] = true;
    Queue.push(src);
    // While queue is not empty.
    while (!Queue.empty()) {
        // Add node to path.
        // Check if we have found the destination yet or not, if we have we do one last push to path and we're done!
        if (Queue.front() == dest) {
            return;
        }
        int top = Queue.front();
        path.push_back(Queue.front());
        // Pop off front.
        Queue.pop();
        // Iterate and process all none visited nodes.
        for (int node = 0; node < amountOfNodes; node++) {
            // Check if it is not visited already.
            if (visited[node] == false && (adjMatrix[node * amountOfNodes + src] != 0)) {
                Queue.push(node); // Add to end.
                visited[node] = true;
            }
        }
    }
}

Sample input and output:

(6, 3) -> Path is: 6

(1, 5) -> Path is: 1 2 3 4

As you can see, it does not compute the path properly at all. Where is my algorithm going wrong here, and how do I fix it?

Answer 1

BFS involves visiting adjacent nodes in a FIFO fashion. Once you reach a node, you put into the queue all its neighbours, unless they were already visited.

First off, there's a typo where you iterate over adjacent nodes. You want to traverse the top column, not the src one:

adjMatrix[node * amountOfNodes + top] != 0
//                               ~~^

Secondly, your current path implementation stores the visit order of nodes, not a path from the source to its destination. For the latter, you need to store the parent of each node, so that the final path can be restored by going from a child (destination) to its parent, grandparent, great-grandparent, ..., etc.

std::vector<int> parent(amountOfNodes, -1);

//...

if (visited[node] == false && (adjMatrix[node * amountOfNodes + top] != 0))
{
    Queue.push(node); // Add to end.
    visited[node] = true;
    parent[node] = top;
}

Restoring the path is straightforward:

int u = dest;            
do
{
    std::cout << u << " ";
    u = parent[u];
}
while (u != -1);

DEMO