def floyd_warshall_predecessor_and_distance(G, weight='weight'):
 from collections import defaultdict
 dist = defaultdict((lambda : defaultdict((lambda : float('inf')))))
 for u in G:
  dist[u][u] = 0
 pred = defaultdict(dict)
 undirected = (not G.is_directed())
 for (u, v, d) in G.edges(data=True):
  e_weight = d.get(weight, 1.0)
  dist[u][v] = min(e_weight, dist[u][v])
  pred[u][v] = u
  if undirected:
   dist[v][u] = min(e_weight, dist[v][u])
   pred[v][u] = v
 for w in G:
  for u in G:
   for v in G:
    if (dist[u][v] > (dist[u][w] + dist[w][v])):
     dist[u][v] = (dist[u][w] + dist[w][v])
     pred[u][v] = pred[w][v]
 return (dict(pred), dict(dist))

def floyd_warshall_predecessor_and_distance ( G , weight = 'weight' ) : from collections import defaultdict dist = defaultdict ( ( lambda : defaultdict ( ( lambda : float ( 'inf' ) ) ) ) ) for u in G : dist [ u ] [ u ] = 0 pred = defaultdict ( dict ) undirected = ( not G . is_directed ( ) ) for ( u , v , d ) in G . edges ( data = True ) : e_weight = d . get ( weight , 1.0 ) dist [ u ] [ v ] = min ( e_weight , dist [ u ] [ v ] ) pred [ u ] [ v ] = u if undirected : dist [ v ] [ u ] = min ( e_weight , dist [ v ] [ u ] ) pred [ v ] [ u ] = v for w in G : for u in G : for v in G : if ( dist [ u ] [ v ] > ( dist [ u ] [ w ] + dist [ w ] [ v ] ) ) : dist [ u ] [ v ] = ( dist [ u ] [ w ] + dist [ w ] [ v ] ) pred [ u ] [ v ] = pred [ w ] [ v ] return ( dict ( pred ) , dict ( dist ) )
find all-pairs shortest path lengths using floyds algorithm .