443,665 Members | 1,258 Online Need help? Post your question and get tips & solutions from a community of 443,665 IT Pros & Developers. It's quick & easy.

# Qquestion on Shortest paths algorithm

 P: n/a Hello. I have implemented the Dijkstra shortest path algorithm, it works fine but I have one question on how I can improve something. I want to find all the possible shortest paths from a node since there is a possibility to exist more than one shortest paths with the same distance. Does anyone has any idea how this could be done? Code double Dijkstra_Least_Cost(vector< vector::const_iterator iter; vector< vector(D_size,0)); outputfile <<"Starting from node: " << start_vertex << endl; //initialize the vectors distance.push_back(0); //in order to start from 1. not_checked.push_back(true); //in order to start from 1. predecessor.push_back(0); //in order to start from 1. for (ii = 1; ii < graph_size; ii ++) { distance.push_back(graph[start_vertex][ii]); not_checked.push_back(true); predecessor.push_back(start_vertex); } distance[start_vertex] = 0; //set start distance to zero predecessor = -1; predecessor[start_vertex] = -1; //default start predecessor not_checked[start_vertex] = false; //mark as checked vertex bool done = false; int testing = 0; while (!done) { int V, shortest_d = BIG; for (jj = 1; jj < graph_size; jj ++) { //if it is <= we get a different route. if (distance[jj] <= shortest_d && not_checked[jj]) { V = jj; shortest_d = distance[V]; } } not_checked[V] = false; //for every neighbor W of V //edge relaxation for (W = 1; W < graph_size; W++) { if (graph[V][W] < BIG && not_checked[W]) { //unchecked neighbor if (distance[W] distance[V] + graph[V][W]) { distance[W] = distance[V] + graph[V][W]; predecessor[W] = V; } } while (kk < graph_size && !not_checked[kk]) kk++; done = (kk == graph_size);//done=true if there are no unchecked neighbors } //*******************************************PRINT LEAST COST TO NODES for (ii = 1; ii < graph_size; ii++) { temp_d+=distance[ii]; outputfile << "To arrive at node " << ii << " will cost" << distance[ii] << endl; } average_distance = temp_d / (graph_size-2); //-2 because we dont count itself and also // the graph vector is 1 more than the number of nodes //E4 cout << endl; //*******************************************PRINT LEAST COST TO NODES cout << "Shortest Paths" << endl; //Print out all shortest paths stackfirst != start_vertex) { cout << iter->first << ": " << iter->second << endl; } } cout << endl; cout << "Number of times each link is counted for the Shortest Path" << endl; for ( ii = 1; ii < graph_size; ii++) { for (jj = 1; jj < graph_size; jj++) { if (betweennes_l[ii][jj] != 0 ) { cout << ii << "-"<< jj << "=" << betweennes_l[ii][jj]<< endl; } } } return average_distance; } Cheers costas Jul 26 '06 #1
5 Replies

 P: n/a co*********@gmail.com wrote: Hello. I have implemented the Dijkstra shortest path algorithm, it works fine but I have one question on how I can improve something. I want to find all the possible shortest paths from a node since there is a possibility to exist more than one shortest paths with the same distance. Does anyone has any idea how this could be done? [snip] //edge relaxation for (W = 1; W < graph_size; W++) { if (graph[V][W] < BIG && not_checked[W]) { //unchecked neighbor if (distance[W] distance[V] + graph[V][W]) { distance[W] = distance[V] + graph[V][W]; predecessor[W] = V; } } [snip] This is more of a programming question than a C++ question so you might try comp.programming. To briefly address your question, you need to modify the logic of the above snippet to include a check for dist[W] = dist[V] + graph[V][W]. In such a case rather than replacing the predecessor of W with V, you must add V to a list of W's predecessors. The result is that, instead of each vertex having a path of predecessors back to the start, each vertex has a tree of predecessors back to the start, with each path through the tree being an equal shortest path. Jul 26 '06 #2

 P: n/a Mark thanks for the reply. you are right on some point but the problem is that over there are passed only the values that have to do with the path that was already selected. mostly the problem is at //if it is <= we get a different route. for (jj = 1; jj < graph_size; jj ++) { if (distance[jj] <= shortest_d && not_checked[jj]) { V = jj; shortest_d = distance[V]; } } over there if i select <= and not < it gives another shortest path. the first problem it that it gives only 2 shortest paths ..and there are cases that there are more. The second problem is that even if I can see the two paths, i cannot store both of these paths. In order to achive it i have to modify the code (replace < with <= ) and run it for a second time. btw thanks for the tip. I have post it to comp.programming as well. Jul 26 '06 #3

 P: n/a Please quote the relevant portions of the message to which you are replying. co*********@gmail.com wrote: Mark thanks for the reply. you are right on some point but the problem is that over there are passed only the values that have to do with the path that was already selected. mostly the problem is at //if it is <= we get a different route. for (jj = 1; jj < graph_size; jj ++) { if (distance[jj] <= shortest_d && not_checked[jj]) { V = jj; shortest_d = distance[V]; } } I don't think so. The code above is to pick out the closest vertex not yet "finalized", which then becomes the source for the next relaxation pass. (And as an aside this is a pretty slow implementation since you take O(n) time to find that vertex. The conventional approach is to use a priority queue instead.) In any event, look back at my earlier reply. What you call the "edge relaxation" step is where you determine if there is a better route to a particular vertex. What you don't check for is the case of a tie-- two routes that are equally good. You need separate logic for the '>' case and the '=' case, but in the '=' case you need to save all equally good routes. As I said before, the way to do this is not to have a single predecessor value but a collection (list, vector, whatever) of values. Mark Jul 27 '06 #4

 P: n/a Ok I can see what you are saying. I have implemented it and it works ok now with the concept that you told me. Since my predecessor was already a vector i constracted a map and i store all the values of the predecessor when I have two equal length paths. My question now is how can i retrive these paths? Do I have to try all the possible combinations that can be made with the vectors (I can see a solution like that) or is there any easiest way. Cheers Costas Jul 27 '06 #5

 P: n/a co*********@gmail.com wrote: Ok I can see what you are saying. I have implemented it and it works ok now with the concept that you told me. Since my predecessor was already a vector i constracted a map and i store all the values of the predecessor when I have two equal length paths. My question now is how can i retrive these paths? Do I have to try all the possible combinations that can be made with the vectors (I can see a solution like that) or is there any easiest way. Cheers Costas Once again, when you reply to a post you need to quote the portion you're replying to. Just like I've quoted above what you wrote. The sets of predecessors define a DAG (directed acyclic graph). You'll need to build up all possible paths from start to finish. It's not that hard though-- you can do it recursively from the end point. Jul 27 '06 #6

### This discussion thread is closed

Replies have been disabled for this discussion. 