Phoenix Holmes - 1 year ago 93
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;
{
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.