# FFloyd-Warshall doesn't works

In https://stackoverflow.com/questions/55518900/seeking-pseudo-code-for-calculating-the-smith-and-schwartz-set I have found the following application of Ffloyd-Warshall algorithm :

I guess python is close enough to pseudocode.

Let's say we have n candidates numbered from 0 to n - 1.

First you can compute a matrix beats[i][j] equal to True if candidate i beats candidate j and False otherwise.

Now compute the transitive closure of the matrix using the Floyd-Warshall algorithm:

for k in range(n):

for i in range(n):

for j in range(n):

beats[i][j] = beats[i][j] or (beats[i][k] and beats[k][j])


There is my code for n=3

B =[["False","True","True","False"],["False","False","True","True"],["False","False","False","False"],["True","False","True","False"]]
def floydWarshall1(graph,n=3): #n=no. of vertex
beats=graph
[[["True"  if (beats[i][j]=="True" or (beats[i][k] and beats[k][j])=="True") else "False" for j in range(n)] for i in range(n)]for k in range(n)]
return beats
fw=floydWarshall1(B,3)
show(B)
show(fw)


I wonder why B and fw are the sames since

show(B)
show(B and B)


returns False for the first and True for the second. Certainly an error of mine.

edit retag close merge delete

Sort by » oldest newest most voted

This :

def FW(B): return [[bool(v) for v in u] for u in matrix(B)+(matrix(B).transpose()*matrix(B))]
B =[[False,True,True,False],[False,False,True,True],[False,False,False,False],[True,False,True,False]]
fw=FW(B)
print(matrix(B))
print("-"*9)
print(matrix(fw))


should do...

more

I have tried the proposed solution but if I understand the process, there is a strange line.

[1 1 1 0]
[0 1 1 1]
[1 1 1 1]
[1 0 1 1]


If 1 there is a path from i to j . But there is no path from 2 to 2 so fw should be 0 not 1