python - 寻找断开边缘的最小路径的快速算法

Question

嗨，我有一个有向图的邻接矩阵:

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

这里我们有一些没有直接连接的边，我想用边之间的最小路径替换零。预期输出:

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

有没有快速的Python解决方案？(注意图是有向的)

Answer 1

numpy和 networkx让这变得非常简单。

首先，定义邻接矩阵。正如 Kenny Ostrom 所指出的，对角线通常为 0(稍后会详细介绍):

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]])

现在找到最短距离:

dists = nx.floyd_warshall_numpy(nx.from_numpy_matrix(am, create_using=nx.DiGraph()))

(非常感谢 @curious_cat 指出需要 create_using=nx.DiGraph()，顺便说一句。)

最后，您可以用您找到的距离替换 0 条目:

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

如果您希望对角线是其他东西(我必须说，这对我来说没有什么意义)，您可以使用 np.fill_diagonal .