Floyd Warshall Algorithm

+10

n개의 노드가 있는 방향 그래프가 주어집니다. 노드의 번호는 0부터 n-1까지입니다. 이 그래프는 n x n 행렬로 주어지며, matrix[i][j]는 노드 i에서 노드 j로 가는 간선의 가중치입니다. 간선이 없으면 -1이고, matrix[i][i]는 0입니다. 경로의 길이는 해당 경로에 포함된 간선 가중치의 합입니다.

노드 i에서 노드 j까지의 최단 경로 길이를 [i][j] 항목에 담은 n x n 행렬을 반환하세요. 노드 i에서 노드 j에 도달할 수 없으면 -1을 담습니다.

함수

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: 간선 가중치: matrix[i][j]는 i에서 j로 가는 간선의 가중치이며, 간선이 없으면 -1입니다
반환값integer-2d-array: 모든 노드 쌍 사이의 최단 거리, 경로가 없는 경우 -1

제약 조건

1 ≤ n ≤ 100, 여기서 n = matrix.length = matrix[i].length
matrix[i][i] = 0
i ≠ j인 경우, matrix[i][j]는 -1(간선 없음)이거나 0 ≤ matrix[i][j] ≤ 1000입니다.
간선은 한 방향입니다: matrix[i][j]와 matrix[j][i]는 서로 독립적입니다.

예제

입력: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
출력: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
설명: 노드 0은 노드 1을 거쳐 노드 2에 11이 아닌 6의 비용으로 도달하고, 노드 3에는 9의 비용으로 도달합니다. 노드 1은 노드 2를 거쳐 노드 0에 3의 비용으로 도달합니다. 노드 3에서는 아무것도 나가지 않으므로, 대각선이 아닌 위치에 있는 해당 행의 값은 -1입니다.

입력: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
출력: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
설명: 2에서 1로 가는 간선의 가중치는 0이므로 0 → 2 → 1의 비용은 1이며, 직접 가는 비용인 6보다 작습니다. 노드 1에서 나가는 간선도, 노드 0으로 들어오는 간선도 없으므로 해당 쌍의 값은 -1로 유지됩니다.

후속 질문

테이블을 만든 뒤 간선 하나의 비용이 낮아집니다. O(n²) 반복문을 다시 실행하는 대신 O(n³)으로 모든 거리를 갱신할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

모든 노드 쌍에 대해 최단 경로를 구해야 합니다. Floyd-Warshall은 삼중 루프 하나로 n²개의 모든 답을 찾습니다. 각 라운드에서는 경로가 노드를 하나 더 거쳐 가도록 하고, 쌍마다 비교 한 번의 비용이 듭니다. 지금까지의 최선 경로와 새 노드를 거치는 경로를 비교합니다.

아무것도 바뀌지 않을 때까지 모든 경로를 간선 하나씩 확장합니다

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

행렬에서 시작해 각 단계마다 모든 경로를 간선 하나씩 연장합니다. i에서 m까지의 경로에 간선 m → j를 더하면 i에서 j까지의 경로가 되며, 더 짧은 경우에만 유지합니다. 아무것도 바뀌지 않을 때까지 반복합니다.

p번의 단계를 거치면 간선이 최대 p+1개인 모든 최단 경로를 찾습니다. 가중치는 음수가 아니므로 어떤 최단 경로에는 루프가 없고 간선이 최대 n-1개이며, 모든 거리가 최종값이 되면 단계가 멈춥니다. 노드가 100개일 때 한 단계는 n³ = 10^6번의 연산이고, 최단 경로가 긴 사슬을 이루면 최대 n번의 단계가 필요합니다. 따라서 O(n⁴), 최대 10^8번의 연산입니다.

알고리즘

matrix를 dist에 복사합니다.
모든 i, m, j에 대해 dist[i][m]과 matrix[m][j]가 모두 존재하면 두 값의 합을 계산합니다.
dist[i][j]가 -1이거나 합보다 크면 합을 저장하고, 해당 반복에서 값이 변경되었음을 기록합니다.
아무것도 변경되지 않을 때까지 반복한 다음 dist를 반환합니다.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: 라운드마다 정류장을 하나 더 허용

핵심 아이디어

