[Algorithm] 8. Shortest Path

최단 경로 알고리즘

• 가장 짧은 경로를 찾는 알고리즘이다.
• 한 지점에서 다른 한 지점까지의 최단 경로, 한 지점에서 다른 모든 지점까지의 최단 경로 등 다양한 문제상황이 있을 수 있다.
• 각 지점은 그래프에서 노드로 표현한다.
  • 각 노드는 문제 상황에 따라서 국가 도시 등 다양한 형태로 표현될 수 있다.
• 지점 간 연결된 도로는 그래프에서 간선으로 표현한다.
  • 특정 노드에서 다른 노드로 이동이 가능하다면, 방향성이 있는 간선을 통해서 표현 가능하다. 이러한 간선은 문제 상황마다 도로나 통로로 표현된다.

다익스트라(Dijkstra) 알고리즘

• 대표적인 최단 경로 알고리즘이다.
• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.
  • 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다. 따라서 현실세계의 길찾기 문제에서 사용될 수 있는 알고리즘이다.
• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.
  • 매 상황에서 아직 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
• 다만 기본적으로 최단 경로 문제는 DP 알고리즘으로 분류되기도 한다.
  • A → C 최단 경로에 B 를 거쳐가는 경로가 존재한다고 하면 A → B, B → C 최단경로를 모두 고려한 경로로 만들어지기 때문이다. 따라서 기본적으로 길찾기 문제는 DP 원리가 적용된 문제라고 할 수 있다.
• 동작 과정
  • 다익스트라 최단 경로 알고리즘은 다시 한번 이야기하면, 하나의 출발 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.
    1. 출발 노드를 설정한다.
    2. 최단 거리 테이블을 초기화 한다. 초기화하는 과정에서 처음에는 기본적으로 모든 노드까지 가기 위한 비용을 무한으로 설정한다. 그리고 자기 자신에 대한 노드는 0으로 설정한다. 자기 자신에서 자기 자신으로 가는 비용은 0이라고 볼 수 있기 때문이다.
    3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 이 과정으로 다익스트라 최단 경로 알고리즘이 그리디 알고리즘으로 분류된다.
    4. 3번에서 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
    5. 위 과정에서 3번과 4번을 반복한다.
• 그리디 알고리즘으로 이 문제를 해결할 수 있는 이유는, 3번 과정을 통해 현재 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는 과정을 반복할 때마다 그렇게 선택된 노드까지의 최단거리는 더이상 바뀌지 않는다는 점 때문이다.
• 즉 매번 현재를 기준으로 하여 최단 거리가 가장 짧은 노드를 선택하는 과정을 반복할 때마다 특정 노드까지의 최단거리를 확실히 결정하는 것과 같다고 볼 수 있다.
• 이러한 특징 때문에 매 상황마다 아직 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택하는 것을 반복함으로써 모든 노드에 대해서 다 방문처리가 끝났을 때 우리는 전체 노드까지의 모든 최단 거리를 알 수 있는 것이다.
• 또한 다익스트라 최단 경로 알고리즘의 단순한 형태는 출발 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 것과 같다. 즉 다익스트라 최단 경로 알고리즘이라고 부르지만 단순히 이러한 과정을 반복하게 되면 각 노드까지의 최단 거리만 알 수 있게 된다.
• 실제로 완전한 형태의 최단경로 까지 알기 위해서는 별도의 로직이 추가적으로 사용되어야 한다. 다만 완전한 형태의 최단 경로까지 모두 출력하라고 요구하는 경우는 일반적인 코테 수준에서는 많이 출제되지 않는다.
• 다익스트라 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다.
• 처리 과정에서 더 짧은 경로를 찾으면 갱신하는 것을 반복한다.

다익스트라 알고리즘의 자세한 동작과정

• 그래프를 준비하고 출발 노드를 설정한다. 출발노드 자기 자신 이외에 무한으로 초기화한다.

• 이제부터 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 매번 선택해서 해당 노드를 거쳐가는 경로를 확인하여 테이블을 갱신한다.
• 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드를 처리한다.

• 1번 노드를 거쳐갈 때의 비용과 현재까지의 비용을 비교해서 더 짧은 거리로 테이블을 갱신한다.
• 인접한 노드를 하나씩 확인하면서 기존 테이블 정보를 이용하여 거리를 구하고 더 짧은 거리로 갱신한다.
• 위 예제에서는 1번 노드를 거쳐갈 때의 모든 경로를 확인한 결과로 테이블을 갱신한다.
• 다시 한번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번 노드를 처리한다.

