zelenov aleksey zelenov aleksey - 1 month ago 5
Python Question

Fast algorithm to find minimum path for disconnected edges

Hi I have adjacency matrix for a directed graph:

∞ 12 0 28 0 0 0
12 ∞ 10 43 0 0 0
0 10 ∞ 0 10 0 0
28 43 17 ∞ 0 0 0
0 31 10 0 ∞ 8 0
0 0 0 0 14 ∞ 6
0 0 0 0 0 6 ∞


here we have some edges that are not connected directly and i want to replace zeros with minimum path between edges. The expected output:

∞ 12 22 28 32 40 46
12 ∞ 10 40 20 28 34
22 10 ∞ 50 10 18 24
28 27 17 ∞ 27 35 41
32 20 10 60 ∞ 8 14
46 34 24 74 14 ∞ 6
52 40 30 80 20 6 ∞


is there any fast python solution for that?(note that graph is directed)

Answer

numpy and networkx make this very simple.

First, define the adjacency matrix. As Kenny Ostrom noted, the diagonal is conventionally 0 (more on that later):

import numpy as np
import networkx as nx

am = np.array([[0,   12,  0,   28,  0,   0,   0],
    [12,  0,   10,  43,  0,   0,   0],
    [0,  10,  0,   0,   10,  0,   0],
    [28,  43,  17,  0,   0,   0,   0],
    [0,   31,  10,  0,   0,   8,   0],
    [0,   0,   0,   0,   14,  0,   6],
    [0,   0,   0,   0,   0,   6,   0]])

Now find the shortest distances:

dists = nx.floyd_warshall_numpy(nx.from_numpy_matrix(am))

Finally, you can replace the 0 entries by the distances you found:

>>> np.where(am, am, dists)
array([[  0.,  12.,  22.,  28.,  32.,  46.,  52.],
       [ 12.,   0.,  10.,  43.,  20.,  34.,  40.],
       [ 22.,  10.,   0.,  17.,  10.,  24.,  30.],
       [ 28.,  43.,  17.,   0.,  27.,  41.,  47.],
       [ 32.,  31.,  10.,  27.,   0.,   8.,  20.],
       [ 46.,  34.,  24.,  41.,  14.,   0.,   6.],
       [ 52.,  40.,  30.,  47.,  20.,   6.,   0.]])

If you want the diagonal to be something else (which makes less sense to me, I must say), you can use np.fill_diagonal.

Comments