플로이드-워샬 알고리즘: 코딩 인터뷰 가이드

TL;DR: Floyd–Warshall 알고리즘은 동적 프로그래밍을 사용하여 모든 쌍의 최단 경로를 계산합니다. 그래프에서 거리 행렬을 초기화한 다음 모든 중간 정점 k에 대해 각 쌍을 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])으로 업데이트합니다. O(V³) 시간과 O(V²) 공간에서 실행되며 음수 대각선 항목을 통해 음수 순환을 노출할 수 있습니다.

플로이드-워샬 알고리즘이란 무엇입니까?

Floyd–Warshall은 모든 정렬된 정점 쌍 사이의 최단 경로에 대한 동적 프로그래밍 알고리즘입니다. 방향성 또는 방향성이 없는 가중치 그래프와 함께 작동하며 음수 간선을 허용합니다. 그러나 관련된 음의 가중치 사이클이 존재하는 경우 사이클을 반복적으로 횡단하면 경로 비용이 계속 감소하기 때문에 일부 최단 경로에는 유한 최소값이 없습니다.

이 알고리즘은 전역 경로 문제를 하나의 결정으로 바꾸기 때문에 기억에 남습니다. 현재 중간 정점 k의 경우 i에서 j로 가장 잘 알려진 경로가 있는 그대로 더 나은가요, 아니면 i에서 k로 이동한 다음 k에서 j로 이동하는 것이 더 나은가요?

재발을 어떻게 도출합니까?

D(k, i, j)를 i에서 j까지의 최단 거리로 정의하며, 중간 정점은 처음 k개의 정점에서만 나올 수 있습니다. 허용되는 최단 경로는 D(k−1, i, j)를 유지하면서 정점 k를 피하거나 k를 사용하고 i에서 k까지의 최상의 허용 경로와 k에서 j까지의 최상의 허용 경로로 분할됩니다.

그것은 재발을 제공합니다 :

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

k 단계는 호환되는 방식으로 k-1 단계 값에만 의존하기 때문에 행렬을 그 자리에서 업데이트할 수 있습니다. 이 추론은 중요한 루프 순서도 설명합니다. k는 가장 바깥쪽 루프여야 합니다. i 또는 j를 외부에 놓으면 불변성이 변경되고 부분적으로 허용된 경로를 잘못 사용할 수 있습니다.

거리 행렬을 어떻게 초기화합니까?

V x V 행렬을 만듭니다. dist[i][i]을 0으로 설정하고 직접 가장자리의 셀을 가중치로 설정하고 직접 가장자리가 없으면 무한대를 사용합니다. 평행한 모서리가 가능하다면 가장 작은 직접 중량을 유지하십시오. 두 거리를 추가하기 전에 무한 감시자가 오버플로되거나 잘못된 후보를 생성하지 않도록 둘 다 유한한지 확인하십시오.

인터뷰에서 Floyd–Warshall을 어떻게 추적합니까?

행렬 행에 소스로 레이블을 지정하고 열에 대상으로 레이블을 지정합니다. 초기 행렬을 표시한 다음 하나의 k를 선택하고 대표 셀을 평가합니다. 각 셀에 대해 현재 값을 k를 통한 경로와 비교합니다. 두 세그먼트 모두에 연결할 수 있고 새 합계가 더 작은 경우에만 업데이트하세요.

일반적으로 큰 예를 위해 모든 행렬을 그릴 필요는 없습니다. 한 가지 개선 사항과 한 가지 변경되지 않은 값을 포함하여 불변성을 입증하기에 충분한 셀을 추적합니다. k를 완료한 후 모든 행렬 항목은 중간 정점이 처리된 집합으로 제한되는 경로 중에서 최적임을 명시합니다.

어떤 의사 코드를 작성해야 합니까?

외부에 k가 있는 세 개의 중첩 루프를 사용합니다.

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

유한 검사와 숫자 유형에 대해 설명하세요. 큰 정수 센티널이 있는 언어에서는 음수 값에 무한대를 추가하면 유한해 보이거나 오버플로될 수 있습니다. 가드는 단순한 구현 세부 사항이 아니라 정확성의 일부입니다.

