그래프 (4) - 최단 경로(다익스트라, 벨만-포드, SPFA, 0-1 BFS)

그래프 이론의 유명한 문제인 최단 경로 문제를 해결하는 알고리즘에 대해 알아보자. 알고리즘에 따라 사용 가능한 조건과 얻을 수 있는 결과가 다르기 때문에 상황에 맞는 알고리즘을 잘 골라서 사용하는 것이 중요하다.

 

다익스트라

다익스트라(Dijkstra) 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 꽤 빠른 시간 안에 동작하나 가중치가 양수여야 한다는 제한조건이 있다. 이는 다익스트라가 (전체 최단 경로)=(부분 최단 경로들의 합)이라는 그리디한 접근으로 동작하기 때문이다.

* 참고: 다익스트라의 초기 아이디어는 그리디이나, 효율성을 위해 힙을 사용하게 되면서 힙에 방문한 정점을 중복해서 넣는 방식으로 구현하면 일종의 백트래킹처럼 동작한다. 이 경우 음수 가중치의 간선도 처리가 가능하다. 그러나 음수 사이클의 처리가 불가능하고, 음수 간선이 많아짐에 따라 시간복잡도가 지수적으로 증가할 우려가 있어 어쨌든 음수 가중치가 포함된 경우 벨만-포드를 사용하는 것이 보통 안전하다.

 

알고리즘은 다음과 같다.

1) 각 정점의 cost를 inf로 초기화하고, 시작 정점의 cost=0으로 한다. 시작 정점을 힙에 넣는다.

2) 힙에서 최소 cost인 정점을 pop하여 정점을 방문처리하고, 해당 정점($u$)과 연결된 정점 중 방문하지 않은 정점($v$)들을 살펴본다. 이때 $u$를 거쳐 가는 경로의 cost가 더 적다면($cost[u]+w<cost[v]$), 갱신하고 $v$를 힙에 push한다.

3) 힙이 빌 때까지 반복한다.

 

힙에서 가장 작은 cost를 가진 정점 $u$를 꺼내는 순간 $cost[u]$가 최적해임이 보장되므로, $u$를 더 이상 볼 필요 없이 방문처리하고 인접한 정점들의 cost를 relax해준다고 생각하면 쉽게 짤 수 있다. 다익스트라의 시간복잡도는 $O((V+E)\log V)$이다.

def dijkstra(start):
    cost = [float('inf')]*(N+1)
    cost[start] = 0
    heap = []
    heapq.heappush(heap, (0, start_node))
    
    visited = [False]*(N+1)
    while heap:
        u_cost, u = heapq.heappop(heap)
        if visited[u]: continue
        visited[u] = True
        for v, v_cost in adj[u]:
            if visited[v]: continue
            if (total_cost := u_cost+v_cost) < cost[v]:
                cost[v] = total_cost
                heapq.heappush(heap, (total_cost, v))
    
    return cost

 

최단 경로의 복원이 필요한 경우에는, parents 배열을 만들어서 갱신될 때마다 $parents[v]=u$로 설정해 주면 되겠다. 이후 도착점부터 parents 배열에 따라 거꾸로 이어 나가면 최단 경로를 만들어낼 수 있다.

 

 

벨만-포드

벨만-포드(Bellman-Ford) 알고리즘은 다익스트라처럼 정해진 시작점으로부터 다른 정점까지의 최단 거리를 계산하지만, 음수 가중치가 포함된 경우에도 사용 가능한 알고리즘이다. 대신 시간복잡도는 $O(VE)$로 다익스트라보다 느리다.

 

아이디어는 더 간단한데, (음수 사이클이 없다면) 두 정점을 잇는 최단 경로가 지나는 간선 개수는 최대 $V-1$개임을 이용한다. 음수 가중치가 있어 그리디한 방식으로 접근하기 어려우므로, 단순하게 모든 간선을 살펴보는 것을 $V-1$번 반복하면서 최솟값을 업데이트해준다. 다만 음수 사이클이 있는 경우를 검출할 필요가 있기 때문에, 마지막에 한 번 더 반복하면서 $V-1$번 이후인데도 업데이트가 이루어지는지 검사한다.

def bellman_ford(start):
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    
    for i in range(V):
        for u, v, w in edges:
            if dist[u] == float('inf'): continue
            if (new_dist := dist[u] + w) < dist[v]:
                dist[v] = new_dist 
                if i == V-1: return _, True
    
    return dist, False

 

 

SPFA

벨만-포드에서 모든 간선을 반복해서 체크하는 행위가 비효율적이라 느껴진다면, SPFA(Shortest Path Faster Algorithm)을 이용해 보자. 업데이트가 일어난 정점의 목록을 queue로 관리하면서 해당 정점들과 연결된 간선에 대해서만 업데이트를 진행한다. 이때 큐에 이미 들어 있는 정점을 또 넣을 필요는 없으므로, in_queue 배열을 만들어서 관리해준다.

음수 사이클은 같은 정점이 큐에 V번 들어오는 것으로 판단할 수 있다. cycle 배열을 만들어서 정점이 큐에 들어올 때마다 +1하여 구현해주면 된다.

def spfa(start):
    dist = [float('inf')]*N
    q = deque()
    in_queue = [False]*N
    cycle = [0]*N
    
    dist[start] = 0
    q.appendleft(start)
    in_queue[start] = True
    cycle[start] = 1

    while q:
        u = q.pop()
        in_queue[u] = False
        for v, w in adj[u]:
            if (new_dist := dist[u]+w) < dist[v]:
                dist[v] = new_dist
                if not in_queue[v]:
                    in_queue[v] = True
                    q.appendleft(v)
                    
                    cycle[v] += 1
                    if cycle[v] >= N: return False
    
    return dist

 

SPFA의 시간복잡도는 최악의 경우 벨만-포드와 동일하게 $O(VE)$이나, 평균적으로는 $O(V+E)$ 정도에 동작한다.

 

 

0-1 BFS

추가로, 특수한 상황에서 빠르게 최단 경로를 구해낼 수 있는 일종의 트릭인 0-1 BFS에 대해 알아보자.

0-1 BFS는 간선의 가중치가 0 or 1로만 구성된 상황에서 적용 가능하다. deque으로 BFS를 돌리면서 연결된 간선의 가중치가 0인 정점은 덱의 front에, 1인 정점은 덱의 back에 삽입해 준다. 이렇게 반복하면 덱 전체에 들어 있는 정점들이 [(가중치 +0인 정점들), (가중치 +1인 정점들)] 두 레벨으로만 나뉘게 되므로, $O(1)$으로 다익스트라처럼 큐 안의 정점들이 정렬된 것과 같은 효과를 얻을 수 있다. 따라서 $O(V+E)$만에 문제를 해결할 수 있다.

def bfs(start):
    dist[start] = 0
    q = deque()
    q.append(start)
    visited = [False]*(N+1)

    while q:
        u = q.popleft()
        if visited[u]: continue
        visited[u] = True

        for v, w in adj[u]:
            if visited[v]: continue
            if w == 0:
            	if dist[u] < dist[v]:
                    dist[v] = dist[u]
                    q.appendleft(v)
            else:
            	if dist[u] + 1 < dist[v]:
                    dist[v] = dist[u] + 1
                    q.append(v)
  
    return dist