dijkstra/prim's algorithm...a little help?

Question

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

Example Image http://img688.imageshack.us/img688/7613/exampleu.jpg

Answer 1

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.

Answer 2

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.