Skip to content

Latest commit

 

History

History
15 lines (9 loc) · 1.14 KB

28. Bellman Ford.md

File metadata and controls

15 lines (9 loc) · 1.14 KB

Bellman Ford Algorithm

Bellman Ford is used to find the shortest path from source to all other nodes Dijkstra fails in case of negative edge, which was solved by bellman ford Dijkstra is also used to find the shortest path between source to destination but, dijkstra does not work in the case of negative edge. Because in the case of dijkstra if you'll calculate shortest distance between two nodes, then each time they will give different weight, and it will stuck in the infinite loop. so this problem was solved by Bellman Ford Algorithm

Screenshot from 2021-10-03 20-00-04

  • Bellman Ford will not give answer in the case of negative weight cycles, because each time you will iterate, it will give lesser answer, But bellman will tell you whether there is a negative weight cycle or not.

Screenshot from 2021-10-03 20-05-00

  • It will work for both undirected as well as directed graph

Time Complexity and Space complexity