Bellman ford Algorithm

1. Bellman Ford Algorithm Taimur khan MS Scholar University of Peshawar [email protected]

2. Shortest path problem Shortest path network Directed graph Source s, Destination t cost( v-u) cost of using edge from v to u Shortest path problem Find shortest directed path from s to t Cost of path = sum of arc cost in path

3. Applications Netowrks (Routing ) Robot Navigation Urban Traffic Planning Telemarketer operator scheduling Routing of Communication messages Optimal truck routing through given traffic congestion patteren OSPF routing protocol for IP

4. Single source shortest path Given graph (directed or undirected) G = (V,E) with weight function w: E  R and a vertex s  V , find for all vertices v  V the minimum possible weight for path from s to v. There are two algorithms Dijikstra’s Algorithm Bellman Ford algorithm

5. Relaxation M aintain d[ v ] for each v Î V d[ v ] is called shortest-path weight estimate INIT( G , s ) for each v  V do d[ v ] ← ∞ π [ v ] ← NIL d[ s ] ← 0

6. Relaxation RELAX( u , v ) if d[v] > d[u]+w(u,v) then d[v] ← d[u]+w(u,v) π [v] ← u 5 2 2 9 5 7 Relax(u,v) 5 2 2 6 5 6

7. Bellman Ford Dijikstra Algorithm fails when there is negative edge Solution is Bellman Ford Algorithm which can work on negative edges

8. PsuedoCode BELMAN-FORD ( G, s ) INIT ( G, s ) for i ←1 to |V|-1 do for each edge ( u , v )  E do RELAX ( u, v ) for each edge ( u, v )  E do if d[v] > d[u]+w(u,v) then return FALSE > neg-weight cycle return TRUE

9. s a b t ∞ ∞ ∞ 1 2 3 s a b t 5 -2 4 6 -9

10. s a b t ∞ ∞ ∞ 1 5 4 ∞ 2 3 s a b t 5 -2 4 6 -9 5 4 ∞

11. s a b t ∞ ∞ ∞ 1 5 4 ∞ 2 5 3 11 3 s a b t 5 -2 4 6 -9 4 11 5

12. s a b t ∞ ∞ ∞ 1 5 4 ∞ 2 5 3 11 3 5 2 11 s a b t 5 -2 4 6 -9 2 11

13. Any Question? Thank you