如何确定两个节点是否相互连接？

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]); 
} 

输出：

Vertex Distance from Source 
4  73 

，如果你想看到所有的代码，这是略有http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/修改。

Answer 1

简单的方法是从源代码运行dfs并观察节点目的地是否被访问，它在Dijkstra算法之前在O（N + M）中运行。
如果你的图不是面向对象的，在O（N + M）中将它分割成连接的组件，并且在运行算法之前检查，如果O（1）中的源和目标位于相同的组件中。

建议：
更好地使用priority_queue代替设置，它会更快。