Bellman-ford algorithm will find the shortest path to all of the vertices from the source node.
Dijkstra's shortest path algorithm can not work around graphs with negative weight. Bellman-ford can.
Time Complexity:
Generally:
which is
Worst Case: graph is a complete graph
Therefore,
Space Complexity:
Conclusion:
If we were to say the number of verticies is . At worst case,
Advantages
Disadvantages
1) Initialize dist list with length of n with
2) We will relax the graph n-1 times
3) If necessary: We will relax the graph one more time making it relaxed n times. If the values of dist for any nodes change on the nth relaxation, the graph contains negative cycle.
def bellmanFord(self, times: List[List[int]], n: int, k: int) -> int:
# Initializing dist list with float("inf")
dist = [float("inf")] * (n)
dist[k-1] = 0
# Relaxation
for _ in range(n-1):
for u,v,w in times:
# Updating shortest path to target node
if dist[u-1] != float("inf") and dist[u-1] + w < dist[v-1]:
dist[v-1] = dist[u-1] + w
# Checking if there are unreached nodes
if float("inf") in dist:
return -1
else:
return max(dist)