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