최단 경로 with 파이썬

in Algorithm on Basics

1. 개요

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 길 찾기 문제라고도 불린다. 최단 경로 알고리즘은 보통 그래프로 표현하는데, 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다. 학부 수준에서 사용되는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 3가지가 있다.

2. 다익스트라 최단 경로 알고리즘

데이크스트라라고도 불리는 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.
다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

  1. 출발 노드를 설정
  2. 최단 거리 테이블을 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
  5. 3,4과정을 반복

다익스트라 최단 경로 알고리즘에서는 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복하는데, 이렇게 선택된 노드는 최단 거리가 완전히 선택된 노드 이므로, 더이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다. 다시 말해 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다. 그렇기 때문에 사실 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다.

cf) 선택된 노드는 왜 최단 거리가 완전히 선택된 상태인가?
우선순위 큐로 인해 시작점으로부터 거리가 최소인 노드부터 선택되면서 시작점으로부터 해당 노드까지의 거리들이 계산된다. 따라서 해당 노드가 선택될 때는 이미 시작점으로부터 자신보다 더 작은 거리에 있는 모든 노드에서 계산이 마치고 자신의 순서로 온 것이다. 따라서 해당 노드가 선택될 때는 이미 최단 거리 선택이 완료된 상태가 되는 것이다. 이를 코딩의 조건으로 생각해자.
우선순위 큐에서 꺼낸 거리가 저장된 거리보다 크다면 해당 노드는 이미 처리가 완료된 노드라고 할 수 있다. 따라서 주변을 살피는 과정을 할 필요가 없다. 이미 전에 처리했으니 말이다. 하지만 저장된 거리보다 작다면 해당 노드는 아직 처리가 안 된 것이므로 처리를 진행하면 된다.

우선순위 큐

방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정은 우선순위 큐를 이용한다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있다. 따라서 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. PriorityQueue와 heapq 라이브러리를 사용할 수 있는데 일반적으로 heapq가 더 빠르게 동작하므로 heapq 사용을 권장한다. 우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용된다. 대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정 한다는 점도 알아두자.
우선순위 큐를 구현할 때는 내부적으로 최소 힙 혹은 최대 힙을 이용한다. 최소 힙을 이용하는 경우 값이 낮은 데이터가 먼저 삭제되며, 최대 힙을 이용하는 경우 값이 큰 데이터가 먼저 삭제된다. 파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용한다.
최소 힙을 최대 힙처럼 사용하기 위해서는 일부러 우선순위에 해당하는 값에 음수 부호를 붙여서 넣었다가 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호를 붙여서 원래 값으로 돌리는 테크닉을 자주 사용하므로 알아두자.
우선 순위 큐를 구현할 때는 힙 자료구조를 이용하는데 사실 단순히 리스트를 이용해서 구현할 수도 있다. 하지만 시간 복잡도에서 차이가 난다. 리스트를 이용해서 우선순위 큐의 기능을 구현하기 위해서는 삭제할 때마다 모든 원소를 확인해서 우선순위가 가장 높은 것을 찾아야 하므로 최악의 경우 O(N)의 시간이 소요된다.

우선순위 큐 구현 방식삽입 시간삭제 시간
리스트O(1)O(N)
힙O(logN)O(logN)

데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 해보자. 삽입에서는 O(logN)의 연산을 N번 수행하고 삭제할 때도 같다. 따라서 전체 시간 복잡도는 O(NlogN)이다.

구현

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 10억

# 노드의 개수, 간선의 개수
n,m = map(int,input().split())
start = int(input())

# 인덱스와 노드의 번호를 맞추기 위해서 +1
graph = [[] for i in range(n+1)]

# 최단 거리 저장 리스트
distance = [INF]*(n+1)

# 간선 정보 입력
for _ in range(m):
    # a에서 b로 가는데 필요한 비용 c
    a,b,c = map(int,input().split())    
    graph[a].append((c,b))

