최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.
여러 유형이 있는데, 그 중 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 공부하겠다.
1. 다익스트라 알고리즘
(1) 이론
다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작한다.
동작원리는 다음과 같다.
1) 출발 노드를 설정한다.
2) 최단 거리 테이블을 초기화한다.
3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5) 3, 4번을 반복한다.
3번의 과정에 대해서 그리디 알고리즘으로 볼 수 있다.
출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리 저장하기 위해 1차원 리스트를 이용하였다.
파이썬 heapq 라이브러리에서는 최소 힙을 따르기 때문에 pop()을 하면 가장 우선순위가 낮은 원소가 나온다. 이 경우에는 가장 최단 거리가 짧은 원소가 꺼내진다.
한번 처리된 노드는 더이상 처리되지 않기 때문에 시간복잡도 O(ElogN)을 가진다. N은 노드의 개수, E는 간선의 개수이다.
(2) 코드
import heapq
import sys
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정
n, m = map(int, sys.stdin.readline().rstrip().split()) #노드의 개수 n, 간선의 개수 m 입력받기
start = int(input()) #시작 노드 번호 입력받기
graph = [ [] for _ in range(n + 1) ] #(노드의 개수 + 1)의 크기로 할당하여 노드의 번호를 인덱스로 하였다.
distance = [INF] * (n + 1) #최단 거리 저장하기 위한 리스트
for _ in range(m): #모든 간선 정보 입력받기
a, b, c = map(int, input().split())
graph[a].append((b, c)) #a번 노드에서 b번 노드로 가는 비용이 c라는 의미
def dijkstra(start):
distance[start] = 0 #시작 노드로 가기 위한 최단 경로는 0으로 설정
q = []
heapq.heappush(q, (distance[start], start)) #시작 노드에 대한 정보를 큐에 삽입
while q: #큐가 비어있지 않으면
dist, now = heapq.heappop(q) #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
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(q, (cost, i[0]))
dijkstra(start) #다익스트라 알고리즘 수행
for i in range(1, n + 1): #모든 노드로 가기 위한 최단 거리 출력
if distance[i] == INF: #도달할 수 없는 경우, 무한 출력
print('INFINITY')
else: #도달할 수 있는 경우, 거리 출력
print(distance[i])
2. 플로이드 워셜 알고리즘
(1) 이론
플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 할 수 있는 알고리즘이다. 시간 복잡도는 O(N^3)이다.
플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.
다익스트라 알고리즘은 그리디 알고리즘으로 볼 수 있는데, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 알고리즘으로 볼 수 있다.
점화식은 다음과 같다. Dab = min(Dab, Dak + Dkb)
바로 이동하는 거리가 특정 노드를 거쳐서 이동하는 거리보다 더 많은 비용을 가진다면 이를 짧은 것으로 갱신한다는 것이다.
(2) 코드
INF = int(1e9) #무한을 의미하는 값으로 10억 설정
n, m = map(int, input().split()) #노드의 개수 n과 간선의 개수 m 입력받기
graph = [[INF] * (n + 1) for _ in range(n + 1)] #2차원 리스트를 만들고, 모든 값을 무한으로 초기화
for a in range(n + 1): #자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for b in range(n + 1):
if a == b:
graph[a][b] = 0
for _ in range(m): #각 간선에 대한 정보를 입력받아 저장
a, b, c = map(int, input().split())
graph[a][b] = c #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', end = ' ')
else:
print(graph[a][b], end = ' ')
print()
3. 실전 문제
(1) 미래 도시
Q
방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데, 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.
공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개 회사는 양방향으로 이동할 수 있다. 도로는 마하의 속도로 이동시켜주기 때문에 특정 회사와 다른 회사가 도로로 연결되어 있다면 정확히 1만큼의 시간으로 이동할 수 있다.
또한 방문 판매원 A는 X번 회사에 가서 물건을 팔기 전에 K번 회사에 가서 소개팅 상대랑 커피를 마실 예정이다.
따라서 방문 판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다. 가능한 한 빠르게 이동하는게 목표다.
입력조건
첫째 줄에 전체 회사 개수 N과 경로 개수 M이 공백으로 구분되어 주어진다(1<=N,M<=100).
둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
M+2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다.
출력조건
첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
만약 X번 회사에 도달할 수 없다면 -1을 출력한다.
A
N과 M의 범위가 100으로 한정되어 있고, 작기 때문에 구현이 쉬운 플로이드 워셜 알고리즘을 이용하여 풀었다. 리스트 크기를 n + 1로 설정했기 때문에 주어지는 숫자 그대로를 사용하여 인덱스에 넣을 수 있다.
코드
INF = int(1e9)
n, m = map(int, input().split()) #N과 M 입력받기
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for a in range(n + 1): #자기 자신에게 가는 경로는 0으로 초기화
for b in range(n + 1):
if a == b:
graph[a][b] = 0
for _ in range(m):
a, b = map(int, input().split())
graph[a][b] = 1 #경로가 연결되어 있으면 1의 시간으로 갈 수 있으므로 1로 설정
graph[b][a] = 1 #양 방향 이동가능하다는거 주의!!
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])
x, k = map(int, input().split()) #X와 K 입력받기
dist = graph[1][k] + graph[k][x] #최단 거리, 1번 회사로부터 출발이므로 [0]이 아니라 [1]로 시작하기!!
if dist >= INF: #X에 도달하지 못하는 경우라면 아직 INF로 되어 있을테니
print(-1)
else:
print(dist)
(2) 전보
Q
어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, X에서 Y로 향하는 통로가 설치되어 있어야 한다. 일방통행이며, 메시지 보낼때는 일정 시간이 소요된다.
어느 날 C라는 도시에 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 도시 C에서 보낸 메시지를 받게 되는 도시의 개수가 몇 개인지와 도시들이 메시지 받게되는데 걸리는 시간을 구하는 프로그램을 작성하시오.
입력조건
첫째 줄에 도시의 개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C가 주어진다(1<=N<=30000, 1<=M<=200000, 1<=C<=N).
둘째 줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X,Y,Z가 주어진다. 이는 특정 도시 X에서 Y로 이어지는 통로가 있으며, 메시지가 전달되는 시간이 Z라는 의미이다(1<=Z<=1000).
출력조건
첫째 줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.
A
플로이드 워셜 알고리즘을 이용하여 풀었다. 다익스트라 알고리즘을 이용하여 푸는 것도 시도해봐야 한다.
점화식에 따른 플로이드 워셜 알고리즘을 실행안했는데, 그 이유는 이 문제는 C에서 출발하는 것만을 구하면 되기 때문이다.
코드
INF = int(1e9)
n, m, c = map(int, input().split()) #N,M,C 입력
graph = [[INF] * (n + 1) for _ in range(n + 1)] #2차원 리스트 초기화
for a in range(n + 1): #자기자신에게 가는 최단 거리는 0으로 설정
for b in range(n + 1):
if a == b:
graph[a][b] = 0
for _ in range(m): #X,Y,Z에 대한 정보 입력
x, y, z = map(int, input().split())
graph[x][y] = z
count = 0
time = 0
for i in range(n + 1):
if graph[c][i] < INF and c != i: #C에서 다른 도시로 가는 통로가 있고, C가 자기 자신에게 가지 않는 경우
count += 1
time = max(time, graph[c][i]) #총 걸리는 시간이므로 더하는게 아니라 가장 오래 걸리는 시간을 측정
print(count, time, end = ' ')
