🔀

Shortest Path Routing Algorithm

May 30, 2024

Shortest Path Routing Algorithm

Overview

  • Also known as Dijkstra's Algorithm
  • Developed by Edsger Dijkstra
  • Aim: Find the shortest path from source router to destination router in a graph

Graph Representation

  • Routers: Represented by nodes (e.g., A, B, C, D, E, F, G, H)
  • Edges: Represent communication links between nodes
  • Weights: Represent distance, cost, or delay between nodes

Node Types

  1. Tentative Node: Represented by a white circle (e.g., C, D)
  2. Working Node: Represented by an arrow/circle (e.g., A, B, G)
  3. Permanent Node: Represented by a solid circle

Algorithm Steps

Initial Configuration

  1. Source Node: Set as current working node and marked permanent
  2. Other Nodes: Marked as tentative

Step-by-Step Process

  1. Explore Current Working Node (source node)
    • Find neighboring routers of the source node (e.g., from A to B and G)
      • Update path lengths (distance + current working node)
      • Example: A to B (cost: 2, path: 2, current node: A)
      • Example: A to G (cost: 6, path: 6, current node: A)
    • Unexplored nodes updated to infinity (∞)
  2. Select Next Node
    • Choose the node with the smallest path cost (e.g., B with cost 2)
    • Mark selected node as permanent and set as current working node
  3. Repeat Process
    • Explore newly selected working node (e.g., B)
      • Update path lengths for neighboring nodes (e.g., E and C)
      • Example: B to C (cost: 7 + 2 = 9, path: 9, current node: B)
      • Example: B to E (cost: 2 + 2 = 4, path: 4, current node: B)
    • Continue selecting the node with the smallest path cost
  4. Update Paths
    • Recalculate paths for neighboring nodes if a shorter path is found
    • Example: E to G (cost: 4 + 1 = 5, path: 5, current node: E)
    • Update if new path is shorter than the previously known path
  5. Final Steps
    • Continue the process until the destination node is reached
    • Example: From F to H to D, update paths and costs accordingly
    • Final path from A to D: A -> B -> E -> F -> H -> D

Calculation Example

Path Calculation

  • Source Node A to Destination Node D
    1. A to B: Cost 2
    2. B to E: Cost 2
    3. E to F: Cost 2
    4. F to H: Cost 2
    5. H to D: Cost 2
  • Total Cost: 2 + 2 + 2 + 2 + 2 = 10

Summary

  • This algorithm systematically finds the shortest path by iteratively selecting the node with the smallest known path cost and updating neighboring nodes' path costs.
  • Key steps involve marking nodes as tentative or permanent and continually exploring the most cost-effective paths.

Full transcript