최단 경로 찾기 알고리즘 (다익스트라 / 플로이드 워셜) (python)

 

최단 경로를 찾는 알고리즘 중 대표적인 두가지로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 있습니다.

 

다익스트라 알고리즘

 

- 개념

다익스트라 알고리즘은 출발 노드에서 특정 노드로 가는 최단 경로를 구할 때 사용할 수 있는 알고리즘입니다.

 

출발 노드부터 시작해 그 노드에서 갈 수 있는 모든 방문하지 않은 노드를 방문 비용이 낮은 것 부터 확인하며 최단 거리 테이블을 갱신해 나가는 방식으로 최단 경로를 구해 나가며, 방문 비용이 낮은 것을 확인하기 위해 heap을 사용하는 것이 특징입니다.

 

다익스트라 알고리즘의 시간 복잡도는 최대 간선의 개수를 E, 노드의 개수를 V 라고 했을 때 O(ElogV) 입니다.

 

- 구현

다익스트라 알고리즘 구현은 대표적인 유형인 백준 최소비용 구하기 문제를 예시로 풀며 진행하겠습니다. 

 

1916번: 최소비용 구하기

	# 다익스트라 알고리즘을 효율적으로 구현하기 위해선 최소 힙을 활용해야 하므로 heapq를 import 해줍니다
	import heapq
	# 입력 데이터가 많은 경우를 대비하여 input을 좀 더 빠르게 동작하게 만드는 sys.stdin.readline을 사용합시다
	import sys
	input = sys.stdin.readline
	# 노드와 간선의 갯수를 입력 받은 다음
	n = int(input())
	m = int(input())
	# 각 노드에 연결되어 있는 노드 정보를 담을 리스트를 만들어주고
	graph = [[] for _ in range(n + 1)]
	# 무한을 의미하는 상수를 우선 선언해 준 다음
	INF = int(1e9)
	# 그 노드에 도달할 수 있는 최소 비용을 저장할 테이블을 무한을 기본값으로 하여 선언해줍니다.
	distance = [INF] * (n + 1)
	# 간선의 갯수만큼 반복해주며
	for _ in range(m):
	# 출발 도시 번호, 도착 도시 번호, 버스 비용 정보를 입력받아
	a, b, c = map(int, input().split())
	# 출발 도시 번호 노드에 도착 도시 번호와 버스 비용 정보를 저장해줍니다.
	graph[a].append((b, c))
	# 이제 다익스트라 함수를 정의해봅시다
	def dijkstra(start):
	# 큐를 하나 선언해서
	q = []
	# 시작 노드 정보와 거기 까지 갈 때 드는 비용 0을
	# 최소 힙이 비용을 기준으로 동작할 수 있게 비용이 앞으로 오게 집어 넣어 우선 순위 큐로 만들어준 다음
	heapq.heappush(q, (0, start))
	# 큐에 값이 있는 동안 반복하며
	while q:
	# 큐에 있는 노드 정보 중 가장 비용이 작은 노드 정보를 꺼내와
	# (최소힙이기 때문에 자동으로 가장 비용이 작은 정보가 출력됩니다)
	dist, now = heapq.heappop(q)
	# 그 비용이 이미 그 노드의 거리 정보에 저장된 값보다 크면 무시하고
	if distance[now] < dist:
	continue
	# 그렇지 않다면 이 노드에서 갈 수 있는 다른 노드 정보들을 확인해
	for target, target_cost in graph[now]:
	# 이 노드까지 오는 비용과 이 노드에서 갈 수 있는 다른 노드까지 가는 데 드는 비용까지 더한 다음
	cost = dist + target_cost
	# 그게 거리 정보 테이블에 저장된 값보다 작다면
	if distance[target] > cost:
	# 갱신해주고
	distance[target] = cost
	# 다음 노드에서도 이를 반복할 수 있게 힙에 그 정보를 넣어줍니다.
	heapq.heappush(q, (cost, target))
	# 출발 노드와 도착 노드 정보를 받아 온 다음
	s, e = map(int, input().split())
	# 출발 노드 정보를 인자로 넣어 dijkstra 함수를 실행하고
	dijkstra(s)
	# dijkstra 함수가 실행되며 갱신된 거리 정보 테이블에서 도착 노드 부분에 저장된 정보를 출력합니다
	print(distance[e])

view raw dijkstra.py hosted with ❤ by GitHub

 

플로이드 워셜

 

- 개념

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구할 수 있는 알고리즘입니다. 

 

노드의 개수를 n이라고 했을 때 n만큼 3중으로 반복하며 모든 노드에 대한 모든 노드의 최단 거리를 저장하는 2차원 배열을 갱신해 나가기 때문에 플로이드 워셜 알고리즘의 시간 복잡도는 O(n^3) 입니다.

 

- 구현

11404번: 플로이드

	# 무한으로 사용할 상수 값을 정의해주고
	INF = int(1e9)
	# 도시 (노드)와 버스 (간선)의 갯수를 입력받습니다.
	n = int(input())
	m = int(input())
	# 자기 자신부터 n번 도시까지의 최단 거리를 저장하는 걸
	# 1번부터 n번 도시까지 모두 해줘야하므로
	# 초기값이 무한이고 크기가 n * n인 2차원 배열을 선언해줍니다.
	graph = [[INF] * (n + 1) for _ in range(n + 1)]
	# 그 도시에서 그 도시로 가는 건 거리가 0이니 2중 반복문을 돌며 0으로 저장해줍니다
	for r in range(n + 1):
	for c in range(n + 1):
	if r == c:
	graph[r][c] = 0
	# 간선의 갯수만큼 반복하며 a도시에서 b도시까지 갈 때의 비용 c를 저장해줍니다.
	# 이 때 c가 graph[a][b]에 이미 저장된 값 보다 크다면 저장할 필요가 없으므로 min 함수를 활용하여 더 작은 값만 저장해줍니다.
	for _ in range(m):
	a, b, c = map(int, input().split())
	graph[a][b] = min(graph[a][b], c)
	# 도시의 개수 n만큼 3중으로 반복하며
	for k in range(1, n + 1):
	for r in range(1, n + 1):
	for c in range(1, n + 1):
	# 다른 길을 거쳐갈 때 더 빨리 갈 수 있는 경로가 있는지 확인합니다.
	graph[r][c] = min(graph[r][c], graph[r][k] + graph[k][c])
	# 0번 도시 정보는 없으므로 출력되지 않게 반복하며
	for i in range(1, n + 1):
	for cost in graph[i][1:]:
	# 갈 수 없는 도시는 0으로
	# 갈 수 있는 도시는 저장된 비용으로 출력해줍니다.
	if cost == INF:
	print(0, end=' ')
	else:
	print(cost, end=' ')
	print()

view raw floyd-warshall.py hosted with ❤ by GitHub