Bellman-Ford Algorithm.pptx

Bellman ford Algorithm

1. Eastern University Presentation on Bellman-Ford Algorithm Presented TO Tanzim Tamanna Shitu Presented By Ashik Ahammed Hridoy ID: 203400003 1

2. What is Bellman-Ford? Bellman Ford algorithm helps us find the shortest path from a vertex to all other vertices of a weighted graph. It is similar to Dijkstra's algorithm but it can work with graphs in which edges can have negative weights. 2

3. Example of Bellman Ford : 3 Relaxation: If {d(u) + c(u , v) < d(u)} d(v) = d(u) + c (u , v) Iteration: (n – 1) [n : no. of vertices] (6 – 1) = 5 times A D C B E F

4. Example of Bellman Ford : 4 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F ∞ ∞ ∞ ∞ ∞ Step - 1 1 st Iteration Selected Vertices

5. Example of Bellman Ford : 5 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F A ∞ ∞ ∞ ∞ ∞ 6 4 5 ∞ ∞ Step - 2 Selected Vertices 1 st Iteration

6. Example of Bellman Ford : 6 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F A ∞ ∞ ∞ ∞ ∞ B 6 4 5 ∞ ∞ 6 4 5 5 ∞ Step - 3 Selected Vertices 1 st Iteration

7. Example of Bellman Ford : 7 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F A ∞ ∞ ∞ ∞ ∞ B 6 4 5 ∞ ∞ C 6 4 5 5 ∞ 2 4 5 5 ∞ Step - 4 Selected Vertices 1 st Iteration

8. Example of Bellman Ford : 8 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F A ∞ ∞ ∞ ∞ ∞ B 6 4 5 ∞ ∞ C 6 4 5 5 ∞ D 2 4 5 5 ∞ 2 3 5 5 4 Step - 5 Selected Vertices 1 st Iteration

9. Example of Bellman Ford : 9 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F A ∞ ∞ ∞ ∞ ∞ B 6 4 5 ∞ ∞ C 6 4 5 5 ∞ D 2 4 5 5 ∞ E 2 3 5 5 4 2 3 5 5 4 Step - 6 Selected Vertices 1 st Iteration

10. Example of Bellman Ford : 10 A D C B E F -1 5 6 4 -2 -2 3 3 -1 A B C D E F A ∞ ∞ ∞ ∞ ∞ B 6 4 5 ∞ ∞ C 6 4 5 5 ∞ D 2 4 5 5 ∞ E 2 3 5 5 4 F 2 3 5 5 4 Step - 7 Final Value Selected Vertices 1 st Iteration

11. After 4 th iteration we will get: 11 A B C D E F A 1 3 5 3 B 1 3 5 3 C 1 3 5 3 D 1 3 5 3 E 1 3 5 3 F 1 3 5 3 Final Value Selected Vertices Example of Bellman Ford :

12. Bellman Ford Using JavaScript: 12

13. Bellman Ford Using JavaScript: 13 A B C D E F A 1 3 5 3 B 1 3 5 3 C 1 3 5 3 D 1 3 5 3 E 1 3 5 3 F 1 3 5 3 Final Value

14. THANKS EVERYONE! 14