Qquestion on Shortest paths algorithm

[costantinos]

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<int> > graph, int
start_vertex, ofstream &outputfile)
{
unsigned int graph_size = graph.size();
unsigned int D_size = graph_size + 1;
unsigned int ii, jj, W;
unsigned int kk = 1;
double average_distance = 0;
double temp_d = 0;

vector <int> distance;
vector <int> predecessor;
vector <bool> not_checked;
map <int,int> intermediate_nodes;
map<int, int>::const_iterator iter;
vector< vector<int> > betweennes_l(D_size, vector<int>(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[0] = -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
stack<int> temp; //No recursion- use stacks
for (ii = 1; ii < graph_size; ii++)
{
int m = ii;
int m1;

while (predecessor[m] != -1)
{
m1 = m;
temp.push(m);
//intermediate_nodes[m]++; //how many times a node was used along
the
// paths. we will count the paths of length > 1
m = predecessor[m];
betweennes_l[m][m1]++;
intermediate_nodes[m]++; //how many times a node was used along the
//paths. we will count the paths of length > 2
}

int flag = 0;

while ( !temp.empty() )
{
if (flag ==0 )
{
cout << start_vertex;
}
cout << "-"<< temp.top();
flag++;
temp.pop();
}
cout << endl;
}



for (iter=intermediate_nodes.begin(); iter !=
intermediate_nodes.end(); ++iter)
{
if (iter->first != 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

 

[Mark P]

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.

 

[costantinos]

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.

 

[Mark P]

Please quote the relevant portions of the message to which you are replying.

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

 

[costantinos]

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 <int, vector <int>> 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

 

[Mark P]

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 <int, vector <int>> 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.