Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory: Dijkstra's Algorithm

  1. Dec 5, 2003 #1

    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.

    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.
    Last edited by a moderator: Dec 5, 2003
  2. jcsd
  3. Dec 5, 2003 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  4. Dec 5, 2003 #3
    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.

    Last edited by a moderator: Dec 5, 2003
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook