-
Notifications
You must be signed in to change notification settings - Fork 1
/
bellman_ford.py
42 lines (31 loc) · 1.06 KB
/
bellman_ford.py
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
class Graph:
def __init__(self,v):
self.v = v
self.vertices=[]
def add_edge(self,s,d,w):
self.vertices.append([s,d,w])
def print_distance(self, dist):
print("Vertex\t\tDistance")
for i in range(self.v):
print(f"{i}\t\t{dist[i]}")
def bellmanFord(self, src):
dist = [float('inf') for _ in range(self.v)]
dist[src] = 0
for _ in range(self.v-1):
for s,d,w in self.vertices:
if dist[s]!=float('inf') and dist[d]>dist[s]+w:
dist[d] = dist[s]+w
for s,d,w in self.vertices:
if dist[s]!=float('inf') and dist[d]>dist[s]+w:
print("Graph has negative cycle")
return
self.print_distance(dist)
nv = int(input("Enter no. of vertices: "))
ne = int(input("Enter no. of edges: "))
g = Graph(nv)
print("Enter source, destination and weights of edges")
for _ in range(ne):
s,d,w=map(int,input().split())
g.add_edge(s,d,w)
src = int(input("Enter source node: "))
g.bellmanFord(src)