Python中路径的平方矩阵长度

Question

我有一个单位之间的平方连接真相矩阵。它显示了哪些单元相互连接。

例如。

[[False, False, True], # 1
 [False, False, True], # 2
 [True, True, False]]  # 3

可解释为：

• 1不是连接到自身，也不是连接到2，而是连接到3。
• 2不是连接到1，也不是连接到自身，而是连接到3。
• 3与1相连，3与2相连，但与自我无关。

当我想找到所有单元的路径长度时，结果是：

distances = [[0, 2, 1], 
             [2, 0, 1],
             [1, 1, 0]]

我不知道这是因为缺乏算法技巧.

请注意，我知道最短路径评估，但是我需要这样的结构，因为这样就可以很容易地进行进一步的操作。

例如，稍后我可能会说，我想知道最短距离的最长距离，从单元5,7,10到单元15,16,17。

np.max(np.min(distances[np.array([5,6,7])][:, np.array([15,16,17])], 1))

应用程序可能处于风险游戏中，您可能希望从所有拥有的区域开始捕获属于奖金的所有区域。它将在到达奖金中的所有区域所需的旋转次数方面给出一个下限(忽略您是否能够从部队的角度来捕获)。在这个简单的例子中：

froms = np.array([1,2])
tos = np.array([0,1])
np.max(np.min(distances[froms][:, tos], 1))
1

Answer 1

这能做你想做的事：

In1

scipy.sparse.csgraph.floyd_warshall(np.matrix(
    [[False, False, True],
     [False, False, True],
     [True, True, False]]
).astype(int))

Out1

array([[ 0.,  2.,  1.],
       [ 2.,  0.,  1.],
       [ 1.,  1.,  0.]])

Answer 2

你要找的是"Floyd-Warshall算法“。

def floyd_warshall(W):
    n = len(W)
    D = {x: None for x in range(n)}
    D[0] = W
    for k in range(1, n+1):
        D[k] = list(D[k-1])
        for i in range(n):
            for j in range(n):
                D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k-1] + D[k-1][k-1][j])
    return D[n]


if __name__ == '__main__':
    INF = float('inf')
    W = [[0, 1, INF, INF],
         [INF, 0, 3, 1],
         [INF, INF, 0, 8],
         [INF, 2, INF, 0]]
    print(floyd_warshall(W))

对于你的情况，矩阵应该是

    W = [[0, INF, 1],
         [INF, 0, 1],
         [1, 1, 0]]

这是一个距离矩阵。用最小距离计算一个新的距离矩阵。因此，一些值将是相同的(例如，0值)，而其他值将减少到最小数目。

似乎还有一个SciPy实现：cipy.sparse.csgraph.floyd_warshall