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.
   1. For the node just added to the confirmed list in the previous step, call it node '''Next''', select its Link State Packet (see LinkState)
   1. 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'''.
      a. 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'''.
      a. 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'''.
   1. 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