플로이드 와샬 알고리즘 시간복잡도 - peulloideu wasyal algolijeum siganbogjabdo

플로이드-워셜 알고리즘

다익스트라, 벨만-포드 알고리즘으로 주어진 하나의 정점으로부터 다른 모든 정점들까지의 최단 경로를 구할 수 있었다면, 플로이드-워셜 알고리즘을 활용하면 모든 정점들간의 최단 경로를 구할 수 있다.
다익스트라 알고리즘에서는 출발점이 정해져 있었기 때문에 출발점에서 도달할 수 있는 가장 가까운 경로를 탐욕적으로 선택해갔다. 그런데 출발점이 따로 정해져있지 않은 경우에는 어떨까?

플로이드-워셜 알고리즘 구현

플로이드-워셜 알고리즘은 경유하는 정점에 초점을 두고, 그 정점을 거쳐가는 경로가 기존 경로보다 더 효율적인지를 판단한다. 즉, 경유하는 정점의 입장에서 어떤 정점 u가 다른 정점 v로 갈 때 자신을 거쳐서 가는 것이 기존의 경로보다 더 효율적이라면 기존의 경로를 갱신해주는 작업을 반복하는 것이다.

플로이드-워셜 알고리즘 프로세스

1. 간선들의 정보(정점, 간선의 길이)를 저장할 인접행렬을 만들고, 거리 값은 무한대로 초기화한다.
2. 인접행렬에 간선들의 정보를 저장한다. 이 때 두 정점 사이의 간선이 여러 개라면 더 짧은 간선을 저장한다.
3. 경유지를 기준으로, 어떤 두 정점이 해당 경유지를 거처갈 경우에 기존의 거리보다 더 짧다면 기존의 거리 값을 갱신한다.
4. 모든 정점을 경유지로 설정해 3번 과정을 반복한다.

플로이드-워셜 알고리즘 코드 (Python)

def floyd_warshall(n, edges):
    # 그래프 정보를 담을 인접행렬, 거리는 무한대로 초기화
    adj = [[float('inf')] * (n+1) for _ in range(n+1)] 
    
    # 인접행렬에 그래프 정보 저장 (정점 u -> v 거리 w)
    for u, v, w in edges:
        adj[u][v] = w
    
    # k : 경유지 (각 정점들을 경유지로 설정)
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
            	# 정점 i -> j로 갈 때 기존 거리값과 k를 거쳐갈 때의 거리 값 중 작은 값을 저장
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
    
    return adj
    
# 정점 개수 & 간선 정보
n = 4  
edges =  [[1, 2, 4],
    [1, 3, 1],
    [2, 3, 2],
    [2, 4, 1],
    [3, 2, 1],
    [4, 1, 5],
    [4, 3, 5]]
    
# 결과 출력
dist = floyd_warshall(n, edges)
for i in range(1, n+1):
    print(dist[i][1:])

시간 복잡도 & 공간 복잡도

코드에서 알 수 있듯이 정점의 개수 VV만큼 반복분이 3중으로 수행되고 있기 때문에 O(V3)O(V^3)의 시간 복잡도를 갖는다.
그리고 간선들의 정보를 V∗VV*V 크기의 인접행렬에 담았기 때문에 O(V2)O(V^2) 의 공간 복잡도를 갖는다.

플로이드 워셜(Floyd-Warshall)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 에 사용할 수 있는 알고리즘이다.

• 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라와 다른 점이다.

노드의 개수가 n 개일때 n 번의 단계를 수행하며 단계마다 O(N²) 의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 그래서 총 시간 복잡도는 O(N³)이다.

즉, 모든 지점을 시작으로 삼고 모든 지점에 대해서 끝으로 삼아서 최단 거리를 구하는데 모든 노드를 경유지로 삼는 과정인 n 번의 단계를 수행 한다. min(시작 → 끝, 시작 → 경유 + 경유 → 끝) 를 구하는 것이다.

• 다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 배열을 사용하였다.
• 반면에 플로이드-워셜 알고리즘은 모든 노드에 대해서 다른 모든 노드로의 최단 거리를 저장해야 하기 때문에 2차원 배열을 사용해야 한다. 이때문에 n 번의 단계마다 O(N²) 의 시간이 소요된다는 것이다.
• 다이스트라 알고리즘은 그리디 알고리즘이다.
• 플로이드-워셜 알고리즘은 n 번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 배열을 갱신하기 때문에 다이나믹 프로그래밍이다.

전체적으로 3중 반복문을 잉요하여 최단 거리 배열을 갱신하면 된다. 핵심 개념에 대해서 Swift 로 구현된 예시 코드를 살펴보자.

var answer = 0
// 최단 거리를 가지는 2차원 배열
var node: [[Int]] = []

// 지점 사이의 요금은 1이상 100,000이하.
// 지점의 총 갯수 n 은 최대 200개.
// ✅ 요금의 최대값은 가장 비싼 요금의 모든 지점을 거치는 경우이므로 200 * 100000 로 표현 가능.
// 이때 Int.max 를 사용하면 메모리 초과가 발생하기도 한다.
node = Array(repeating: Array(repeating: 200 * 100000, count: n + 1), count: n + 1)

// Floyd-Warshal 알고리즘
for i in 1...n { // 경유지 1...n 
    for j in 1...n {
        for k in 1...n {
            if node[j][k] > node[j][i] + node[i][k] {
                node[j][k] = node[j][i] + node[i][k]
            }
        }
    }
}

// 시작점에서 AB 각각으로 이동하는 경우.
answer = node[s][a] + node[s][b]
    
// ✅ n번의 단계에서 최단 경로 구하기
for i in 1...n {
    answer = min(answer, node[s][i] + node[i][a] + node[i][b])
}

// 출처: 2021 KAKAO BLIND RECURITMENT - 합승 택시 요금