15주차_#1753_최단경로

Yona·2021년 12월 30일

다익스트라 백준 알고리즘

🍕 baekjoon

목록 보기

26/31

문제

백준_1753_최단경로

처음 보고든생각

아...아아 이거 컴넷 기말고사에 나왔던 알고리즘인데
아아아아 다익스트라

다익스트라 알고리즘
특정 정점에서 다른 모든 정점으로 가는 최단 거리를 알려준다.
가중치가 음인 경우는 불가능 (플로이드 워셜을 써야)
우선순위 큐 사용시 복잡도는 O(N*logN)

다만 '서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.' 가 걸린다. 아예 다르게 접근해야하는지, 아니면 다익스트라를 보강하는 방식으로도 가능한지 일단 수도코드를 간단하게 작성해서 각을 재봐야겠다.

다익스트라 알고리즘 구현

우선순위 큐

파이썬의 heapq는 우선순위 큐를 만드는데 주로 사용된다. (heap은 여기를 참고)

다익스트라 알고리즘 python

import heapq
import sys

def dijkstra(start) :
	#초기 배열 설정
	distances = {node:sys.maxsize for node in graph}
	# 시작 노드의 거리는 0으로 설정
	distances[start] = 0
	queue = []

	# 시작노드부터 탐색하기를 위함.
 	# (거리,노드) - 거리, 노드 순으로 넣은 이유는 heapq 모듈에 첫번째 데이터를 기준으로 정렬을 진행하기때문
	# (노드,거리) 순으로 넣으면 최소 힙이 예상한대로 정렬되지 않음
	heapq.heappush(queue, (distances[start], start))

	# 우선 순위 큐에 데이터가 하나도 없을 때 까지 반복
	while queue :
		# 가장 낮은 거리를 가진 노드와 거리를 추출
		current_distance, node = heapq.heappop(queue)
		# 파이썬 heapq에 (거리, 노드) 순으로 넣다보니까, 동일한 노드라도 큐에 저장이 된다.
		# 예시 ) queue[(7, 'B'), (10, 'B')]
		# 이러한 문제를 아래 조건문으로 이미 계산되어 저장된 거리와 추출된 거리와 비교하여
		# 저장된 거리가 더 작다면 비교하지 않고 큐의 다음 데이터로 넘어간다.
		if distances[node] < current_distance :
			continue

		# 대상인 노드에서 인접한 노드와 거리를 순회
		for adjacency_node, distance in graph[node].items() :
			# 현재 노드에서 인접한 노드를 지나갈때까지의 거리를 더함
			weighted_distance = current_distance + distance
			# 배열의 저장된 거리보다 위의 가중치가 더 작으면 해당 노드의 거리 변경
			if weighted_distance < distance[adjacency_node] :
				# 배열에 저장된 거리보다 가중치가 더 작으므로 변경
				distances[adjacency_node] = weighted_distance
				# 다음 인접 거리를 계산하기 위해 우선순위 큐에 삽입 (노드가 동일해도 일단 다 저장함)
				heapq.heappush(queue, (weighted_distance, adjacency_node))

	return distances

graph = {
	'A' : {'B' : 10, 'C' : 3},
	'B' : {'C' : 1, 'D' : 2},
	'C' : {'B' : 4, 'D' : 8, 'E' : 2},
	'D' : {'E' : 7},
	'E' : {'D' : 9},
}

result = dijkstra('A')
print(result)

이 코드에선 dictionary형태로 쓰는데,
'B' : {'C' : 1, 'D' : 2} 처럼 중복된 키가 있을 수 없기 때문에
'서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.' 의 조건을 벗어난다.

리스트 형태로 고치도록 하자!

짠 코드

import heapq
import sys

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

# 노드의 개수, 간선의 개수를 입력받기
V, E = map(int,input().split())
# 시작 노드 번호를 입력받기
start = int(input())

# 최단거리 테이블
distance_result = [INF]*(V+1)

# 노드 연결정보
graph = [[] for i in range (V+1)]
for _ in range (E) :
	u, v, w = map(int,input().split())
	graph[u].append((v,w))

# 최소힙을 통해 개선된 다익스트라 알고리즘
def dijkstra(start) :
	q = []
	heapq.heappush(q, (0, start))
	distance_result[start] = 0

	# 최소힙에 남은게 있는동안 반복
	while q:
		# 최소힙을 사용하여 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
		dist, cur_v = heapq.heappop(q)

		# 이미 처리된 노드라면 무시
		# 별도의 visited 테이블이 필요없이, 최단거리테이블을 이용해 방문여부 확인
		if distance_result[cur_v] < dist :
			continue

		# 선택된 노드와 인접한 노드 연산
		for i in graph[cur_v] :
			weight = dist + i[1]
			# 선택된 노드를 거쳐 이동하는게 더 빠른 경우
			if weight < distance_result[i[0]] :
				distance_result[i[0]] = weight # 수정해주고
				heapq.heappush(q, (weight, i[0])) # 힙에 넣어준다

dijkstra(start)

for i in range(1, V+1) :
	if distance_result[i] == INF :
		print('INF')
	else :
		print(distance_result[i])