DijkstrasAlgorithm

Back to ComputerTerms

This is a greedy algorithm that calculates the shortest path from one point to all nodes in a graph.

1. Initialize the confirmed list with an entry for myself; this entry has a cost of 0.

2. For the node just added to the confirmed list in the previous step, call it node Next, select its Link State Packet (see LinkState)

3. For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum of the cost from myself to Next and from Next to Neighbor.

   1. If Neighbor is currently on neither the Confirmed nor the Tentative list, then add <Neighbor,Cost,Next Hop> to the Tenative list, where Next Hop is the direction I go to reach Next.

   2. If Neighbor is currently on the Tentative list, and the Cost is less than the currently list cost for Neighbor, then replace the current entry with <Neighbor,Cost,Next Hop>, where Next Hop is the direction I go to reach Next.

4. If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to step 2.

Back to ComputerTerms