In [1]:

    

import numpy as np
from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
from scipy.sparse import csr_matrix


    

In [2]:

    

n = 100
c = n * 50
np.random.seed(1)
d = np.random.randint(0, n, c)
i = np.random.randint(0, n, c)
j = np.random.randint(0, n, c)


    

In [3]:

    

csr = csr_matrix((d, (i, j)), shape=(n, n))
a = csr.toarray()


    

In [4]:

    

print(a.shape)


    

    




(100, 100)

In [5]:

    

print((a > 0).sum())


    

    




3945

In [6]:

    

%%timeit
shortest_path(a)


    

    




2.59 ms ± 132 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [7]:

    

%%timeit
shortest_path(csr)


    

    




1.73 ms ± 18.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [8]:

    

%%timeit
shortest_path(a, method='FW')


    

    




2.57 ms ± 173 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [9]:

    

%%timeit
shortest_path(csr, method='FW')


    

    




1.73 ms ± 21.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [10]:

    

%%timeit
floyd_warshall(a)


    

    




1.92 ms ± 30.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [11]:

    

%%timeit
floyd_warshall(csr)


    

    




1.61 ms ± 17 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [12]:

    

%%timeit
dijkstra(a, indices=0)


    

    




762 µs ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [13]:

    

%%timeit
dijkstra(csr, indices=0)


    

    




164 µs ± 4.85 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [14]:

    

a_n = a.copy()
a_n[0, 1] = -10
csr_n = csr_matrix(a_n)


    

In [15]:

    

%%timeit
johnson(csr_n)


    

    




6.53 ms ± 72.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [16]:

    

%%timeit
bellman_ford(csr_n)


    

    




79.8 ms ± 354 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [17]:

    

%%timeit
floyd_warshall(csr_n)


    

    




1.57 ms ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [18]:

    

%%timeit
johnson(csr_n, indices=0)


    

    




952 µs ± 11.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)