Floyd Warshall, how it's works?

[-ordi-]

from copy import deepcopy

sis = file("teedtest.01.sis", "r")
val = file("rp.val", "wt")

N, K = map(int, sis.readline().strip().split()) 

alist = []
for i in range(0, K):
  t = []
  for i in range(0, K):
    t.append(0)
  alist.append(t)
  
for i in range(K):
  a, b, c = map(int, sis.readline().strip().split())
  alist[a][b] = alist[b][a] = c

D = deepcopy(alist)
print D
for k in range(0, K): 
  for u in range(0, K): 
    for v in range(0, K): 
      #print k, u, v
      D[u][v] = min(D[u][v], (D[u][k] + D[k][v]))
      
for i in range(K):
  print D[i]

10 15
1 3 3
1 4 3
2 4 3
2 5 3
3 5 3
6 7 2
7 8 2
8 9 2
9 10 2
10 6 2
1 6 1
2 7 2
3 8 3
4 9 4
5 10 5

How to calculate all paths in every town to other?

Current output, it's not correct?

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[Gribouillis]

from copy import deepcopy

sis = file("teedtest.01.sis", "r")
val = file("rp.val", "wt")

N, K = map(int, sis.readline().strip().split()) 

alist = []
for i in range(0, K):
  t = []
  for i in range(0, K):
    t.append(0)
  alist.append(t)
  
for i in range(K):
  a, b, c = map(int, sis.readline().strip().split())
  alist[a][b] = alist[b][a] = c

D = deepcopy(alist)
print D
for k in range(0, K): 
  for u in range(0, K): 
    for v in range(0, K): 
      #print k, u, v
      D[u][v] = min(D[u][v], (D[u][k] + D[k][v]))
      
for i in range(K):
  print D[i]

10 15
1 3 3
1 4 3
2 4 3
2 5 3
3 5 3
6 7 2
7 8 2
8 9 2
9 10 2
10 6 2
1 6 1
2 7 2
3 8 3
4 9 4
5 10 5

How to calculate all paths in every town to other?

Current output, it's not correct?

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

The undefined values must be infinite. You should take all the coefficients initially equal to sys.maxint (or sys.maxsize in python 3).

[Gribouillis]

You can also work with floating point numbers and use float("inf") for the infinite value.

[-ordi-]

You can also work with floating point numbers and use float("inf") for the infinite value.

Thanks, it's works! and system.maxint seems too!

[richieking]

info ;)

sys.maxsize also exist in py2.6

[TrustyTony]

Also N*K as initial value worked in my own distance algorithm.