-
Notifications
You must be signed in to change notification settings - Fork 1
/
Bellman-Ford.py
81 lines (66 loc) · 2.51 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import numpy as np
import scipy as sp
import sys
def BellmanFord(ist,isp,wei):
# B-F algorithm is slower than the Diskstra's algorithm since it gives considerations to the graphs with negative
# weights, the running time difference of both algorithms running the Rome traffic problem is: 0.00196814537048s for
# Dijkstra and 0.0779738426208s for Bellman-Ford. The time difference is significant and will be much greater when
# dealing with more data, but B-F algorithm can be applied to problems which Dijkstra is not applicable, see in
# project 2
#----------------------------------
# ist: index of starting node
# isp: index of stopping node
# wei: adjacency matrix (V x V)
#
# shpath: shortest path
#----------------------------------
V = wei.shape[1]
# step 1: initialization
Inf = sys.maxint
d = np.ones((V),float)*np.inf
p = np.zeros((V),int)*Inf
d[ist] = 0
# step 2: iterative relaxation
for i in range(0,V-1):
for u in range(0,V):
for v in range(0,V):
w = wei[u,v]
if (w != 0):
if (d[u]+w < d[v]):
d[v] = d[u] + w
p[v] = u
# step 3: check for negative-weight cycles
for u in range(0,V):
for v in range(0,V):
w = wei[u,v]
if (w != 0):
if (d[u]+w < d[v]):
print('graph contains a negative-weight cycle')
# step 4: determine the shortest path
shpath = [isp]
while p[isp] != ist:
shpath.append(p[isp])
isp = p[isp]
shpath.append(ist)
return shpath[::-1]
if __name__ == '__main__':
# indices of starting and stopping vertices
ist = 4
isp = 3
# randomly generated adjacency matrix
#N = 10
#ma = np.around(np.random.uniform(0,1.2,(N,N)))
#wei = ma*np.random.uniform(0,30,(N,N))
#wei = np.tril(wei,-1) + np.triu(wei,1)
# adjacency matrix
wei = np.array([[ 0, 20, 0, 80, 0, 0, 90, 0],
[ 0, 0, 0, 0, 0, 10, 0, 0],
[ 0, 0, 0, 10, 0, 50, 0, 20],
[ 0, 0, 10, 0, 0, 0, 20, 0],
[ 0, 50, 0, 0, 0, 0, 30, 0],
[ 0, 0, 10, 40, 0, 0, 0, 0],
[20, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0]])
# minimal distance path
shpath = BellmanFord(ist,isp,wei)
print ist,' -> ',isp,' is ',shpath