# Retrieving distances from shortest_distance

Hi and happy new year graph coders!

The shortest_distance function implements the Floyd's algorithm. I am
carefully following the example provided by the docs
<https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.shortest_distance&gt;
but the function doesn't return the expected result.

Here is my trivial try:

# -------------------
import graph_tool as gt
from graph_tool.topology import shortest_distance
import numpy as np

wedges=[(2, 0, 6.0), (0, 3, 7.0), (0, 2, 2.0)]
print(wedges)

# Définition of the weighted graph
g= gt.Graph(directed=True)
weight = g.new_edge_property("double")

# Floyd call
dist=shortest_distance(g, dense=True)

# I'm expecting the vector distance from vertex 2
print(dist[g.vertex(2)])

# -------------------

outputting :

# -------------------
[(2, 0, 6.0), (0, 3, 7.0), (0, 2, 2.0)]
array([ 1, 2147483647, 0, 2], dtype=int32)
# -------------------

This not the correct distance vector from the 2-indexed node nor the correct
predecessor vector. And I don't understand why I get an int32 vector since
the weights have double type.

Can somebody please correct my code in order to get the correct distances?

Pascal

You need to actually pass the weights to the function:

dist = shortest_distance(g, weights=weight, dense=True)

Best,
Tiago

I was benchmarking some Floyd APSP source-code.

Some results (in seconds) on a random graph with 800 nodes and abouts 10000
edges:

Networkx : 82.66
Python with array : 38.97
Numpy from Networkx : 1.67 (no predecessors calculation)
graph-tool : 0.91
Scipy (Cython) : 0.50
Pure C code : 0.35

Below the code I used for Graph-tool test:

# -------------------
import graph_tool as gt
from graph_tool.topology import shortest_distance
import numpy as np
from random import randrange

def random_edges(n, density, max_weight=100):
M=n*(n-1)//2
m=int(density*M)
edges=set()
wedges=[]
while len(edges)<m:
L=(randrange(n),randrange(n))
if L!=L and L not in edges:
w=float(randrange(max_weight))
wedges.append(L+(w,))
return wedges

n=800
density=0.33

wedges=random_edges(n, density)

start=clock()

g= gt.Graph(directed=True)
weight = g.new_edge_property("double")