無向グラフと無重みグラフの2つのノード間の距離を求める

Question

グラフ内のsからtまでの距離を求めたい。どのように距離を見つけるためにbfsを変更するか、良いO(n)を持つ別のアルゴリズムを使用することができます。正確には、グラフは次の2つのノード間（最短）距離を見つけるために、BFSを変更することができる非加重と

Answer 1

無向であることが重要です。

このアルゴリズムを使用する前に注意すべき二つの重要なポイント：

• グラフのエッジは重量またはのいずれかを持っています。
• グラフは無指向性です。

注意すべきもう一つの重要なことは、次のとおりです。

• あなたは、各ノードを訪問する際に最適な距離の条件をチェックする必要があるため、あなたはノードをマークするブール配列を必要としません。
• デキューを使用してノードを格納します。
• エッジの重みは1ある場合、それは前方に、後方にそれが0ある場合押し込まれます。ここ

実装

、エッジ[V] [I]ペアの形態で存在する隣接リストである[V] 縁、すなわち[I]意志を1次回vが接続されているノードを含み、edges [v] [i] .secondは、vとedges [v] [i] .firstの間の距離を含みます。

Qは、ダブルエンドキューです。距離は配列です。distance [v]には、開始ノードからvノードまでの距離が含まれます。最初、ソースノードから各ノードまでの距離は、無限大です。

void bfs (int start) 
{  
     deque <int > Q;  //Double-ended queue 
     Q.push_back(start); 
     distance[ start ] = 0;  
     while(!Q.empty()) 
      { 
      int v = Q.front(); 
      Q.pop_front(); 
      for(int i = 0 ; i < edges[v].size(); i++) 
      { 


      /* if distance of neighbour of v from start node is greater 
      than sum of distance of v from start node and edge weight between v and its neighbour 
      (distance between v and its neighbour of v) ,then change it */ 


      if(distance[ edges[ v ][ i ].first ] > distance[ v ] + edges[ v ][ i ].second) 
      { 

       distance[ edges[ v ][ i ].first ] = distance[ v ] + edges[ v ][ i ].second; 

      /*if edge weight between v and its neighbour is 0 then push it to front of 
      double ended queue else push it to back*/ 

       if(edges[ v ][ i ].second == 0) 
       { 
        Q.push_front(edges[ v ][ i ].first); 
       } 
       else 
       { 
         Q.push_back(edges[ v ][ i ].first); 

       } 
      } 
      } 
     } 
}