시간과 공간의 복잡성은 무엇입니까?

세 개의 루프는 k, i, j의 모든 조합을 검사하므로 런타임은 O(V³)입니다. 거리 행렬은 O(V²) 공간을 차지합니다. 내부 업데이트는 3차원 테이블을 피하는 반면, 경로 재구성을 위한 다음 홉 또는 선행 행렬은 O(V²) 더 많은 공간을 추가합니다.

Floyd–Warshall은 구현이 간결하고 예측 가능하기 때문에 적당한 밀도의 그래프에 종종 매력적입니다. 음수가 아닌 간선이 있는 대규모 희소 그래프의 경우 각 소스에서 Dijkstra를 실행하는 것이 더 효율적일 수 있습니다. 선택하기 전에 항상 필요한 출력, 그래프 밀도, 가중치 제약 조건 및 정점 수를 비교하십시오.

실제 최단 경로를 어떻게 재구성합니까?

거리만으로는 정점 순서를 알 수 없습니다. i에서 j로의 직접 간선이 존재할 때 j로 초기화된 next[i][j] 행렬을 유지합니다. k를 통한 라우팅이 dist[i][j]을 향상시킬 때마다 next[i][j]를 next[i][k]로 설정하세요. 경로를 재구성하려면 대상에 도달할 때까지 현재 정점에서 next[current][destination]까지 반복적으로 이동합니다.

재구성하기 전에 연결할 수 없는 쌍을 확인하고 부정적인 주기 사례로부터 보호하세요. 쌍이 음의 주기로 이동한 다음 목적지에 도달할 수 있는 경우 재구성할 수 있는 유한한 최단 경로는 없습니다.

Floyd–Warshall은 어떻게 음의 순환을 감지합니까?

알고리즘이 완료된 후 대각선을 검사합니다. dist[v][v] < 0 값은 v에서 음의 가중치 사이클에 도달할 수 있고 v로 돌아갈 수 있음을 증명합니다. 이는 단순히 음의 가장자리를 찾는 것보다 더 강력합니다. 완벽하게 유효한 최단 경로를 갖는 그래프에는 음의 가장자리가 존재할 수 있습니다.

면접관이 어떤 쌍이 영향을 받는지 묻는 경우 i가 정점 v에 도달할 수 있고 v가 j에 도달할 수 있는 모든 i와 j를 식별합니다. 이러한 쌍은 음의 순환을 임의로 여러 번 반복할 수 있으므로 최단 경로 값은 유한하지 않습니다.

언제 다른 최단 경로 알고리즘을 선택해야 합니까?

가중치가 없는 그래프에는 너비 우선 검색을 사용하고, 음수가 아닌 가중치가 있는 단일 소스 문제에는 Dijkstra를 사용하고, 음수 가중치 또는 도달 가능한 음주기 감지가 중요한 경우 단일 소스에는 Bellman–Ford를 사용합니다. Floyd–Warshall은 모든 쌍 거리가 필요하고 입방 시간이 허용되는 경우 직접 선택합니다.

어떤 면접 실수를 피해야 합니까?

k를 다른 루프 안에 넣거나, 대각선에 0을 잊어버리거나, 가드 없이 무한대를 추가하거나, 음수 에지를 음수 사이클과 혼동하거나, O(V²) 행렬 공간이 모든 표현에서 자동으로 입력을 포함한다고 주장하지 마세요. 그래프가 방향을 향하고 있는지, 평행 모서리가 존재하는지, 면접관에게 거리, 경로 또는 주기에 영향을 받는 쌍이 필요한지 여부를 명확히 합니다.

코딩 인터뷰 보조 워크플로을 연습하고, Bellman–Ford 알고리즘을 비교하고, Big O 복잡성 치트 시트을 검토하세요.

자주 묻는 질문

루프뿐만 아니라 불변성을 연습하세요.

YesToTheOffer는 코딩 설명을 구성하고, 이를 개인 준비 노트에 기초하고, 극단적인 사례를 조사하고, 나중에 검토할 수 있도록 인터뷰 기록을 보존하는 데 도움이 됩니다.