# Bellman-Ford Algorithm

choikh0423·2022년 5월 15일
0

목록 보기
1/2

## What is Bellman-Ford Algorithm?

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.

## Analysis

Time Complexity:
Generally:
$O(|E|(|V|-1))$ which is $O(|E||V|)$

Worst Case: graph is a complete graph
$|E| = {n(n-1) \over 2} = {n^2-n \over 2} {\displaystyle \approx } O(n^2)$
Therefore,
$O(|E||V|)=O(|V^2||V|){\displaystyle \approx }O(|V^3|)$

Space Complexity:
$O(|V|)$

Conclusion:
If we were to say the number of verticies is $n$. At worst case,

• Time Complexity: $O(n^3)$
• Space Complexity: $O(n)$

## Evaluation

• Can be applied to graphs w/ negative weight

• As Dijkstra's is greedy and Bellman-Ford is dynamic, it is slower than Dijkstra's.
• Does not work if there is a negative cycle in the graph. We can find out if there is a negative cycle, but not work through it.

## Implementation

1) Initialize dist list with length of n with $float("inf")$
2) We will relax the graph n-1 times

• Go through each edge to check if $dist[v] > dist[u] + w$ where $u$ will be the source node and $v$ will be the target node of that edge.
• If $dist[v] > dist[u] + w$ update $dist[v] = dist[u] + w$

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.

## Code

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)