대칭 인접 행렬에 대해 Floyd-Warshall 최적화

Question

대칭 인접 행렬이 보장된다면 Floyd-Warshall의 런타임 상수를 낮추는 최적화가 있습니까?

Answer 1

내가 생각 해낸 생각했다.

플로이드 - 바르샬의 증명에 의존하기 때문에 정확한 정확성은 입증하기가 어렵습니다. 여기에 꽤 좋은 증거가 주어집니다. Floyd-Warshall proof

입력 행렬은 symmetric입니다. 이제 나머지 증명은 두 개의 내부 루프에서 계산 순서가 중요하지 않으며 그래프 이 각 단계마다 대칭 인 인 것을 보여주기 위해 수정 된 Floyd-Warshall의 증명을 사용합니다. 두 조건이 모두 참이라면 두 알고리즘 모두 똑같은 일을합니다.

는 이제 i에서 j의 경로에 중간 정점으로 설정 {0, ..., k}에서만 정점을 사용하여 j에 i의 거리로 dist[i][j][k]을 정의 할 수 있습니다.

dist[i][j][k-1]은 엣지의 무게로서 i에서 j까지로 정의된다. 이 가중치 사이에 가장자리가 없으면 무한대로 간주됩니다.

위에 링크 증명에 사용하기 동일한 로직을 사용하여 (dist[k][i][k] 비슷하게 등) dist[i][k][k] 계산 지금

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]) 

:

지금

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1]) 

dist[k][k][k-1] 때문에 제외 될 수 없다 (또는 그래프에 negative loop이있는 경우) 이는 dist[i][k][k] = dist[i][k][k-1]을 의미합니다. 이후 dist[k][k][k-1] = 0 이후 두 매개 변수가 동일하면 그렇지 않으면 min()의 첫 번째 매개 변수가 선택됩니다. dist[i][j][k]을 계산할 때 dist[i][k] 또는 dist[k][j] 이미 자신의 경로에 k을 허용하는 경우 이제

는 dist[i][k][k] = dist[i][k][k-1] 때문에, 그건 문제가되지 않습니다. dist[i][j][k-1]은 dist[i][j][k]의 계산에만 사용되므로 dist[i][j][k]이 계산 될 때까지 은 dist[i][j][k-1]으로 유지됩니다. i 또는 j이 k과 같으면 위의 경우가 적용됩니다.

따라서 계산 순서는 중요하지 않습니다.

이제 알고리즘의 모든 단계를 수행 한 후 dist[i][j] = dist[j][i]을 표시해야합니다.

모든 a 및 b에 대해 dist[a][b] = dist[b][a]부터 시작합니다.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 
      = min(dist[j][i], dist[k][i] + dist[j][k]) 
      = min(dist[j][i], dist[j][k] + dist[k][i]) 
      = dist[j][i] 

따라서 우리의 지정은 모두 참이며 불변성을 유지합니다. dist[a][b] = dist[b][a]. 따라서 알고리즘의 모든 단계를 거친 후에 dist[i][j] = dist[j][i]

그러므로 두 알고리즘 모두 동일하고 정확한 결과를 산출합니다.

속도는 더 쉽게 증명할 수 있습니다. 내부 루프는 일반적으로 호출되는 횟수의 절반을 조금 넘기 때문에 함수는 약 두 배 빠릅니다. 여전히 동일한 횟수만큼 할당하기 때문에 약간 느리게 만들어졌지만, 대부분의 시간을 차지하는 것은 min()이므로 문제가되지 않습니다.

내 증명에 문제가있는 것으로 보이지만 기술적 인 부분이 있으면 지적하고 해결하도록 노력할 것입니다.

편집 :

당신은 모두 속도와 같은 루프을 변경하여 절반의 메모리를 절약 할 수 있습니다

for (int k = 0; k < N; ++k) { 
    for (int i = 0; i < k; ++i) 
     for (int j = 0; j <= i; ++j) 
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]); 
    for (int i = k; i < N; ++i) { 
     for (int j = 0; j < k; ++j) 
      dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]); 
     for (int j = k; j <= i; ++j) 
      dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]); 
    } 
} 

를이 너무 최적화 된 알고리즘의 루프 위를 분할 그것은 여전히 ​​정확하고 아마 같은 속도를 얻지 만 메모리의 절반을 사용합니다.

Chris Elion에게 감사드립니다.

Answer 2

(Wikipedia 기사의 의사 코드 표기법 사용) edgeCost 행렬이 대칭이면 경로 반복 행렬이 각 반복 후에도 대칭이 될 것이라고 나는 믿는다. 따라서 각 반복마다 항목의 절반 만 업데이트하면됩니다.

낮은 수준에서, d (i, j) = d (j, i)이므로 행렬의 절반 만 저장하면되므로 사용되는 메모리 양을 줄이고 수를 줄이면됩니다. 동일한 데이터를 여러 번 액세스하므로 캐시 미스가 발생합니다.

for (int k = 0; k < N; ++k) 
    for (int i = 0; i < N; ++i) 
     for (int j = 0; j <= i; ++j) 
      dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 

지금 물론 우리 모두가 정확하고 빠릅니다 표시해야합니다 : 일부 후