2つのノードが互いに接続されているかどうかを調べるにはどうすればよいですか？

Question

このコードは最短経路を検出しますが、目的地に到達することすらできない場合は考慮しません。この機能を実行する前に目的地に到達可能かどうかをどうすれば確認できますか？

void Trains::shortestPath(int src, int dest) 
{ 
    set< pair<int, int> > setds; 
    vector<int> dist(V, INF); 
    setds.insert(make_pair(0, src)); 
    dist[src] = 0; 
    while (!setds.empty()) 
    { 
     pair<int, int> tmp = *(setds.begin()); 
     setds.erase(setds.begin()); 
     int u = tmp.second; 
     list< pair<int, int> >::iterator i; 
     for (i = adj[u].begin(); i != adj[u].end(); ++i) 
     { 
      int v = (*i).first; 
      int weight = (*i).second; 
      if (dist[v] > dist[u] + weight) 
      { 
       if (dist[v] != INF) 
        setds.erase(setds.find(make_pair(dist[v], v))); 
       dist[v] = dist[u] + weight; 
       setds.insert(make_pair(dist[v], v)); 
      } 
     } 
    } 
    printf("Vertex Distance from Source\n"); 
     printf("%d \t\t %d\n", dest, dist[dest]); 
} 

出力：あなたはすべてのコードを見たい場合、これがわずかhttp://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/から変更されて

Vertex Distance from Source 
4  73 

。

Answer 1

ソースからdfsを実行し、ノード宛先が訪問された簡単な方法は、Dijkstraのアルゴリズムより前にO（N + M）で実行されます。
グラフが指向していない場合は、O（N + M）で接続されたコンポーネントに分割し、アルゴリズムを実行する前にチェックします。

アドバイス：
代わりにpriority_queueを使用すると、より高速になります。