OpenMPIを使用したBFS

Question

OpenMPIを使用して幅優先探索を実装しようとしています（関連性のあるC++の場合）。私は実行をいつ/いつ止めるべきかわかりません。

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

私の現在のアルゴリズムである：以下のように

私はグラフのすべてのエッジを追跡するために2次元配列を使用

1. ルートは、距離0を有し、他の人が持っているINT_MAX
2. ルートはすべての近隣ノードに距離を送信し、停止します
3. 他のノードはそれぞれ距離を受信します
4. If新しい距離は現在の距離、更新間隔よりも（小さい）方が良いと私は本当にそのように第五ステップを変更する方法がわからない3

ステップで始まる

繰り返し永遠に他のすべてのネイバーに新しい距離を送りますすべてが止まる。私は小さなグラフでテストしているので、すべての最小距離が見つかってプロセスがアップデートを送信していないので、すべてのルート以外のプロセスがステップ3でスタックすることを意味します。

アルゴリズムはかなり理解しやすく、私の質問はコード自体よりもアルゴリズムに関連しているため、私のコードは含まれていませんでした。

Answer 1

解決策は、プロセスからルートに更新を送信する4と5の間に中間ステップを追加することです。

各反復の後、プロセスpは、この繰り返しの距離を更新したかどうかを伝えるメッセージをルートに送信します。すべてのプロセスが距離を更新していないことを「報告」すると、（ルートから）停止するメッセージが表示されます。

だから、擬似コードに変更するには：

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