Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

FFloyd-Warshall doesn't works

In 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
    [[["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  

I wonder why B and fw are the sames since

show(B[0][1] and B[1][3])

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