Jump to content
  • Advertisement
Sign in to follow this  
valla2

Dijkstra's algorithm question

This topic is 4816 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a question. In the beginning, the distance of all the vertices from the source vertex is infinity. Then, to save a new distance for a vertex B, its distance from the vertex A you came from ( this is the weight of the edge A-B ) plus the distance of A from the source vertex must be smaller than the previous distance of B (from the source vertex), right? Ok so the first time you enter this procedure, since all distances are initialiezed to infinity, the addition of the two distances i mentioned will give a result of infinity too, which means i 'll never get a distance smaller than infinity for all the vertices in my graph! Not to mention that i could get an overlfow error when i add MAX_INT + x. So what should i do?? thanks in advance

Share this post


Link to post
Share on other sites
Advertisement
You don't add the distances, you change the original distance with the new one, if it's smaller. That's why infinity it's used at first, so that the first distance is allways smaller.

Share this post


Link to post
Share on other sites
>you change the original distance with the new one, if it's smaller.

and to calculate the new distance you add the distance of vertex A and the weight of the edge A->B, and this means you still have infinity.

??

edit:
>You don't add the distances
i didn't say something like this, read again how i put it in my OP

Share this post


Link to post
Share on other sites
Quote:
edit:
>You don't add the distances
i didn't say something like this, read again how i put it in my OP


I'm having trouble understanding what you're saying at all, you should really pay more attention to your english.

Quote:
>you change the original distance with the new one, if it's smaller.

and to calculate the new distance you add the distance of vertex A and the weight of the edge A->B, and this means you still have infinity.


All nodes distance are initialized to infinity except the starting node.

Share this post


Link to post
Share on other sites
Quote:
Original post by valla2
>you change the original distance with the new one, if it's smaller.

and to calculate the new distance you add the distance of vertex A and the weight of the edge A->B, and this means you still have infinity.

??

edit:
>You don't add the distances
i didn't say something like this, read again how i put it in my OP

Blah blah plus blah blah adition blah blah add blah +.
Could have fooled me. Sounds to me like you should take his advice: replace, don't add.[smile]

Share this post


Link to post
Share on other sites
Quote:

I'm having trouble understanding what you're saying at all, you should really pay more attention to your english.

It would be wiser to ask for a clarifing question instead of making thins up, then. As for my English, if you can't help me with my algorith problem you are welcome to correct my English mistakes instead of flaming.

>All nodes distance are initialized to infinity except the starting node.
yeah i know this

iMalc, i do replace... But to calculate the new value you have to make a little addition. And the starting value is infinity :/

Share this post


Link to post
Share on other sites
I think all distances of the vertices are initialized to infinity EXCEPT the starting vertex which is 0 since the distance between the starting vertex with itself is 0.

Share this post


Link to post
Share on other sites
Quote:
Original post by yapposai
I think all distances of the vertices are initialized to infinity EXCEPT the starting vertex which is 0 since the distance between the starting vertex with itself is 0.


Yeah yapposai i know that. But what happens the first time you replace the first distance? What will the new value be?

Share this post


Link to post
Share on other sites
oh... i got it! For some reason a kept missing a condition in an if statement, thanks yapposai :)

Now i have another question. If anyone can help me i would appreciate it.

We are in the phase where we choose the vertex we are going to visit next. We pick the vertex that was not visited before, and that has the minimum distance so far. Ok i understand why we choose one that was not visited before by our program, but why does it have to have the smallest distance so far? Our algorithm will finally visit all the vertices, so why do we visit the vertices in that order? Isn't that an extra loop we can ommit? We can just visit them randomly?

For example:
edit:
if
A-B = 5
A-C = 10
B-D = 20 -> A->D = 25
whether we visit the vertices in this order:

//this is what the algorith does
B - D
/
A
\
C

or this:


// this is what i say the algorith could do without any probs
C - D // C means that B will visited 3rd...
/
A
\
B // B means that C will be visited 2nd...

is the same thing.. the resulting values will be the same..
?

wait.. now that i think of it, what we should do is not visit them randomly, but firstly visit only the ones that don't have an inifinitive distance...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!