zelenov aleksey - 1 year ago 58

Python Question

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 Source

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

.