Bellman-Ford algorithm for Shortest Path Algorithm
Bellman-Ford is a single source shortest path algorithm that determines the shortest path between a given source vertex and every other vertex in a graph. This algorithm can be used on both weighted and unweighted graphs.
A Bellman-Ford algorithm is also guaranteed to find the shortest path in a graph, similar to Dijkstra’s algorithm. Although Bellman-Ford is slower than Dijkstra’s algorithm, it is capable of handling graphs with negative edge weights, which makes it more versatile. The shortest path cannot be found if there exists a negative cycle in the graph. If we continue to go around the negative cycle an infinite number of times, then the cost of the path will continue to decrease (even though the length of the path is increasing). As a result, Bellman-Ford is also capable of detecting negative cycles, which is an important feature.
Algorithm:
- Initialize distance array dist[] for each vertex ‘v‘ as dist[v] = INFINITY.
- Assume any vertex (let’s say ‘0’) as source and assign dist = 0.
- Relax all the edges(u,v,weight) N-1 times as per the below condition:
- dist[v] = minimum(dist[v], distance[u] + weight)
Complexity Analysis:
- Time Complexity: O(V*E), where V is the number of vertices and E is the number of edges.
- Auxiliary Space: O(V)
Shortest Path Algorithm Tutorial with Problems
In this article, we are going to cover all the commonly used shortest path algorithm while studying Data Structures and Algorithm. These algorithms have various pros and cons over each other depending on the use case of the problem. Also we will analyze these algorithms based on the time and space complexities which are frequently asked in coding interviews.
Table of Content
- Types of Shortest Path Algorithms
- 1. Shortest Path Algorithm using Depth-First Search(DFS
- 2. Breadth-First Search (BFS) for Shortest Path Algorithm
- 3. Multi-Source BFS for Shortest Path Algorithm
- 4. Dijkstra’s Algorithm for Shortest Path Algorithm
- 5. Bellman-Ford algorithm for Shortest Path Algorithm
- 6. TopoLogical Sort
- 7. Floyd-Warshall algorithm for Shortest Path Algorithm
- 8. A* Search Algorithm for Shortest Path Algorithm
- 9. Johnson’s Algorithm for Shortest Path Algorithm
- Complexity Analysis For All Shortest Path Algorithms
- Real World Applications of Shortest Path Algorithms