파이썬에서 경로의 제곱 행렬

Question

단위 사이에 사각형 연결 진리 행렬이 있습니다. 그것은 어떤 유닛이 서로 연결되어 있는지 보여줍니다.
예.

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

는 다음과 같이 해석 할 수 있습니다

• 1도 2에 자체에 연결되어 있지 않은, 어느 자체에, 1에 연결되어 있지 않은 3
• 2에 연결되며, 3 2에 연결되어 1로 연결되어 3
• 3에 연결되어 있지만 찾을 싶어 할 때 그것은 자기

에 연결되어 있지 않습니다 모든 유닛에 대한 경로의 길이는, 결과는 다음과 같습니다

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

이것은 당신이 원하는 것을 할 것입니다 :

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

[1]에서

을 찾고있는 것은 "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 값) 나머지는 최소값으로 줄어 듭니다. 심각하게 cipy.sparse.csgraph.floyd_warshall