[알고리즘] 플로이드 워셜 알고리즘 (+LeetCode 1335)

참고하면 좋은 이전 글: [알고리즘] 다이나믹 프로그래밍 (개념) + LeetCode 509

플로이드 워셜 알고리즘 (Floyd-Warshall algorithm)은 directed graph (유향 그래프: 간선에 방향성이 있는 그래프)에서 노드 i에서 노드 j로 가는 최단 경로를 찾는 알고리리즘이다. 최단 경로를 찾는다는 점에서는 다익스트라 알고리즘과 비슷하지만, 다익스트라 알고리즘은 한 노드에서 출발해서 다른 노드까지 가는 최단 경로를 찾는 방면, 플로이드 워셜 알고리즘은 모든 쌍 i,j에 대해서 최단 거리를 찾는다.

플로이드 와셜 알고리즘을 사용하기 위해서 다음 조건을 만족해야 한다:

• 간선의 가중치(편의상 '거리'라고도 표현하겠습니다)는 양수일 수도 있고 음수일 수도 있다
• Negative cycle은 없어야 한다. Negative cycle이란 그래프에서 순환하는 경로를 이루는 간선의 가중치를 더했을 때 음수가 되는 경로를 뜻합니다. 이러한 경로가 있으면 최단 경로는 무의미해집니다 (negative cycle을 순환하면 거리가 계속 낮아짐)
• 간선에 방향성이 없는 그래프에서도 사용이 가능하지만 이런 경우 간선의 가중치가 음수일 수 없습니다. 예를 들어 1번 노드와 2번 노드를 잇는 가중치가 음수이면 1 -> 2 -> 1은 negative cycle이 되기 때문입니다.

플로이드 워셜 알고리즘은 dynamic programming과 익숙하면 쉽게 이해할 수 있다.

• n = 그래프에 있는 노드 개수
• \( i \in \{ 1,2,...,n\}\): 출발지, \(j \in \{ 1,2,...,n\}\): 도착지
• i에서 j로 가는 최단 경로를 구하는 것이 문제
• {1, 2, ..., k-1}에 있는 노드만 경유해서 i -> j로 가는 최단 경로를 구했다고 하자
• {1,2,...,k}에 있는 노드만 경유해서 i -> j로 가는 최단 경로를 구할 수 있으면 k=n이 될 때까지 반복하면 된다
• 참고로 {1,...,k-1}이 있는 노드만 경유하는 것보다 {1,...,k}에 있는 노드만 경유하는 것이 더 짧을 수밖에 없다: {1,...,k-1}에 있는 노드만 경유하는 경로는 {1,...,k}에 있는 노드만 경유하는 경로이기 때문이다
• i -> j로 갈 때 {1,...,k}에 있는 노드만 경유하는 경로의 최단 거리를 d(i,j,k) 로 표현하자
• d(i,j,k) = min(d(i,j,k-1), d(i,k,k-1) + d(k,j,k-1)). 설명하자면 노드 k를 가능한 경유지에 추가했을 때 d(i,j,k)는 바뀌지 않거나 (다시 말해서 {1,...,k-1} 노드만 경유하거나) k를 경유해야 한다 ( i -> k -> j ). 두 가지 경우 중 더 작은 거리로 업데이트해주면 된다. 여기서 후자 같은 경우 최단 거리를 d(i,k,k-1) + d(k,j,k-1)로 구할 수 있다.

python 코드로 정리하면 다음과 같다. 여기서 w[i][j]는 i에서 j로 가는 간선의 가중치로 초기화된다. w[i][i] = 0이고 경로가 없는 i,j 쌍에 대해서는 모두 가중치가 inf로 초기화되어 있다고 가정했다.

import sys
inf = sys.maxsize # 무한대
def FWA(w): # w: 간선 weight
    n = len(w) # 노드 수
    for k in range(n): # 경유지
        for i in range(n): # 출발지
            for j in range(n): # 도착지
                # inf가 바뀌지 않도록 예외 처리
                if w[i][k] == inf or w[k][j] == inf:
                    continue
                w[i][j] = min(w[i][j], w[i][k] + w[k][j])
    return w

중간에 예외처리 (f w[i][k] == inf or w[k][j] == inf)가 있는 이유는 무한대에 어떤 수를 더해도 무한대가 되어야 하지만 실제로 inf에 수를 더하면 바뀌기 때문에 추가해 뒀다.

