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:
- Root has distance 0, others have INT_MAX
- Root sends distance to all its neighbors and stops
- Each other node receives a distance
- If new distance is better (smaller) than current distance, update distance and send all other neighbors the new distance
- 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.
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: