Sign in to follow this  

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.

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
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
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 this post


Link to post
Share on other sites
Quote:
Original post by valla2
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?


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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this