Voici
Votre nouvel assistant de présentation.
Affinez, améliorez et adaptez votre contenu, trouvez des images pertinentes et éditez des visuels plus rapidement que jamais.
Recherches à la une
Student : Kenan Huseynov
Subject : Data Structures and Algorithms
*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.
*İt’s more time consuming
*Dynamic programming approach is taken to implement the algorithm
Why would one ever have edges with negative weights in real life?
*Negative weight edges might seem useless at first but they can explain a lot of phenomena like cashflow, the heat released/absorbed in a chemical reaction, etc.
Why do we need to be careful with negative weights?
Negative weight edges can create negative weight cycles i.e. a cycle that will reduce the total path distance by coming back to the same point.
Negative weight cycles can give an incorrect result when trying to find out the shortest path.
How Bellman Ford's algorithm works
*Bellman Ford algorithm works by overestimating the length of the path from the starting vertex to all other vertices. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated paths.
By doing this repeatedly for all vertices, we can guarantee that the result is optimized.