BFS mit OpenMPI

Question

Ich versuche, eine Breite-zuerst-Suche mit OpenMPI zu implementieren (auf C++, wenn es relevant ist) und ich habe fast alles läuft, bis auf das Ende. Ich weiß nicht wann/wie ich die Ausführung stoppen kann.

Ich benutze ein 2D-Array den Überblick über alle Kanten in dem Diagramm zu halten, wie folgt:

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

Mein aktueller Algorithmus ist:

1. Root-0-Abstand hat, andere haben INT_MAX
2. Root sendet Distanz zu allen seinen Nachbarn und stoppt
3. Jeder andere Knoten empfängt eine Entfernung
4. If neue Strecke ist besser (kleiner) als aktuelle Entfernung, zu aktualisieren Abstand und alle anderen Nachbarn für immer die neue Strecke
5. Wiederholen sendet beginnend bei Schritt 3

ich nicht wirklich wissen, wie der fünften Schritt zu ändern, so dass alles hört auf. Ich teste auf einer kleinen Grafik (so kann ich leicht verfolgen, was passiert) und es stoppt ziemlich bald, was bedeutet, dass alle Nicht-Root-Prozesse in Schritt 3 stecken bleiben, weil jede minimale Distanz gefunden wurde und kein Prozess ein Update sendet.

Ich habe meinen Code nicht eingefügt, weil der Algorithmus ziemlich einfach zu verstehen sein sollte und meine Frage eher mit dem Algorithmus als mit dem Code selbst zusammenhängt.

Answer 1

Die Lösung, die ich fand, besteht darin, einen Zwischenschritt zwischen 4 und 5 hinzuzufügen, der eine Aktualisierung vom Prozess an den Stamm sendet.

Nach jeder Iteration sendet der Prozess p eine Nachricht an das Stammverzeichnis und teilt ihm mit, ob der Abstand dieser Iteration aktualisiert wurde oder nicht. Wenn alle Prozesse "berichten", dass sie die Entfernung nicht aktualisiert haben, erhalten sie eine Nachricht zum Stoppen (von der Wurzel).

So die Pseudo-Code zu ändern:

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