CODEWITHSUNDEEP
c++algorithm
Phoenix Holmes
Phoenix Holmes

Reputation: 69

How to determine if two nodes are connected to each other?

This code finds the shortest path but it does not take into account if the destination can even be reached. How could I check if the destination is reachable before running this function?

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

Output:

Vertex   Distance from Source
4        73

This is slightly modified from http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/ if you want to see all the code.

Upvotes: 1

Views: 855

Answers (1)

gdhsnlvr
gdhsnlvr

Reputation: 38

Easy way is run dfs from source and watch is node destination is visited, it runs in O(N + M) before Dijkstra`s algorithm.
If your graph is not oriented, split it to connected components once by O(N + M) and check before run your algorithm, if source and destination in same components by O(1).

Advice:
better use priority_queue instead set, it will be faster.

Upvotes: 1

Related Questions