Phoenix Holmes Phoenix Holmes - 4 months ago 41
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());
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

This is slightly modified from if you want to see all the code.


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).

better use priority_queue instead set, it will be faster.