100 lines
3.0 KiB
Python
100 lines
3.0 KiB
Python
import random
|
|
from floyd_warshall import floyd_warshall, reconstruct_path
|
|
|
|
def bellman(n, edges, src):
|
|
INF = float('inf')
|
|
d = [INF]*n
|
|
d[src]=0
|
|
for _ in range(n-1):
|
|
for u,v,w in edges:
|
|
if d[u]!=INF and d[u]+w < d[v]:
|
|
d[v]=d[u]+w
|
|
# negative cycle check
|
|
for u,v,w in edges:
|
|
if d[u]!=INF and d[u]+w < d[v]:
|
|
return None
|
|
return d
|
|
|
|
def test_basic():
|
|
n=4
|
|
edges=[(0,1,5),(1,2,3),(0,2,10),(2,3,1)]
|
|
dist,nxt=floyd_warshall(n,edges)
|
|
assert dist[0][3]==9
|
|
p=reconstruct_path(nxt,0,3)
|
|
assert p==[0,2,3] or p==[0,1,2,3] # 0->2->3 = 11? wait 5+3+1=9, 10+1=11. so 0,1,2,3
|
|
assert p==[0,1,2,3]
|
|
|
|
def test_unreachable():
|
|
n=3
|
|
edges=[(0,1,1)]
|
|
dist,nxt=floyd_warshall(n,edges)
|
|
assert dist[0][2]==float('inf')
|
|
assert reconstruct_path(nxt,0,2) is None
|
|
|
|
def test_negative_no_cycle():
|
|
n=3
|
|
edges=[(0,1,4),(1,2,-2),(0,2,3)]
|
|
dist,nxt=floyd_warshall(n,edges)
|
|
assert dist[0][2]==2
|
|
assert reconstruct_path(nxt,0,2)==[0,1,2]
|
|
|
|
def test_negative_cycle_raises():
|
|
n=3
|
|
edges=[(0,1,1),(1,2,-1),(2,0,-1)]
|
|
try:
|
|
floyd_warshall(n,edges)
|
|
assert False
|
|
except ValueError:
|
|
pass
|
|
|
|
def test_random_vs_bellman():
|
|
random.seed(42)
|
|
for _ in range(200):
|
|
n=random.randint(1,6)
|
|
m=random.randint(0, n*n)
|
|
edges=[]
|
|
for _ in range(m):
|
|
u=random.randrange(n); v=random.randrange(n)
|
|
w=random.randint(-3,5)
|
|
if u==v:
|
|
# allow self loops with non-negative? skip to avoid trivial
|
|
if w<0:
|
|
w=0
|
|
edges.append((u,v,w))
|
|
# ensure no negative cycles by checking bellman per source? Just run; if raises, skip compare
|
|
try:
|
|
dist,nxt=floyd_warshall(n,edges)
|
|
except ValueError:
|
|
continue
|
|
for s in range(n):
|
|
bf=bellman(n,edges,s)
|
|
if bf is None:
|
|
continue
|
|
for t in range(n):
|
|
expected=bf[t]
|
|
got=dist[s][t]
|
|
assert got==expected, (n,edges,s,t,got,expected)
|
|
# path check
|
|
if expected!=float('inf') and s!=t:
|
|
p=reconstruct_path(nxt,s,t)
|
|
assert p is not None
|
|
# verify path cost
|
|
cost=0
|
|
for i in range(len(p)-1):
|
|
ws=[ww for u,v,ww in edges if u==p[i] and v==p[i+1]]
|
|
assert ws, p
|
|
cost+=min(ws)
|
|
assert cost==expected, (p,cost,expected)
|
|
|
|
def test_self_loop_zero():
|
|
n=2
|
|
edges=[(0,0,5)]
|
|
dist,nxt=floyd_warshall(n,edges)
|
|
assert dist[0][0]==0 # self distance stays 0 (min of 0 and 5)
|
|
# actually with self loop 5, min(0,5)=0
|
|
|
|
if __name__=='__main__':
|
|
test_basic(); test_unreachable(); test_negative_no_cycle(); test_negative_cycle_raises()
|
|
test_random_vs_bellman(); test_self_loop_zero()
|
|
print("ALL OK")
|