bellman ford python

1class Graph:
2
3
4
5    def __init__(self, vertices):
6
7        self.M = vertices   # Total number of vertices in the graph
8
9        self.graph = []     # Array of edges
10
11
12
13    # Add edges
14
15    def add_edge(self, a, b, c):
16
17        self.graph.append([a, b, c])
18
19
20
21    # Print the solution
22
23    def print_solution(self, distance):
24
25        print("Vertex Distance from Source")
26
27        for k in range(self.M):
28
29            print("{0}\t\t{1}".format(k, distance[k]))
30
31
32
33    def bellman_ford(self, src):
34
35
36
37        distance = [float("Inf")] * self.M
38
39        distance[src] = 0
40
41
42
43        for _ in range(self.M - 1):
44
45            for a, b, c in self.graph:
46
47                if distance[a] != float("Inf") and distance[a] + c < distance[b]:
48
49                    distance[b] = distance[a] + c
50
51
52
53        for a, b, c in self.graph:
54
55            if distance[a] != float("Inf") and distance[a] + c < distance[b]:
56
57                print("Graph contains negative weight cycle")
58
59                return
60
61
62
63        self.print_solution(distance)
64
65
66
67g = Graph(5)
68
69g.add_edge(0, 1, 2)
70
71g.add_edge(0, 2, 4)
72
73g.add_edge(1, 3, 2)
74
75g.add_edge(2, 4, 3)
76
77g.add_edge(2, 3, 4)
78
79g.add_edge(4, 3, -5)
80
81
82
83g.bellman_ford(0)
84
85