# Dijkstra's algorithm question

This topic is 4600 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...

##### Share on other sites
i have another qeustion..

Suppose you have many computers and you want to know the shortest length of a wire to connect them and make a network. Can this problem be solved with Dijkstra?

##### Share on other sites
Quote:
 Original post by valla2i have another qeustion..Suppose you have many computers and you want to know the shortest length of a wire to connect them and make a network. Can this problem be solved with Dijkstra?

That's called a "minimum spanning tree". That's definately not what Dijkstra's algorithm is for.

Google for "minimum spanning tree", in combination with either "Prim" or "Kruskal", which are the most used algorithms for that problem.

##### Share on other sites
oh... i thought the problem i described was the travelling salesperson problem because each computer can be thought as a town and the wires are the roads. It is not becuase you don't know where to start "travelling" from?

##### Share on other sites
Travelling Salesman is if you need the network to be a cycle, so that when every computer is connected to exactly two others, and if you follow it in the same direction long enough you end up at the one you started.

If you only need there to be a path from every computer to every other computer with a minimal amount of wire, it's Minimum Spanning Tree (which is much easier to generate).

##### Share on other sites
and that means that the 2 algorithms ( the one for TSP and the other for MST ) are very different? :(

thank you Urxae

##### Share on other sites
Well, since there are widely known efficient algorithms for MST, but there is no known (to the general public anyway) efficient algorithm for TSP (despite there being a million-dollar prize for the person who finds and publishes one), they're probably rather different.
However, IIRC, one or both of Prim's and/or Kruskal's is rather similar to Dijkstra's. I'm not sure though, it's been almost two years since I took that class.

##### Share on other sites
oh... thank you :)

##### Share on other sites

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