Shortest Path Problem in
Network Model
Step-by-Step Example Using Dijkstra's
Algorithm
Problem Setup
• Goal: Find the shortest path from City A to City
E.
• Cities and Distances:
• A → B: 4 km
• A → C: 1 km
• B → C: 2 km
• B → D: 5 km
• C → D: 8 km
Step 1: Set Up Initial Distances
• 1. Start at City A with distance 0.
• 2. Set distances to all other cities as ∞.
• | City | Distance from A | Previous City |
• |------|-----------------|---------------|
• |A |0 | None |
• |B |∞ | None |
• |C |∞ | None |
• |D |∞ | None |
Step 2: Visit the Closest City (A)
• From A, check the distance to B and C:
• A → B = 4 km
• A → C = 1 km
• Update Table:
• | City | Distance from A | Previous City |
• |------|-----------------|---------------|
• |A |0 | None |
Step 3: Visit the Next Closest City
(C)
• From C, check the distances to B, D, and E:
• • C → B = 3 km
• • C → D = 9 km
• • C → E = 11 km
• Update Table:
• | City | Distance from A | Previous City |
• |------|-----------------|---------------|
Step 4: Visit the Next Closest City
(B)
• From B, check the distance to D:
• • B → D = 8 km
• Update Table:
• | City | Distance from A | Previous City |
• |------|-----------------|---------------|
• |A |0 | None |
• |B |3 |C |
Step 5: Visit the Next Closest City
(D)
• From D, check the distance to E:
• • D → E = 10 km
• Final Table:
• | City | Distance from A | Previous City |
• |------|-----------------|---------------|
• |A |0 | None |
• |B |3 |C |
Final Shortest Path from A to E
• The shortest path from A to E is:
• A→C→B→D→E
• Total Distance = 10 km