I was wondering for dijkstra's and prim's algorithm, what happens when they are choosing between more than one vertex to go to ,and there are more than one vertex with the same weight.
For example
+3
A:
It doesn't matter. Usually the tie will be broken in some arbitrary way like which node was added to the priority queue first.
The goal of Dijkstra is to find a shortest path. If you wanted to find all shortest paths, you would then have to worry about ties.
mathmike
2010-04-28 15:26:49
Starting at vertex a and assuming it just updated b and c, First it would go to vertex c, then update the weight for vertex d and vertex e. Now vertex e has weight 5, and so does vertex b. How does it choose which one to go to next? mathmike are you saying it is random?thanks
bfpri
2010-04-28 15:30:39
Yes, it's essentially random.
mathmike
2010-04-28 15:31:30
"random" is probably not the word you want to use in a computer science context - that usually means "roll of the dice" random. The choices you allow here are "arbitrary" - any possible method for choosing among the tied values is fine.
Keith Randall
2010-04-29 02:15:43
A:
Correct me if I'm wrong, but your graph doesn't have any alternate paths for Dijkstra's algorithm to apply.
dhdean
2010-04-28 15:27:43
Yea, not for prim's..but maybe dijkstra'sStarting at vertex a and assuming it just updated b and c, First it would go to vertex c, then update the weight for vertex d and vertex e. Now vertex e has weight 5, and so does vertex b. How does it choose which one to go to next? mathmike are you saying it is random? thanks
bfpri
2010-04-28 15:32:46
A:
Dijkstra algorithms expands (or "relaxes") all the edges from a touches but not expanded node (or "gray" node) with the smallest cost.
If two nodes have the same cost, well... it's just random :)
Tristram Gräbener
2010-04-28 15:27:58
+2
A:
There could be multiple MSTs, and whichever arbitrary tiebreaking rules you use might give you a different one, but it'll still be a MST.
For example, you can imagine a triangle A-B-C where all the edge weights are one. There are three MST in this case, and they are all minimum.
The same goes for Dijkstra and the shortest path spanning tree -- there could be multiple shortest path spanning trees.
Larry
2010-04-28 15:28:42
Starting at vertex a and assuming it just updated b and c, First it would go to vertex c, then update the weight for vertex d and vertex e. Now vertex e has weight 5, and so does vertex b. How does it choose which one to go to next? mathmike are you saying it is random? thanks
bfpri
2010-04-28 15:31:04
I'm not mathmike, but I'm saying it doesn't matter, so you can make it random if you like.
Larry
2010-04-28 15:32:09
And it is not "random" in the true sense of the word, but it is what you program it to be -- sometimes breaking ties by smallest index, or shortest edge length. It depends on the implementation.
Larry
2010-04-28 15:33:59