1 INF = 10000
2
3
4 def getGraph() -> tuple:
5 G = [
6 #a b c d e
7 [0, 4, 5, 0, 0], # a
8 [0, 0, 0, 8, 0], # b
9 [0, 0, 0, 0, -7], # c
10 [0, 0, 0, 0, -6], # d
11 [0, 2, 0, 0, 0] # e
12 ]
13 return G, 5
14
15
16 def bellman(G: list, n: int, s: int):
17 dis = [INF for _ in range(n)]
18 dis[s] = 0 # start from a
19 for _ in range(n - 1):
20 for i in range(n):
21 for j in range(n):
22 if G[i][j] != 0 and dis[j] > dis[i] + G[i][j]:
23 dis[j] = dis[i] + G[i][j]
24 return dis
25
26
27 if __name__ == '__main__':
28 G, n = getGraph()
29 dis = bellman(G, n, 0)
30 print(dis)