• 4번 노드를 거쳐갈 때의 경로를 확인하기 위해서 4번 노드와 인접한 노드를 확인한다.
• 유의할 점은, 4번 노드까지 가기 위한 비용은 1로 결정이 되어서 더 이상 바뀌지 않는다.
• 다익스트라 알고리즘이 그리디한 방법으로 동작할 수 있는 이유는, 가장 최단 거리가 짧은 노드를 고를 때마다 해당 노드까지의 거리는 더이상 바뀌지 않는다는 점 때문이다.
• 다시 말해 4번 노드까지 도착하기 위한 최단거리는 1이기 때문에 이와 같이 4번 노드를 거쳐갈 때에 대한 비용을 고려할 때는 4번 노드까지의 비용인 1에 4번에서 3번 노드로 가기 위한 비용인 3을 더한 4를 비교하면 된다.
• 즉 이전 까지는 테이블에 담겨 있는 3번 노드까지의 최단거리값이 5였는데 이게 4보다 더 크기 때문에, 더 작은 값으로 갱신한다.
• 다음 단계도 마찬가지로 방문하지 않은 노드 중에서 가장 최단거리비용이 작은 노드를 선택한다. 최단 거리 비용이 같은 것이 2개 이상일 때 일반적으로 더 번호가 낮은 노드부터 선택해서 처리한다.

• 여기서도 2번 노드까지의 최단 거리 비용은 변하지 않는다. (2)
• 여기서 이미 방문 처리된 노드라면(위 예제에서는 4번 노드), 무시하는 방법을 사용할 수 있다.
• 왜냐하면 이미 방문처리가 된 노드는 그 노드까지의 최단거리 값이 이미 결정되어 바뀌지 않기 때문이다.
• 이후 또한 방문하지 않은 노드 중에서 현재까지의 최단 거리 값이 가장 작은 노드를 선택하고 위 과정을 반복한다.

• 마지막 노드는 처리하지 않아도 괜찮다.
• 왜냐하면, 앞서 확인했던 다른 노드까지의 최단거리 값은 더 이상 바뀌지 않기 때문에 다익스트라 알고리즘을 수행할 때 마지막 노드에 대한 정보는 처리하지 않아도 전체 결과를 얻을 수 있다.

다익스트라 알고리즘의 특징

• 그리디 알고리즘에 속한다. 즉 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복한다.
  • 임의의 과정이란 해당 노드를 거쳐가는 각각의 경우를 확인해서 테이블을 갱신할지 안할지를 결정하는 과정이다.

  • 단 총 비용은 고려하지 않는다. 즉 다익스트라가 최소 신장 트리를 보장하지 않는다는 것이다. 이는 반대도 마찬가지다.

    이미지 출처: https://sojeong-lululala.tistory.com/137

• 단계를 거치며 한 번 방문 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
  • 따라서 한 단계당 하나의 노드에 대한 최단 거리는 확실히 찾는 것으로 이해할 수 있다.
  • 이러한 이유로 그리디 알고리즘을 이용해서 최적의 해를 구할 수 있다는 정당성이 있다.
• 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
• 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 한다.

다익스트라 알고리즘 구현

• 매 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)한다.

# 간단한 다익스트라 알고리즘 구현
# 노드의 개수 n, 간선의 개수 m
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트
visited = [False] * (n+1)
# 최단 거리 테이블
distance = [1e9] * (n+1)

# 그래프 내용 채우기(간선 정보 입력받기)
for _ in range(m):
    a, b, c = map(int, input().split())
    # a 번 노드에서 b 번 노드로 가는 비용이 c 라는 의미
    graph[a].append((b, c))
    
# 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = 1e9
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index += 1
    return index
    
# 다익스트라 최단 거리 알고리즘
def dijkstra(start):
    # 시작 노드 초기화
    distance[start] = 0
    visited[start] = True

    # 출발 노드로부터 당장 도달이 가능한 다른 노드까지의 거리를 먼저 갱신
    for j in graph[start]:
        distance[j[0]] = j[1]
        
    # 시작 노드를 제외한 전체 n-1 개의 노드에 대해 반복
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smalledst_node()
        visited[now] = True
        
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
        
            # 현재 선택된 노드까지의 거리(distance[now]) 값에 현재 노드와
            # 연결된 거리 값을 더해서 cost 를 만든다.
            cost = distance[now] + j[1]
            
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 갱신
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == 1e9:
        print("INFINITY")
    else:
        print(distance[i])