def dijkstra(start):
    q = []
    distance[start] = 0
    # 우선순위 큐는 첫 번째 데이터로 순위 결정하므로 비용을 먼저 
    heapq.heappush(q,(0,start))    
    while q:
        dist,now = heapq.heappop(q)       
        # 이미 처리된 경우는 무시
        # start지점의 경우 = 등호가 성립하므로 <=가 아니다.
        if distance[now]<dist:
            continue
        # 처리가 안 된 경우 이제 처리
        for cost,way in graph[now]:
            # 비용이 갱신된 경우에만 push
            # 등호가 들어가는 경우는 왜 하지 않는가? -> 어쩌피 최단 거리로 같은 곳에 도착했으니 다음부터 그곳에서 시작하는 경우는 어쩌피 거리가 같잖아.
            if distance[way]>dist+cost:
                distance[way]=dist+cost
                heapq.heappush(q,(cost+dist,way))

dijkstra(start)

# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1,n+1):
    # 도달 불가
    if distance[i] == INF:
        print("불가능")
    else :
        print(distance[i])    


# 입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

# 출력 예시
0
2
3
1
2
4

시간 복잡도

시간 복잡도는 O(ElogV)이다.(V는 노드 개수, E는 간선 개수)
위에서 설명했듯이 데이터의 개수가 N개일 때, 하나의 데이터를 삽입 및 삭제할 때의 복잡도는 O(logN)이다. 코드에서 확인할 수 있듯이 한 번 처리된 노드는 더 이상 처리하지 않는다. 따라서 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상의 횟수로는 반복되지 않는다. 또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다. 그러므로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드를 확인하는 총 횟수는 총 최대 간선의 개수 E만큼 연산이 수행될 수 있다.

3. 플로이드 워셜 알고리즘

다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있는 알고리즘이었다. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘이다. 다익스트라 알고리즘과 다른점은 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점과 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 1차원 리스트가 아닌 2차원 리스트가 필요하다는 점이다. 또한, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다. 노드의 개수가 N이라고 할 때, N번 만큼 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문이다.
각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 경우를 고려하면 된다. 좀 더 자세히 말하자면, A -> 1번 노드 -> B로 가는 비용과 A -> B로 가는 비용과 비교해서 최소 비용으로 리스트를 갱신하는 것이다.
알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1개의 노드 중에서 서로 다른 노드 (A,B)쌍을 선택한다. 쌍을 선택하는 방법은 N-1개에서 2개를 선택하는 순열과 같다. 그리고 위와 같이 비교해서 최소 비용을 갱신한다. 해당 순열을 모두 비교하고 이 과정을 N번 반복하면 모든 경우의 최소 비용이 작성된 2차원 리스트가 완성되는 것이다.
다이나믹 프로그래밍이라는 특징을 가지므로 점화식을 구하면 손쉽게 코딩할 수 있다. 여기서 괄호는 첫번째에서 두번째로 갈 때를 뜻한다. D(ab) = min( D(ab), D(ak)+D(kb) )
플로이드 워셜 알고리즘은 다익스트라 알고리즘과 다르게 음수 사이클의 존재를 감지할 수 있다. 로직을 수행한 뒤에 (i,i)가 음수라면 i에서 i로 되돌아오는 음수 사이클이 존재한다는 것을 의미한다.

import sys

input = sys.stdin.readline
INF = int(1e9) # 연결 불가능 INFINITY

# 노드와 간선의 개수
n = int(input())
m = int(input())

# 기본 그래프 형성, 모두 연결 불가능으로 초기화
graph = [[INF]*(n+1) for i in range(n+1)]

# 같은 곳은 0
for i in range(1,n+1):
    graph[i][i]=0

# 그래프 정보 입력
for _ in range(m):
    # a에서 b로 가는 비용 c
    a,b,c = map(int,input().split())
    graph[a][b]=c

# 플로이드 워셜 알고리즘 수행
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):
        if graph[a][b] == INF:
            print("INFINITY")
        else :
            print(graph[a][b],end=" ")
    print()

# 입력 예시
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

# 출력 예시
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0


시간 복잡도

N-1개에서 2개를 선택하는 순열의 복잡도는 O(N^2)이다. 이 과정을 N번 반복해야하니 총 복잡도는 O(N^3)이다.

4. 벨만 포드

그림1

벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다는 점에서 앞선 알고리즘들과 차이가 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 시간 복잡도는 O(VE) 이다. 동작원리는 다음과 같다.

  1. 출발 노드 지정
  2. 최단 거리 테이블 초기화
  3. 다음 과정을 n-1번 반복
    • 전체 간선 E개를 하나씩 확인
    • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  4. 음의 간선 순환이 발생하는지 체크하고 싶다면 3번의 가정을 1번 더 수행하여 최단 거리 테이블이 갱신된다면 음의 간선 순환이 존재하는 것으로 인지

