473,320 Members | 2,004 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Qquestion on Shortest paths algorithm

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 <intdistance;
vector <intpredecessor;
vector <boolnot_checked;
map <int,intintermediate_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<inttemp; //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

Jul 26 '06 #1
5 2846
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
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
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
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

Jul 27 '06 #5
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 <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.
Jul 27 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Lau | last post by:
How do I easily calculate the shortest path between two geographical spots on a map? The map is divided into zones. So I guess it is possible to use Dijkstra’s Shortest Path algorithm, but it...
6
by: ThanhVu Nguyen | last post by:
Hi all, I need recommendation for a very fast shortest path algorithm. The edges are all directed, positive weights. Dijkstra shortest path will solve it just fine but the if the graph is not...
20
by: Webdad | last post by:
Hi! I running my first year as industrial engineer (informatics) We have an assignment to do : .... create a playfield (matrix). Some places in that field are blocked, so you can't pass them....
5
by: leezard | last post by:
I am developing a program using VB.NET that will accept a start and end point, the system then will generate the shortest path to reach the end point. Anyone here have idea on doing this or some...
1
by: Adam Hartshorne | last post by:
Hi All, I know how to calculate the all-pair shortest paths matrix on an undirected graph. I was wondering how I could extend this to calculate the all-pair average path, or if not a simple...
4
by: Shuch | last post by:
Hi all, I am in shortage of time...and i want to know if someone has a code written in c++ or c for finding the shortest path using stack or queue??????my specifications r as follow: Input...
8
by: abhradwip | last post by:
I want to write a program which will find the shortest path between n no. of cities using dijkstra's algorithm ...... but could not do it..... i have written a program which will give the shortest...
4
prometheuzz
by: prometheuzz | last post by:
Hello (Java) enthusiasts, In this article I’d like to tell you a little bit about graphs and how you can search a graph using the BFS (breadth first search) algorithm. I’ll address, and...
2
by: shashankbs | last post by:
Given a topology and a certain node X, find the shortest path tree with X as the root. * Input: a topology file similar to the following (which is a three-node ring) ...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.