최단 경로
가장 빠르게 도달하는 방법
다익스트라 최단 경로 알고리즘
방법1. 간단한 다익스트라 알고리즘
방법2. 개선된 다익스트라 알고리즘
플로이드 워셜 알고리즘
최단 경로
가장 빠르게 도달하는 방법
다익스트라 최단 경로 알고리즘
방법1. 간단한 다익스트라 알고리즘
시간 복잡도 O(V^2) V는 노드 개수
import sys
input = sys.stdin.readline
INF = 1e9
# 노드의 개수, 간선의 개수 입력 받기 =
n, m = map(int, input().split())
# 시작 노드 번호를 입력 받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for _ in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트 만들기
visited = [False] * (n+1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (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 = INF
index = 0
for i in range(1, n+1):
if distance[i] < min_value and not visitied[i]:
min_value = distance[i]
index = i
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_smallest_node()
visited[now] = True
# 현재 노드와 연결된 다른 노드를 확인
for j in graph[now]:
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] == INF:
print("INFINITY")
# 도달할 수 있는 경우, 거리를 출력
else:
print(distance[i])방법2. 개선된 다익스트라 알고리즘
-
시간 복잡도 O(ElogV) E는 간선의 개수, V는 노드의 개수
-
힙 자료구조 이용 -> 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.
힙 Heqp 자료구조 -
우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나
-
우선순위 큐 -> 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.
-
PriorityQueue 와 heapq 중 heapq 사용 권장
import sys input = sys.stdin.readline INF = 1e9 # 노드의 개수, 간선의 개수 입력 받기 = n, m = map(int, input().split()) # 시작 노드 번호를 입력 받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for _ in range(n+1)] # 방문한 적이 있는지 체크하는 목적의 리스트 만들기 visited = [False] * (n+1) # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (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 = INF index = 0 for i in range(1, n+1): if distance[i] < min_value and not visitied[i]: min_value = distance[i] index = i 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_smallest_node() visited[now] = True # 현재 노드와 연결된 다른 노드를 확인 for j in graph[now]: 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] == INF: print("INFINITY") # 도달할 수 있는 경우, 거리를 출력 else: print(distance[i])플로이드 워셜 알고리즘
#Backend #Developer