Floyd-Warshall을 경로 길이로 제한합니다. k

Question

Floyd-Warshall algorithm을 구현하고 있습니다.

약 50 개의 노드가있는 전체 그래프가 있습니다. 모든 노드 사이의 최대 경로를 찾고 싶습니다. 알고리즘이 반환하는 경로는 임의의 길이 일 수 있습니다. 1 < x < 50이 길이는 최대 3-4 에지 길이가되어야합니다. 어떻게 알고리즘을 변경할 수 있습니까?

Answer 1

하자가 에서 IJ 행 중량 될 w(i,j). 그럼 당신은 4 가장자리까지 사용하고 유사 w3에 대한 최종 각 쌍에 대해 처음부터 거리를 포함 끝에

def shortest(w1, w2): 
    w12 = a new V x V matrix 
    for i in V: 
    for j in V: 
     w12(i, j) = w1(i, j) 
     for k in V: 
     if w12(i, j) > w1(i, k) + w2(k, j): 
      w12(i, j) = w1(i, k) + w2(k, j) 
    return w12 

w2 = shortest(w, w) 
w3 = shortest(w2, w) 
w4 = shortest(w2, w2) 

, w4을 계산할 수 있습니다. 먼저 w3을 계산하지 않고 w4을 계산할 수 있습니다. 이 2 진법의 형태, 즉 모든 2 승법 행렬을 계산하고 결합하면, O (n3 logk)의 시간 복잡도, 즉 최대 경로 길이에서 단지 logarithmical을 달성 할 수있다.

위키 피 디아에는 위에 요약 된 알고리즘에 대한 짧은 기사가 있습니다. 제목은 "min-plus matrix multiplication"입니다. 아마도이 용어와 관련된 일부 참조 또는 "거리 제품"이라는 대체 용어는 가능한 구현에 대한 추가 정보로 이어질 것입니다. 예를 들어, "faster funny matrix multiplication for the all-pairs shortest paths problem"이라는 종이가 있는데,이 문제를 논의하고 알고리즘을 제시하며 SIMD 구현에 대해 생각합니다.