• 맨 처음 테이블 초기화시 무한 값을 넣는다.
• 다익스트라 알고리즘을 간단히 구현한 위 방법의 성능을 분석해보자.
  • 총 $O(V)$ 번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다.
  • 따라서 전체 시간 복잡도는 $O(V^2)$ 이다.
  • 여기서 $V$ 는 노드의 개수를 의미한다.
  • 일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 이 코드로 문제를 해결할 수 있다. 그러나 노드의 개수가 10,000개가 넘어가면 효율성 테스트를 통과하지 못할 수 있다.
  • 즉 간단한 방법으로 매번 최단 거리가 가장 짧은 노드를 선형탐색하는 경우 시간 초과 판정을 받을 수 있기 때문에 효율적으로 동작하는 알고리즘을 설계할 필요가 있다.

우선순위 큐(Priority Queue)

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.
• 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인하는 경우 우선순위 큐를 활용할 수 있다.
• 파이썬, C++, Java 를 포함한 대부분의 프로그래밍 언어에서 우선순위 큐를 표준 라이브러리 형태로 지원한다.
• 힙(Heap)
  • 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나이다.
  • 최소 힙과 최대 힙이 있다.
    • 최소 힙은 값이 낮은 데이터부터 꺼내는 방식으로 동작한다.
    • 최대 힙은 값이 높은 데이터부터 꺼내는 방식으로 동작한다.
  • 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.
  • 힙은 데이터를 삽입하거나 삭제할 때 $O(logN)$ 만큼의 시간 복잡도가 소요된다.
• 만약 우선순위 큐를 구현하기 위해서 단순하게 리스트를 이용한다면 데이터를 삽입할 때는 데이터를 맨 뒤에 차례대로 넣으면 되기 때문에 $O(1)$ 의 상수시간이 걸리지만, 데이터를 삭제할 때는 전체 데이터를 순회하며 우선순위가 가장 높은 데이터가 무엇인지 확인해야 하기 때문에 $O(N)$ 의 선형시간이 걸린다.
• 반면에 힙은 내부적으로 트리 구조를 이용하여 데이터의 삽입과 삭제에 있어서 $O(logN)$ 만큼의 수행시간을 보장할 수 있는 형태로 구현된 자료구조이다.
• 힙을 이용해서 우선순위 큐를 구현하게 되면 삽입과 삭제에 있어서 모두 $O(logN)$ 만큼의 수행시간이 걸린다.
• 힙을 활용한 우선순위 큐(heapq)는 데이터를 꺼낼 때 우선순위가 높은 데이터부터 차례대로 나온다는 특징 때문에 힙 자료구조의 특성을 이용해서 정렬을 수행할 수 있다.
• 파이썬에서 heapq 는 최소 힙이 기본이기 때문에, 힙에 모든 데이터를 넣었다가 힙에서 모든 데이터를 다 꺼내면, 그렇게 꺼내진 데이터 순서 자체가 오름차순 정렬이 이루어진 형태가 된다.
• 힙 정렬은, 힙 자료구조가 데이터 삽입 및 삭제가 $O(logN)$ 이기 때문에, N개의 모든 데이터를 넣었다가 빼서 정렬하는 전체 시간 복잡도가 $O(NlogN)$ 이 된다.
• 이는 기본적으로 표준 라이브러리 단에서 제공하는 병합 정렬 혹은 퀵 정렬 기반의 정렬 알고리즘과 동일한 시간 복잡도이다. 따라서 힙 정렬 또한 단순히 힙에 데이터를 모두 넣었다가 꺼내는 과정 만으로 최악의 경우에도 $O(NlogN)$을 보장할 수 있다.

다익스트라 알고리즘 개선된 구현

