0%

Bellman Ford

Bellman-Ford Algorithm is slower than Dijkstra. But it can handle graph contains a negative cycle.

Time Complexity: E * V

  • E is the number of edges
  • V is the number of vertexs

Implementation

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#!/usr/local/bin/python3

import math
from typing import List
from collections import defaultdict

def bellman_ford(vertexs: int, edges: List[List[int]], origin: int, destination: int):
'''
print shortest path from origin to destination
Args:
vertexs: number of vertexs. First vertex is 0.
edges: list of (start, end, weight)
origin: -
destination: -
Raise:
ValueError: if destination is not reachable from origin
or a negative cycle is found
'''
# prepare data
dist, prev = defaultdict(lambda: math.inf), [None] * vertexs
dist[origin] = 0
# relex edges
for _ in range(vertexs):
upd = 0
for u, v, w in edges:
# find a shorter path
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
upd += 1
if upd == 0: # quick exit
break
# check for negative cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError('Negative cycle is found')
# build path
path, cur = [], destination
while cur != origin and prev[cur] is not None:
path.append(cur)
cur = prev[cur]
if cur != origin:
raise ValueError(f'{destination} is not reachable from {origin}')
path = [origin] + path[::-1]
print('->'.join([str(vertex) for vertex in path]))

# regular graph with negative weight
bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, -1]], 0, 4)
# negative cycle
bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, -1], [2, 4, 10], [3, 4, -1], [4, 1, -1]], 0, 4)
1
2
3
4

<!-- more -->

## Test Case

regular graph with negative weight

+-+                  +-+

+-2—–>+1| |4+<–+
| +++ +++ |
+++ | +-+ ^ |
|0| +–3—–>+3+—(-1)-+ |
+++ +-+ |
| +-+ |
+–5—->+2+—————-10——+
+-+

negative cycle

+-+                  +-+

+-2—–>+1+<——-(-1)——+4+<–+
| +++ +++ |
+++ | +-+ ^ |
|0| +-(-1)—>+3+—(-1)-+ |
+++ +-+ |
| +-+ |
+–5—->+2+—————-10——+
+-+

```