-5

I am not sure how to implement Floyd's algorithm in the following program. It must print a 5x5 array that represents this graph on page 466 and include a counter which is used to print the total number of comparisons when the algorithm is executed - each execution of the "if" structure counts as one comparison.

Does anyone know how to even start this program? I am not sure how to begin.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
user2548833
  • 383
  • 1
  • 4
  • 7
  • 8
    There's a very clear description of the algorithm in pseudocode on the page you linked to. That seems like a good place to start to me. – ali_m Jul 19 '13 at 10:58
  • @ali_m is right - The pseudocode you linked to is almost Python! With a couple of syntactical replacements you can convert it to valid Python code. – jmetz Jul 19 '13 at 11:04
  • 2
    http://docs.python.org/2/tutorial/ – pcalcao Jul 19 '13 at 11:05

2 Answers2

3

The following is purely a transcription of the pseudocode you linked. I changed almost nothing.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if A[i][k]+A[k][j]<A[i][j]:
                A[i][j]=A[i][k]+A[k][j]
xjcl
  • 12,848
  • 6
  • 67
  • 89
5xum
  • 5,250
  • 8
  • 36
  • 56
  • wouldn't this program have to take a lis though? i know this program is the outline of the main program but i cannot figure out how to take a list of inputs from user which includes infinity (500) – user2548833 Jul 19 '13 at 12:33
  • Either set A[i][j]=0 if vertices are not connected (and apropriatelly change the if statement or set A[i][j] to float('inf'). Oh, and of course, google is your friend. Try googling a question about python's infinity rather than asking it outright. The first google hit is http://stackoverflow.com/questions/1628026/python-infinity-any-caveats – 5xum Jul 19 '13 at 14:45
2

Translated from the page you linked to, 

k=0
while (k <= n-1):
    i=0
    while (i<=n-1):
        j=0
        while(j<=n-1):
            if(A[i,k] + A[k,j] < A[i,j]):
                A[i,j] = A[i,k] + A[k,j]
            j += 1
        i += 1
    k += 1

NB This is the exact translation to Python. Better, more Pythonic code is also possible - see, e.g. 5xum's answer which uses the range function instead of manually incrementing the loop counters.

Also A here would be a 2d matrix (e.g. a numpy ndarray). See more information about numpy here

jmetz
  • 12,144
  • 3
  • 30
  • 41
  • wouldn't this program have to take a lis though? i know this program is the outline of the main program but i cannot figure out how to take a list of inputs from user which includes infinity (500 – user2548833 Jul 19 '13 at 12:46