Phoenix Holmes - 3 months ago 33

C++ Question

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.