Graph Theory: Dijkstra's Algorithm

[wubie]

Hello,

Does anyone know of an online resource which explains Dijkstra's Algorithm both in tabular form and graphical form?

My text does an incredibly poor job explaining this algorithm. I sort of understand it graphically. But I have absolutely no idea what is going on when it comes to implementing it in tabular form.

Here is a question which requires me to use Dijkstra's Algorithm. I have the answer both in tabular and graphical form, but I am running into problems understanding the answer in graphical form and I have NO idea what is going on with the tabular form.

A graph has 11 vertices labelled A to K, and the following 18 edges with their lengths given:

AB(8), AC(5), AD(7), BE(6), BF(2), CE(4), CF(5), DF(4), DG(2), EH(4), FH(4), FI(2), FJ(4), GI(2), GJ(4), HK(4), IK(5), JK(4).

Apply Dijkstra's Algorithm to construct a shortest-path spanning tree from the vertex A.

I understand the first choice: AC.
I now look at the fringe vertices of vertex A and C. I pick AD.
I now look at the fringe vertices of A,C,and D. I pick AB.
I now look at the fringe vertices of B,C,and D. Now do I pick DG or CE? And why? The answer is CE but I don't know why.

My text does not explain what to do in this situation. And the answer does not state its reason for choosing CE over DG.

Any help is appreciated. Thankyou.



Right. I just looked at the answer in tabular form and I think I can follow what is going on in tabular form. But I still don't understand the reasoning of choosing CE over DG.

 

[Hurkyl]

Because it came first in the list!

Both the path ADG and the path ACE have the same weight 9; neither is better than the other. You have to make a choice, and "pick the first one in case of a tie" is as reasonable of a strategy as any.

 

[wubie]

Alright. Thanks Hurkyl.

I found out why I couldn't figure out the tabular form. There was a couple of typo's in the table.

Cheers.