BFS with OpenMPI

Question

I'm trying to implement a breadth-first search using OpenMPI (on C++ if it's relevant) and I got almost anything running, except for the very end. I don't know when/how to stop the execution.

I use a 2D array to keep track of all the edges in the graph as follows:

graph[start][finish] - there is an edge from vertex start to vertex finish

My current algorithm is:

1. Root has distance 0, others have INT_MAX
2. Root sends distance to all its neighbors and stops
3. Each other node receives a distance
4. If new distance is better (smaller) than current distance, update distance and send all other neighbors the new distance
5. Repeat forever starting at step 3

I don't really know how to change the 5th step so that everything stops. I test on a small graph (so I can easily follow what's happening) and it stops pretty soon, meaning all non-root processes get stuck at step 3, because every minimum distance has been found and no process is sending an update.

I didn't include my code because the algorithm should be pretty easy to understand and my question is more related to the algorithm than to the code itself.

Answer 1

The solution I found is to add an intermediary step between 4 and 5 which sends an update from the process to the root.

After each iteration, the process p will send a message to the root telling it whether it updated the distance this iteration or not. When all processes "report" that they haven't updated the distance they will receive a message to stop (from the root).

So to change the pseudocode:

if (rank == 0) // root
{
    distance = 0;
    for each neighbor
        send distance

    vector<bool> status(no_processes - 1, true)
    while (status contains one true value)
        receive update from one process
        update status

    // status is full of false
    send all STOP
}
else
{
    distance = INT_MAX;
    while (true)
    {
        receive message

        if STOP
            stop execution

        status = false;
        if (recv_distance + 1 < distance)
        {
            status = true

            distance = recv_distance + 1;

            for each neighbor
                send distance
        }

        send status to root
    }
}