2.3.5 Path Algorithms

• Dijkstra’s algorithm

  • finds the shortest path between two nodes in a weighted graph
  • used to determine the optimal route to use when forwarding packets through a network
  • implemented using a priority queue, with the smallest distances being stored at the front of the list
• Example of Dijkstra's algorithm

  
• Dijkstra's Algorithm

  
• A* Algorithm

  
• Dijkstra's algorithm worked example

  
• 2. Drawing the table

  A) 0

  B) 4

  C) 3

  D) 2

  E) A

  F) A

  G) A

  H) yes

  I) 4

  J) D

  K) yes

  L) 8

  M) B

  N) yes

  O) yes

  P) 9

  Q) F

  R) yes

  S) yes

  T) yes