n-1번 반복하는 이유는 최단 거리는 최대 v-1개의 간선을 지나가기 때문이다.

INF = int(1e9)


def bf(start):
    dis[start] = 0  # 시작 지점 초기화

    # 매 반복마다 모든 간선 확인
    # 음의 간선 사이클 존재 유무가 필요하면 n번과 return 처리
    # 필요 없다면 n-1번과 리턴 처리는 필요 없음 dis 테이블만 필요함
    for i in range(n):
        # 모든 간선 확인
        for j in range(m):
            current = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # 시작위치에서 현재 노드까지 이동이 가능하면서
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은경우
            if dis[current] != INF and dis[next_node] > cost + dis[current]:
                dis[next_node] = dis[current] + cost
                # 싸이클 유무 확인을 위해 n번 돌렸을 때
                # 최단 거리 갱신이 발생하면 음의 사이클이 존재
                if i == n - 1:
                    return True
    return False


# 노드, 간선 개수
n, m = map(int, input().split())

edges = []
dis = [INF] * n  # 최단 거리 테이블

# 간선 정보
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))

cycle = bf(1)
if cycle:  # 음의 사이클 발생
    print(-1)
else:
    # 1번 노드에서 시작했으니 다른 노드로 가기 위한 최단 거리 출력
    for i in range(2, n + 1):
        if dis[i] == INF:
            print(-1)
        else:
            print(dis[i])


음의 싸이클

위에서 작성한 정석적인 벨만 포드 알고리즘에서는 음의 간선이 주어진 경우 특정한 위치에서 모든 노드까지의 최단 거리를 구할 수 있었고, for문을 한 번 더 돌려 최단 거리 테이블이 변경된다면 시작지점을 기준으로 모든 노드로 진행되는 최단 거리에서 음의 싸이클이 존재한다는 것을 알 수 있었다. 이렇게 시작지점이 주어지고 그 시작점에서의 최단 거리에서 음의 싸이클의 존재를 판단하는 경우는 그냥 위 코드처럼 설계하면 된다.
하지만 음의 간선이 주어진 그래프에서 시작지점에 관계없이 그저 음의 싸이클이 존재하는지만 판단하는 경우는 위 코드처럼 작성할 경우, 모든 노드를 시작지점으로 지정 해서 for문을 돌려야 한다. 다른 언어의 경우는 몰라도 파이썬의 경우는 최적화가 필요한 언어이다. 따라서 모든 경우를 돌려보면 문제상 시간초과가 발생하는 경우가 생길 것이다. 이 경우에는 벨만 코드 알고리즘에서 조건만 약간 변형시키면 된다.
if문의 조건으로 dis[current] != INF을 제외시키고, df의 인자로 아무 시작지점이나 넣어주면 그래프의 주어진 간선 정보로 음의 싸이클이 존재하는지를 판단할 수 있다. dis[current] != INF 조건을 준 이유는 bf알고리즘 처음에 dis[start]를 0으로 초기화해주면서 시작지점으로부터 연결된 노드만을 거리 갱신하기 위한 조건이었다. dis[current] != INF 조건이 없으면 시작 위치와 연결되지 않더라도 거리들이 갱신되기 시작한다. 하지만 이 경우에는 최단 거리 테이블의 목적으로 만들어진 dis가 의미를 상실하게 된다. 이때부터 dis는 음의 싸이클의 유무를 판단하는 용도로만 사용된다. n번째 루프를 돌 때 갱신된다면 음의 싸이클이 존재한다고만 판단하는 용도가 되는 것이다.
정리하자면, 음의 간선이 주어진 그래프에서 시작 지점에 관계없이 음의 싸이클의 존재 유무를 판단해야 하는 경우, 벨만 포드 알고리즘에의 if조건문에서 시작위치와의 연결을 판단하기 위해서 작성했던 dis[current] != INF조건을 삭제해주고, 아무 시작 지점이나 인자로 넣어주면 된다.


5. 실전 문제

문제 : 미래 도시

