Johnson’s Algorithm – Worked Example PDF

Graph:

A→B:3

A→C:8

B→C:-4

B→D:1

C→E:5

D→C:2

D→E:4

E→B:-1

Steps Included:

1. Adding vertex q

2. Bellman–Ford computation of h-values

3. Edge reweighting

4. Dijkstra from each vertex

5. Converting back to original distances

6. Final APSP matrix

Final APSP Matrix (Original Weights):

ABCDE

A → [ 0, 3, -1, 4, 4 ]

B → [ ∞, 0, -4, 1, 1 ]

C → [ ∞, 4, 0, 5, 5 ]

D → [ ∞, 3, 2, 0, 4 ]

E → [ ∞, -1, -5, 0, 0 ]