Dijkstra / prim algorithm ... help a little?

Question

I was wondering, for the dijkstra and prim algorithm, what happens when they choose between multiple vertices, and there are several vertices with the same weight.

for instance

Sample image http://img688.imageshack.us/img688/7613/exampleu.jpg

Answer 1

It does not matter. Usually the tie will be broken in some way, in which way the node was added to the priority queue.

Dijkstra's goal is to find the shortest path. If you want to find all the shortest paths, you have to worry about connections.

Answer 2

There may be several MSTs, and whatever the random binding rules you use may give you another, but it will still be MST.

For example, you can imagine the triangle ABC, where all the weights of the edges are unit. In this case, there are three MSTs, and all of them are minimal.

The same goes for Dijkstra and the shortest path spanning a tree - there may be several shortest spanning trees.

Answer 3

Correct me if I am wrong, but your chart has no alternative ways to apply Dijkstra's algorithm.

Answer 4

Dijkstra's algorithms extend (or “relax”) all edges from touches, but do not extend a node (or a “gray” node) at the lowest cost.

If two nodes have the same cost, well ... it's just random :)