판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 연결된 2개의 회사는 양방향으로 이동할 수 있고 비용 시간은 1이다.
판매원 A는 X번 회사에 방문하기 전에 K번째 회사에 방문하고자 한다. 이때 판매원이 최소 이동 시간을 계산하는 프로그램을 작성하시오.
입력 조건

  • 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 주어진다. (1<=N,M<=100)
  • 둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
  • M+2번째 줄에는 X와 K가 공백으로 구분되어 차례로 주어진다. (1<=K<=100)

출력 조건

  • 첫째 줄에 판매원 A가 K번째 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력하시오.
  • 만약 X번 회사에 도달할 수 없다면 -1 출력
입력 예시
5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

출력 예시
3

풀이

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = int(1e9) # 연결 불가능
graph = [[INF]*(n+1) for i in range(n+1)]

for _ in range(m):
    # a와 b는 연결되어 있다.
    # 시간 비용은 1
    a,b = map(int,input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 자기 자신으로 가는 경우는 0으로 초기화
for i in range(1,n+1):
    graph[i][i]=0  

x,k =map(int,input().split())

# 플로이드 워셜
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])

# 1에서 K로 가는 최단거리 + K에서 X로 가는 최단거리            
final_way = graph[1][k]+graph[k][x]
if final_way >= INF:
    print(-1)
else :
    print(final_way)


문제 : 전보

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y를 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다.
어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 걸쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데 까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.
입력 조건

  • 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C가 주어진다. (1<=N<=30,000 , 1<= M <= 200,000 , 1<= C <=N)
  • 둘째 줄부터 M+1 번째 줄에 걸쳐서 통로에 대한 정보 X, Y, Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메시지가 전달되는 시간 Z라는 의미이다. (1<=X,Y<=N , 1<=Z<=1,000)

출력 조건

  • 첫째 줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력
입력 예시
3 2 1
1 2 4
1 3 2
출력 예시
2 4

풀이

import heapq
import sys
input = sys.stdin.readline

# 도시 개수n, 통로 개수 m, 메시지 보내고자하는 도시 c
n,m,c = map(int,input().split())
INF = int(1e9) # 연결 불가능

# 도시 연결
graph = [[] for i in range(n+1)]

# C도시를 기준으로 다른 도시로 이동 거리  
distance = [INF]*(n+1)

# 도시 연결 입력
for _ in range(m):
    # x에서 y로 이어지는 통로 시간비용 z
    x,y,z = map(int,input().split())
    graph[x].append((z,y))

def dijkstra(start):
    q = []    
    count = 0 # 메시지 받은 도시 개수
    heapq.heappush(q,(0,start))
    distance[start]=0
    while q:
        cost, now = heapq.heappop(q)
        # 이미 처리된 경우
        if cost > distance[now]:
            continue
        count+=1
        max_time = cost
        for i in graph[now]:                        
            if distance[i[1]]>cost+i[0]:                
                distance[i[1]]=cost+i[0]
                heapq.heappush(q,(distance[i[1]],i[1]))
        # 시작점은 count에서 제외         
    return count-1, max_time
    # 마지막으로 선택되서 for문에 들어오는 경우는 최소거리가 가장 큰 것이다.
    # 우선순위 큐의 사용으로 최소거리가 가장 작은 것부터 선택된다.
    # 따라서 가장 마지막에 뽑혔다는 것은 다른 노드는 최소 거리가 이미 다 결정되었다는 뜻이고 
    # 사실상 마지막 수행되는 for문은 의미가 없다.    
    # 즉, 마지막 for문에서의 선택된 노드의 해당 거리는 제일 먼 것이다.
    # 또한 해당 노드가 선택되어 이미 처리된 경우가 아니라면 해당 노드까지의 거리는 다 정해진 것이고
    # 더 이상 방문하지 않게 되므로 카운트 한다.
a,b=dijkstra(c)
print(a,b)

"""
모범 답안에서는 return으로 count와 max_time을 보내지 않고
다익스트라 알고리즘을 수행한 후 완성된 distance를 가지고 처리했다.
count =0
max_time = 0
for d in distance:
    if d!=INF:
        count+=1
        max_time = max(max_time,d)
# 시작노드는 제외해야하므로 -1
print(count -1,max_time)
"""


© 2021. By Backtony