D_basham

asked on

# If anyone is real familar with dijstra shortest path algorithm please help

Good morning, how are you doing? I was wondering if there is anybody that is really familar with dijstra algorithm could I post my code on it and explain to me why it isn't working. I have looked at this code and the algorithm a 100 times and I don't see why it isn't working. Thanks I will post code when someone responds.

ASKER

Thank you so much. I am just not seeing something here. What is happening is the index positions that I want to visit in my distance are working but it is only visting or next is only getting set equal to 0,2,6 of the distance array which obviously are my vertext positions in my graph. I am not visiting 3,4,5? And I can't figure out why. Thank you very much for help.

for(int i=1; i<MAXIMUM; i++)

{

distance[i] = INT_MAX;

}

distance[start] = 0;

used_vertex.clear();

occurs = used_vertex.count(next);

for(allowed_size =1; allowed_size< MAXIMUM; allowed_size++)

{

for(int j=0; j<MAXIMUM; j++)

{

occurs = used_vertex.count(next);

if(occurs == 1)

{

next++;

}

else if(distance[j] < distance[j+1])

{

next = j;

}

}

used_vertex.insert(next);

for(v=0; v<MAXIMUM; v++)

{

occurs1 = used_vertex.count(v);

if (occurs1 == 0 && edges[next][v] != 0)

{

sum= distance[next] + (edges[next][v]);

if(sum < distance[v])

{

distance[v] = sum;

predecessor[v] = next;

}

}

}

}

for(int i=1; i<MAXIMUM; i++)

{

distance[i] = INT_MAX;

}

distance[start] = 0;

used_vertex.clear();

occurs = used_vertex.count(next);

for(allowed_size =1; allowed_size< MAXIMUM; allowed_size++)

{

for(int j=0; j<MAXIMUM; j++)

{

occurs = used_vertex.count(next);

if(occurs == 1)

{

next++;

}

else if(distance[j] < distance[j+1])

{

next = j;

}

}

used_vertex.insert(next);

for(v=0; v<MAXIMUM; v++)

{

occurs1 = used_vertex.count(v);

if (occurs1 == 0 && edges[next][v] != 0)

{

sum= distance[next] + (edges[next][v]);

if(sum < distance[v])

{

distance[v] = sum;

predecessor[v] = next;

}

}

}

}

Sorry - could you post a bit more of your code? It'd be helpful to look at what some of these variables and methods are...

baboo_

baboo_

ASKER CERTIFIED SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Do you mind to post all your code or just important ... and why your program doesn't work ? ==> Any compiling error or just the algorithm gave you the wrong results or it halted during the running time ?

ASKER

Here are my variables locally in the dijkstra() function. The used_vertex is not my class it is my set. Graph is my class.

I knew there was a problem with my for loop trying to visit all vertexes. I tried a while loop and was not getting that too work at all. When I through in a cout statement to see what vertexes I was setting next to. It was only seeing 0, 2, 6 and skipping 1,3,4,5.

Could I just use a bool variable instead of isDone()? Thanks

int distance[MAXIMUM];

int predecessor[MAXIMUM];

set<int> used_vertex;

int v, allowed_size, sum,next=0,occurs, occurs1, weight,j=0;

CS

I knew there was a problem with my for loop trying to visit all vertexes. I tried a while loop and was not getting that too work at all. When I through in a cout statement to see what vertexes I was setting next to. It was only seeing 0, 2, 6 and skipping 1,3,4,5.

Could I just use a bool variable instead of isDone()? Thanks

int distance[MAXIMUM];

int predecessor[MAXIMUM];

set<int> used_vertex;

int v, allowed_size, sum,next=0,occurs, occurs1, weight,j=0;

CS

ASKER

Wouldn't this work in the while see if the next is not in the set then keep going? Thanks

while( used_vertex.count(next) == 0 )

{

int dMin = INT_MAX;

for(int j=0; j<MAXIMUM; j++)

{

if( used_vertex.count(j) == 0 && distance[j] < dMin )

{

dMin = distance[j];

next = j;

}

}

cout<<next<<"\n";

used_vertex.insert(next);

while( used_vertex.count(next) == 0 )

{

int dMin = INT_MAX;

for(int j=0; j<MAXIMUM; j++)

{

if( used_vertex.count(j) == 0 && distance[j] < dMin )

{

dMin = distance[j];

next = j;

}

}

cout<<next<<"\n";

used_vertex.insert(next);

I think it is not neccessary ... because next is always in the set when you use 'used_vertex.insert(next)' ... I think the code of baboo is almost correct, just add the 'used_vertex.insert(next)' after the first loop of finding the mininum distance in the non-visited vertexes. To check if all the vertexes have been visited or not you can use 'while (used_vertex.count() == MAXIMUM)' ==> to be sure all vertexes have been visited.

ASKER

Would parameter would I pass the the count function next?

ASKER

Maybe the trouble I am having is not setting my predecessor[] to 0 or INT_MAX? Like I am with my distance because when I tried to ouptut the path and I pick like my last value and go to my first value of vertexes it blows up with a run time error. Does that make since to set my predecssesor array to all zero or something is that my issue here is my code to output the path from destination back to source or start:

v=goal;

cout<<distance[goal]<<"\n";

cout<<goal<<endl;

while(goal != start)

{

goal = predecessor[goal];

cout<<goal<<endl;

}

Thank you for all your help

v=goal;

cout<<distance[goal]<<"\n"

cout<<goal<<endl;

while(goal != start)

{

goal = predecessor[goal];

cout<<goal<<endl;

}

Thank you for all your help

ASKER

This is what I tried and it visted all vertexs but I can't go from my last vertex to my first it blows up. Why is that? Is it this code or how I

Set my predecessor? Thank you all for your help. :)

while( index < MAXIMUM )

{

int dMin = INT_MAX;

for(int j=0; j<MAXIMUM; j++)

{

used_vertex.insert(next);

if( used_vertex.count(j) == 0 && distance[j] < dMin )

{

dMin = distance[j];

next = j;

}

}

index++;

Set my predecessor? Thank you all for your help. :)

while( index < MAXIMUM )

{

int dMin = INT_MAX;

for(int j=0; j<MAXIMUM; j++)

{

used_vertex.insert(next);

if( used_vertex.count(j) == 0 && distance[j] < dMin )

{

dMin = distance[j];

next = j;

}

}

index++;

ASKER

I know the issue now if I chose a vertex that is anything other then 0 such as 3 then it will keep going up to MAXIMUM and never viste 0,1,or 2. How can I fixe that? Thank you. Based on that while loop?

ASKER

Thanks everyone I have it now. The insert next into my set was in the wrong place. Sorry okidachi the insert needed to be outside the for loop it was blowing me up inside. Thanks for the help thought.

baboo_