c++ - 如何判断两个节点是否相互连接？

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 而不是设置，它会更快。