• 기존의 단순한 형태의 다익스트라 알고리즘에 수행시간을 개선시키기 위해서 힙 자료구조를 사용한다.
• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용한다.
• 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다.
• 그러나 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용한다는 점이 다르다.
• 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
• 즉, 개선된 다익스트라 알고리즘은 우선순위 큐(힙 자료구조)를 사용한 다익스트라 알고리즘이다.
• 그래프를 준비하고 출발 노드를 설정하여 우선순위 큐에 삽입한다.
• 우선순위 큐에는 (거리, 노드) 의 튜플로 넣어서 거리값에 따라 최소 힙으로 동작하도록 한다.
• 매 단계에서 우선순위 큐에서 원소를 꺼내서 해당 노드까지의 거리를 확인한 뒤에 그 노드를 거쳐가는 각각의 경우까지 모두 고려하면 된다.

• 우선순위 큐에서 원소를 꺼내고 방문처리 한 후 처리한다. 갱신이 일어날 때만 갱신된 노드를 우선순위 큐에 담아주면 된다.
• 우선순위 큐에서 다음 원소를 꺼냈는데, 이미 방문처리된 노드가 꺼내졌다면 무시한다. 이 때 별도로 방문 여부를 기록하는 하나의 테이블을 사용하지 않고, 단순히 최단 거리 테이블과 비교해서 현재 테이블에 기록된 노드의 거리값보다 꺼낸 원소의 거리값이 더 크면 무시하도록 만드는 방법이 사용될 수 있다. 이미 방문처리된 노드라고 간주할 수 있기 때문이다.

# 우선순위 큐를 활용한 개선된 다익스트라 알고리즘 구현
import heapq

# 노드의 개수 n, 간선의 개수 m

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]
# 최단 거리 테이블 (무한으로 초기화)
distance = [1e9] * (n+1)

# 그래프 내용 채우기(간선 정보 입력받기)
for _ in range(m):
    a, b, c = map(int, input().split())
    # a 번 노드에서 b 번 노드로 가는 비용이 c 라는 의미
    graph[a].append((b, c))
    
# 다익스트라 최단 거리 알고리즘
def dijkstra(start):
    queue = []
    
    # 시작노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    # queue 가 비어있지 않다면
    while queue:
    
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                
                # 값이 갱신되면 우선순위 큐에 해당 정보 기록
                heapq.heappush(queue, (cost, i[0]))

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == 1e9:
        print("INFINITY")
    else:
        print(distance[i])

개선된 구현방법(우선순위 큐) 성능 분석

• 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 $O(ElogV)$ 이다.
  • $E$ 는 간선의 개수, $V$ 는 노드의 개수를 의미한다.
  • 노드를 하나씩 꺼내 검사하는 반복문(while문 안의 for문)은 노드의 개수 $V$ 이상의 횟수로는 처리되지 않는다.
    • 즉 큐에서 원소를 꺼내서 해당 노드를 처리할지 안할지를 결정할 때 현재의 노드가 이미 처리가 된 적 있는 노드라면 이를 무시할 수 있도록 하기 때문에, while 문 안의 for 문은 노드의 개수 이상의 횟수로 처리되지 않는다.
    • 또한 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는(for 문의 연산) 최대 간선의 개수(E) 만큼 연산이 수행될 수 있다.
• 직관적으로 전체 과정은 $E$ 개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.
  • 그러면 시간복잡도를 $O(ElogE)$ 로 판단할 수 있다.
  • 중복 간선을 포함하지 않는 경우에 이를 $O(ElogV)$로 정리할 수 있다.
    • 즉 두 노드 사이에서 존재할 수 있는 간선이 오는 간선과 가는 간선 두 개 까지만 존재할 수 있다고 했을 때 전체 간선의 개수($E$)는 노드의 개수의 제곱($V^2$) 이하의 값이 될 것이다.
    • $O(ElogE)$ → $O(ElogV^2)$ → $O(2ElogV)$ → $O(ElogV)$
• 결과적으로 우선순위 큐를 이용했을 때 다익스트라 알고리즘의 시간 복잡도는 $O(ElogV)$ 가 되며, 통상적으로 간선의 개수가 10만개, 20만개, 노드의 개수가 1만개 이상으로 많아진다고 하더라도 대개 1초 안쪽의 시간으로 출발 노드부터 다른 모든 노드까지의 최단 거리를 구할 수 있다.

플로이드 워셜(Floyd warshall) 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
• 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
  • 다만 다익스트라와 다르게 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