여기서 w[i][j]들을 저장해야 하기 때문에 공간 복잡도는 O(n^2)가 되고, i,j,k loop들을 돌기 때문에 시간 복잡도는 O(n^3)이 된다.

 

위키피디아에 있는 예시에 플로이드 워셜 알고리즘을 적용해 보자

간선 가중치들이 양수/음수인 directed graph다. 플로이드 워셜 알고리즘을 이해하기 위해서 간단하게 2 -> 3으로 가는 경로를 보자. 경유 노드가 없는 경우 거리가 3인 경로밖에 존재하지 않는다. 하지만 1번 노드가 경유지에 추가되면 2 -> 1 -> 3의 거리는 2라서 최단 거리가 3에서 2로 업데이트된다. 이런 방식으로 경유지를 추가하면서 최단 거리를 업데이트하는 것이 플로이드 워셜 알고리즘의 핵심이다. 이제 코드를 적용해서 각 k마다 어떻게 최단 거리가 업데이트되는지 출력해 보자: 

----- w 초기 값 -----
[[0, 'inf', -2, 'inf'],
[4, 0, 3, 'inf'],
['inf', 'inf', 0, 2],
['inf', -1, 'inf', 0]]
----- k=0 -----
[[0, 'inf', -2, 'inf'],
[4, 0, 3, 'inf'],
['inf', 'inf', 0, 2],
['inf', -1, 'inf', 0]]
----- k=1 -----
[[0, 'inf', -2, 'inf'],
[4, 0, 2, 'inf'],
['inf', 'inf', 0, 2],
['inf', -1, 'inf', 0]]
----- k=2 -----
[[0, 'inf', -2, 'inf'],
[4, 0, 2, 'inf'],
['inf', 'inf', 0, 2],
[3, -1, 1, 0]]
----- k=3 -----
[[0, 'inf', -2, 0],
[4, 0, 2, 4],
['inf', 'inf', 0, 2],
[3, -1, 1, 0]]
----- 마지막 결과 -----
[[0, -1, -2, 0],
[4, 0, 2, 4],
[5, 1, 0, 2],
[3, -1, 1, 0]]

이제 문제를 풀어보자

https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/description/

도시를 이어주는 간선들이 있을 때, 도시에서 도시로 가는 최단 거리가 distanceThreshold를 넘지 않는 도시가 가장 많은 도시를 찾는 문제다. 이 조건을 만족하는 도시가 여러 개 있는 경우 더 큰 도시 index를 리턴하라는 일종의 예외처리를 요구한다 (예시는 링크 참고)

플로이드 워셜 알고리즘을 사용하면 쉽게 풀 수 있다:

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # 플로이드 워셜 알고리즘 구현
        inf = sys.maxsize
        w = [[inf for i in range(n) ] for j in range(n)]
        for i in range(n):
            w[i][i] = 0
        for edge in edges:
            i,j,w_ij = edge
            w[i][j] = w[j][i] = w_ij
        def FWA(w):
            N = len(w)
            for k in range(N):
                for i in range(N):
                    for j in range(N):
                        w[i][j] = min(w[i][j], w[i][k] + w[k][j])
            return w
        # 우선 i->j로 가는 최단 거리를 모두 구한다
        w = FWA(w)
        # distanceThreshold를 초과하지 않는 도시의 수를 찾는다
        num_threshold_cities = [len([d for d in d_list if d <= distanceThreshold])-1 for d_list in w]
        # threshold 넘지 않는 최소 도시의 수
        min_val = min(num_threshold_cities)
        # 최소 도시의 수가 같은 경우가 있으면 가장 높은 index를 요구하기 때문에 reverse를 먼저 한다
        num_threshold_cities.reverse()
        # reversed list에서 최소 값을 갖는 index를 구한 후 reverse하지 않은 list의 index로 다시 바꿔서 리턴
        return len(num_threshold_cities)-num_threshold_cities.index(min_val)-1

다음 문제들도 플로이드 워셜 알고리즘을 적용하면 어렵지 않게 풀 수 있습니다:

•https://www.acmicpc.net/problem/11404

•https://school.programmers.co.kr/learn/courses/30/lessons/72413