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

该应用程序可能在 Risk 游戏中，您可能希望从您拥有的所有区域开始捕获属于奖金的所有区域。它将根据到达奖励中所有区域所需的回合数给出一个下限（忽略你是否能够在部队方面捕获）。在这个简单示例的上下文中：

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

Answer 1

这会做你想做的事：

在[1]:

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

输出[1]:

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

Answer 2

您要找的是“Floyd-Warshall algorithm”。

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

这是一个距离矩阵。 Floyd-Warshall 用最小距离计算一个新的距离矩阵。所以一些值将相同（例如 0 值），而其他值将减少到最小值。

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

Python 中路径的方阵长度

Square matrix length of path in Python

python

numpy

matrix