• 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 즉 2차원 테이블에 모든 노드에서부터 다른 모든 노드로 이동하는 최단 거리 정보를 기록한다.
• 2차원 테이블에 기록된 값을 점화식에 따라서 갱신한다는 점에서 플로이드 워셜 알고리즘은 DP 유형에 속한다.
• 실제로 점화식에 맞게 3중 반복문을 이용해서 2차원 테이블을 갱신해주는 방식으로 동작한다.
• 실제 알고리즘 구현 난이도는 다익스트라 알고리즘에 비해 쉬운 편이다.
• 하지만 모든 노드에서 다른 모든 노드까지의 최단 거리를 구하는 과정에서 시간 복잡도는 $O(N^3)$ 이다.
• 실제 문제 풀이에서는 노드의 개수가 적은 상황에서 효과적으로 사용할 수 있다. 노드의 개수 및 간선의 개수가 많은 경우에는 일반적으로 다익스트라 알고리즘을 사용해야 해결할 수 있는 경우가 많다.
• 플로이드 워셜 알고리즘 점화식
  • 각 단계마다 특정한 노드 k 를 거쳐 가는 경우를 확인한다.
  • 즉 특정한 노드를 거쳐갔을 때를 기준으로 해서 테이블을 갱신한다는 점은 다익스트라 알고리즘과 유사성이 있다.
  • 다만 플로이드 워셜 알고리즘은 a 에서 b 로 가는 최단 거리보다 a 에서 k 를 거쳐 b 로 가는 거리가 더 짧은지 검사하는 것이다.
  • $D_{ab} = min(D_{ab}, D_{ak}+D_{kb})$

플로이드 워셜 알고리즘 동작 과정

• 그래프를 준비하고 최단 거리 테이블을 초기화한다. 초기 상태에는 인접한 노드만 확인해서 테이블을 초기화한다.

  

• 각 노드를 거쳐가는 경우를 확인하여 테이블을 갱신한다. 먼저 1번 노드를 거쳐가는 경우를 고려해서 테이블을 갱신한다.

  

  • 1번 노드를 거쳐가는 경우를 확인하고 있기 때문에 1번에 대한 정보는 갱신되지 않는다. 또한 자기 자신에서 자기 자신으로 가는 테이블의 대각선 부분도 갱신되지 않는다.
  • 기존의 모든 최단 거리에 대해서 1번 노드를 거쳐가는 거리값과 비교하여 더 작은 값이 들어갈 수 있도록 테이블을 갱신하는 것이다.

• 2번 노드, 3번 노드, 4번 노드도 마찬가지로 해당 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

  

• 즉 k 라는 변수를 이용해서 모든 노드에 대해서 하나씩 확인하며, 해당 노드를 거쳐가는 경우를 고려할 수 있도록 하고, 그 때마다 매번 모든 a 와 b 에 대해서 점화식을 갱신하기 때문에 실제로 이를 구현할 때 3중 반복문을 이용해서 코드로 구현할 수 있다.

INF = int(1e9) # 무한

# 노드의 개수 n, 간선의 개수 m
# 2차원 리스트(그래프 표현)를 만들고 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in rnage(1, n+1):
        if a == b:
            graph[a][b] = 0
            
# 각 간선에 대한 정보를 입력받고 그 값으로 초기화
for _ in range(m):
    # A 에서 B 로 가는 비용은 C 라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c
    
# 점화식에 따라 플로이드 워셜 알고리즘 수행 (3중 반복문)
# k 는 거쳐가는 노드, a 는 출발 노드, b 는 도착 노드
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == INF:
            print("INFINITY")
        else:
            print(graph[a][b])

플로이드 워셜 알고리즘 성능 분석

• 노드의 개수가 N 개 일 때 알고리즘 상으로 N 번의 단계를 수행한다.
  • 각 단계는 각 노드를 거쳐가는 경우를 확인하는 것이다.
  • 각 단계마다 $O(N^2)$ 의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
• 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 $O(N^3)$ 이다.
• 이러한 이유로 실제로 플로이드 워셜이 사용되어야 하는 문제에서는 노드의 개수가 500개 이하로 구성된다.
• 노드의 개수가 500개가 된다고 해도, 500 * 500 * 500 은 1억이 넘어가기 때문에 시간초과 판정을 받을 수도 있다.
• 따라서 최단 거리를 구해야 하는 문제가 출제되었을 때 다익스트라, 플로이드 워셜 등 다양한 알고리즘 중에서 어떤 알고리즘을 사용하는 것이 적절한지 고민해야 한다.
• 노드와 간선의 개수가 충분히 크다면 우선순위 큐를 활용한 다익스트라 알고리즘을 구현해보자.

