Ask Your Question

# 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[0][3])
show(B[0][1] and B[1][3])


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

edit retag close merge delete

## 1 Answer

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

## Comments

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[2][2] should be 0 not 1

( 2021-03-13 18:29:57 +0100 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2021-03-12 10:46:11 +0100

Seen: 64 times

Last updated: Mar 12 '21