Dijkstra’s algorithm

• 1. Put root I.e., (myID, 0, 0) in P & (myID,0) to R.
• 2. If node N is just put into P, look at N’s links (I.e. its LSP).
  • 2a. For each link to neighbor M, add cost of the root-to-N-path to the cost of the N-to-M-link (from LSP) to determine a new cost: C.
  • 2b. The “next-hop” corresponds to the next-hop ID in N’s tuple (or N if M is the root itself): h
  • 2c. If M not in T (or P) with better path cost, add (M, C, h) to T.
• 3. If T = empty, terminate. Else, move the min-cost triple from T to P, and add (M, h) to R. Go to step 2.

Previous slide

Next slide

Back to first slide

View graphic version