경로가 양 끝점 사이에서 멈출 수 있는 노드를 제한합니다. 표는 경유지가 없는 경로인 행렬로 시작합니다. k번째 라운드가 끝난 뒤 dist[i][j]는 경유지가 모두 노드 0부터 k까지에 속하는 최단 경로이며, 마지막 라운드에서 답을 얻습니다.

k번째 라운드에서 k에도 멈출 수 있는 최적 경로는 k를 건너뛰거나, 가중치가 음수가 아니므로 k를 한 번 통과합니다. 전자의 경로는 이미 표에 있습니다. 경로의 두 부분은 노드 0부터 k-1까지만 경유하므로 각각 dist[i][k]와 dist[k][j]입니다.

첫 번째 예제에서 1번째 라운드는 노드 0에서 노드 2로 가는 직접 경로의 길이 11을 6으로 바꿉니다. 2번째 라운드에서는 노드 0에서 노드 3까지의 경로 길이가 6 + 3 = 9가 되며, 길이 6인 경로 안에 노드 1을 경유합니다.

표 하나면 충분합니다. dist[k][k]가 0이므로 k번째 라운드에서 행 k와 열 k는 바뀌지 않습니다.

알고리즘

matrix를 dist에 복사합니다. -1은 아직 경로를 찾지 못했다는 뜻입니다.
k를 0부터 n-1까지 순회하며, 모든 i와 j에 대해 다음을 수행합니다. dist[i][k] 또는 dist[k][j]가 -1이면 해당 쌍은 건너뜁니다.
그렇지 않으면 via = dist[i][k] + dist[k][j]를 계산합니다.
dist[i][j]가 -1이거나 via보다 크면, 해당 값을 via로 설정합니다.
dist를 반환합니다.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

함정과 경계 사례

-1을 가중치처럼 더하기: -1 + 5 = 4는 경로처럼 보입니다. 먼저 두 부분을 모두 확인하고, dist[i][j]의 -1은 어떤 경로보다도 나쁜 값으로 취급하세요.
k에 대한 반복문을 안쪽에 넣기. 정점 k를 후보로 고려하기 전에, 0부터 k-1까지의 경유지를 거치는 경로가 확정되어야 합니다.
가장 큰 int를 무한대로 사용하기: 두 값을 더하면 32비트 int에서 오버플로가 발생해 음수 거리가 됩니다. 실제 거리는 최대 99 × 1000 = 99,000이므로 10^9는 안전합니다. 2 × 10^9가 2^31-1보다 작기 때문입니다.
간선이 양방향이라고 가정하기. 두 번째 예제에서 정점 0은 정점 1에 도달하지만, 정점 1에서는 어디에도 도달할 수 없습니다.
가중치를 무시하는 너비 우선 탐색 실행하기: 첫 번째 예제에서 정점 0에서 정점 2까지의 거리를 6이 아니라 11이라고 보고합니다.

자주 묻는 질문3

Floyd Warshall 알고리즘의 시간 복잡도는 얼마인가요?

노드가 n개일 때 시간 복잡도는 O(n³)입니다. 노드에 대해 세 개의 중첩 루프를 수행하고, 각 단계에서 덧셈 한 번과 비교 한 번을 하므로 노드가 100개일 때 10^6단계가 필요합니다. 거리 테이블의 공간 복잡도는 O(n²)이며, 제자리에서 업데이트할 수 있습니다.

Floyd Warshall은 음수 간선 가중치에서도 작동하나요?

네, 가중치의 합이 0보다 작은 루프인 음수 사이클이 없는 한 그렇습니다. 음수 사이클이 있으면 최단 경로가 정의되지 않으며, 표에서 이를 확인할 수 있습니다. 일부 dist[i][i]가 0보다 작은 값으로 끝납니다.

다익스트라 알고리즘 대신 플로이드-워셜 알고리즘을 사용해야 하는 경우는 언제인가요?

수백 개 이하의 노드로 이루어진 조밀 그래프에서 모든 노드 쌍을 구하려면 Floyd-Warshall을 사용하세요. 배열을 사용하는 경우 모든 노드에서 다익스트라를 실행하는 데 O(n³)이 걸리고, 힙을 사용하면 O(n · E log n)이 걸리므로 큰 희소 그래프에서는 다익스트라가 더 효율적입니다. Floyd-Warshall은 힙이 필요 없고 음수 간선도 허용하지만, 다익스트라는 그렇지 않습니다.

def shortestDistances(matrix):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

예상 출력

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]