# Dijkstra's algorithm question

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

## 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 on other sites
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 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:
i didn't say something like this, read again how i put it in my OP

##### Share on other sites
Quote:
 edit:>You don't add the distancesi 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 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 distancesi didn't say something like this, read again how i put it in my OP

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

##### 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 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 on other sites
Quote:
 Original post by yapposaiI 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 on other sites
the first distance B = min (inf, dist(A,A) + Edge(AB))
min( inf, 0 + Edge(AB))
= Edge(AB)

##### 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...

1. 1
Rutin
31
2. 2
3. 3
4. 4
5. 5

• 13
• 40
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632963
• Total Posts
3009534
• ### Who's Online (See full list)

There are no registered users currently online

×