Phoenix Holmes Phoenix Holmes - 9 days ago 5
C++ Question

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.

Answer

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.