Alogirthms/Bellman_Ford.py at master · Arko98/Alogirthms · GitHub

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
global INF
INF = 10000

def Bellman_Ford(Weight):
  '''
  Bellman Ford All-Pair shortest path Traversal Algorithm
  '''
  dist = [0]+[INF for i in range(len(Weight)-1)]
  edge_list = []
  for i in range(len(Weight)):
    for j in range(len(Weight)):
      if (Weight[i][j]!=0 or Weight[i][j]!=INF):
        edge_list.append((i,j))
  for i in range(len(Weight)):
    update = False
    for e in edge_list:
      if (dist[e[1]] > dist[e[0]]+Weight[e[0]][e[1]]):
        dist[e[1]] = dist[e[0]]+Weight[e[0]][e[1]]
        update = True
    if (update == False):
      break
    return dist

# Input Graph Adjacency Matrix
W = [[0,-1,4,INF,INF],
     [INF,0,3,2,2],
     [INF,INF,0,INF,INF],
     [INF,1,5,0,INF],
     [INF,INF,INF,-3,0]]

dist_vals = Bellman_Ford(W)
print(dist_vals)