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)

`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`.