벨만 포드(Bellman-Ford) 알고리즘

• 벨만 포드 알고리즘이 효과적으로 사용될 수 있는 상황은 음수 간선이 포함된 상황에서의 최단 거리 문제이다.
• 예시 : N 개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M 개 있다. 각 버스는 A, B, C 로 나타낼 수 있는데, A 는 시작도시, B 는 도착도시, C 는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C 가 양수가 아닌 경우가 있다. C=0 인 경우는 순간 이동을 하는 경우, C<0 인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
  • 도시의 개수 : N(1≤N≤500)
  • 버스 노선의 개수 : M(1≤M≤6,000)
• 이 문제는 간선이 음수가 될 수 있다는 조건을 제외하면 일반적인 다익스트라 알고리즘과 같은 조건이다.
• 즉, 모든 간선 비용이 양수일 때는 다익스트라 최단 경로 알고리즘을 사용하면 된다. 다익스트라 알고리즘을 이용하면 특정 노드에서 다른 모든 노드까지의 최단 거리를 구할 수 있다.
• 음수 간선이 있어도 최단 경로를 못 구하는 것은 아니다.
• 하지만 음수 간선의 순환이 포함된다면 최소 비용을 특정한 값으로 결정할 수 없는 경우가 발생할 수 있다. 음수 간선의 순환이 포함된다면 최단 거리가 음의 무한인 노드가 발생할 수 있다.

• 음수 간선이 포함된 사이클을 무한히 반복하면 비용을 무한히 줄일 수 있기 때문이다.
• 이렇게 특정한 그래프에서 최단 거리를 찾을 때 음수 순환이 포함되어 있는지를 체크하고자 한다면 어떤 알고리즘을 써야할까?
• 벨만 포드 최단 경로 알고리즘
  • 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다.
    • 모든 간선이 양수인 경우
    • 음수 간선이 있는 경우
      • 음수 간선 순환은 없는 경우
      • 음수 간선 순환이 있는 경우
  • 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다.
  • 또한 음수 간선의 순환을 감지할 수 있다.
  • 벨만 포드 알고리즘의 기본적 시간 복잡도는 정점의 개수와 간선의 개수의 곱인 $O(VE)$ 로 다익스트라 알고리즘에 비해 느리다.

벨만 포드 알고리즘의 동작 원리

• 다익스트라 알고리즘과 유사하다.
  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다.
  3. 다음의 과정을 N-1 번 반복한다.
  4. 전체 간선 E 개를 하나씩 확인한다.
  5. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 비용이 더 작아진다면 그 비용이 기록될 수 있도록 최단 거리 테이블을 갱신한다.
• 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다.
• 이 때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.
• 다익스트라 알고리즘도 N-1 번 반복을 진행하되, 이 때 모든 간선을 다 확인하지는 않고 특정 노드의 붙어있는 간선만 확인한다. 즉 벨만 포드 알고리즘보다 더 적은 만큼만 간선을 확인한다.
• 이는 벨만 포드 알고리즘이 다익스트라 알고리즘의 솔루션을 포함한다는 이야기가 된다. 따라서 다익스트라 알고리즘과 같은 기능을 보장할 수는 있지만 더욱 더 많은 간선 확인이 있어서 시간 복잡도가 더 높게 소요된다.

다익스트라 알고리즘 vs. 벨만 포드 알고리즘

• 다익스트라 알고리즘
  • 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  • 음수 간선이 없다면 최적의 해를 찾을 수 있다.
• 벨만 포드 알고리즘
  • 매번 모든 간선을 전부 확인한다. 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.
  • 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있다.

벨만 포드 알고리즘 구현

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

def bellman_ford(start):
    # 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n 번의 라운드(round)를 반복
    for i in range(n):
        # 매 반복마다 모든 간선을 확인
        for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                # n 번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n-1:
                    return True
    return False
    
# 노드의 개수, 간선의 개수
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
dist = [INF] * (n+1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a 번 노드에서 b 번 노드로 가는 비용이 c 라는 의미
    edges.append((a, b, c))
    
# 벨만 포드 알고리즘 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드

if negative_cycle:
    print("-1")
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
    for i in range(2, n+1):
        # 도달할 수 없는 경우, -1 을 출력
        if dist[i] == INF:
            print("-1")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(dist[i])

맨 위로 이동 ↑