Bellman-Ford from Source 3 on Graph with 5 Nodes (Undirected weighted)

Adjacency matrix (symmetric): edges weights:
1-2:1, 1-4:1, 1-5:4, 1-3:8, 2-4:4, 2-3:12, 2-5:9, 3-4:7, 3-5:3, 4-5:2

Treat undirected as two directed edges.

Initialization

dist[3]=0, others ∞.
dist = [∞,∞,0,∞,∞] indexed 1..5.

Relax edges $V-1=4$ times (order 1→5 edges):

We can simulate quickly (using undirected edges both directions).

Iter1:

• From 3: to1 via8 → dist1=8, to2 via12→12, to4 via7→7, to5 via3→3
• From1 (now8): 1-2 (1): 8+1=9<12 → dist2=9; 1-4(1):8+1=9>7 no; 1-5(4):8+4=12>3 no
• From2(9): 2-4(4):9+4=13>7; 2-5(9):18>3
• From4(7): 4-5(2):7+2=9>3
• From5(3): 5-1(4):7<8 → dist1=7; 5-4(2):5<7 → dist4=5; 5-2(9):12>9? 3+9=12>9 no ; 5-3 done
  After iter1: dist=[7,9,0,5,3]

Iter2:

• Check all edges: 1-2:7+1=8<9 → dist2=8; 1-4:7+1=8>5; 1-3:7+8=15>0; 2-4:8+4=12>5; 3-4:0+7=7>5; 4-5:5+2=7>3; 1-5:7+4=11>3; etc. Improvement dist2 to8.
• After iter2: [7,8,0,5,3]

Iter3:

• 2-1:8+1=9>7; 4-1:5+1=6<7 → dist1=6! ; Then 1-2 again 6+1=7<8 → dist2=7 ; Then 1-3 14>0 ; Now stable.
  After iter3: dist=[6,7,0,5,3] ?? Check 4-5:5+2=7>3, 5-1:3+4=7>6, 5-4:3+2=5 equal, 2-3:7+12=19>0, 4-3:5+7=12>0. So dist=[6,7,0,5,3]

Iter4: No change → converged.

Final distances from 3:

• dist[1]=6 via 3-5(3)+5-4(2)+4-1(1)=3+2+1=6 (path 3-5-4-1)
• dist[2]=7 via 3-5-4-1-2 =3+2+1+1=7 or 3-5-4-2? 3+2+4=9 longer, so 7 is min
• dist[3]=0
• dist[4]=5 via 3-5-4 (3+2)
• dist[5]=3 direct

Check alternative 3-1 direct 8 >6, so indirect via 5-4 shorter (graph has small edges).

No negative edges → Vth iteration detects no negative cycle (no relaxation).

Time Complexity of Bellman-Ford

$O(VE)$; with adjacency matrix $E=\Theta(V^2)$ → $O(V^3)$; with list $E$ → $O(VE)$. Space $O(V)$. Here $V=5$, $E=10$ undirected (20 directed) → ~80 relaxations.