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

I was wondering for dijkstra's and prim's algorithm, what happens when they are choosing between more than o开发者_StackOverflow中文版ne 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

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.

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.

Correct me if I'm wrong, but your graph doesn't have any alternate paths for Dijkstra's algorithm to apply.

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 :)