다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
알고리즘의 원리
1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정의 3번과 4번을 반복한다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장하여 리스트를 계속 갱신한다. 그렇기 때문에 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리하고 있는 노드와 인접 노드로 도달하는 더 짧은 경로를 비교했을 때, 더 짧은 경로를 발견하면 해당 경로가 제일 짧은 경로라고 결정한다. (4번 과정)
다익스트라 구현 방법에는 두가지 방법이 있다.
방법1. 알고리즘을 그대로 구현하는 방법
1. 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언
2. 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색) 한다.
Tip: 모든 리스트는 (노드의 개수 +1)의 크기로 할당해 노드의 번호를 인덱스로 하여 바로 리스트에 접근할 수 있도록 한다.
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
# 주어지는 그래프 정보 담는 N개 길이의 리스트
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())
graph[a].append((b, c)) #a라는 그래프에 b와 c 튜플로
# 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환
def get_smallest_node():
min_value = INF
index = 0
for i in range(1, n+1):
if not visited[i] and distance[i] < min_value:
min_value = distance[i]
index = i
return index
# 다익스트라 알고리즘
def dijkstra(start):
# 시작노드 초기화
distance[start] = 0
visited[start] = True
# 시작노드의 인접한 노드들에 대해 최단거리 계산
for i in graph[start]:
distance[i[0]] = i[1]
# 시작노드 제외한 n-1개의 다른 노드들 처리
for _ in range(n-1):
now = get_smallest_node() # 방문X 면서 시작노드와 최단거리인 노드 반환
visited[now] = True # 해당 노드 방문처리
# 해당 노드의 인접한 노드들 간의 거리 계산
for next in graph[now]:
cost = distance[now] + next[1] # 시작-> 현재노드 + 현재노드와 연결된 거리값
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[next[0]]: # cost < 시작->now의 인접노드 다이렉트 거리
distance[next[0]] = cost
dijkstra(start)
#모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
if distance[i] == INF:
print('도달 할 수 없음')
else:
print(distance[i]) #도달할 수 있는 경우 거리 출력방법 2. 힙 자료구조를 이용해서 구현하는 방법
1446 문제풀이
문제
매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오.
입력
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.
출력
세준이가 운전해야하는 거리의 최솟값을 출력하시오.
문제 분석: D킬로미터의 고속도로에 존재하는 지름길을 이용했을 때 가장 짧은 거리를 출력하는 프로그램 만드는 것이다. 0 부터 D 킬로미터 떨어진 고속도로에서 지름길들 정보가 주어졌을 때 각 길을 사용했을 때 최단 거리로 목적지에 도착할 수 있는 거리를 계산하면 된다.
구현에 필요한 사항을 세가지로 뽑아보자면,
1. 지름길을 저장하는 그래프가 필요하다.
2. 거리를 저장하는 리스트가 필요하다.
3. 지름길의 종료 위치가 도착지보다 멀리 있을 경우에 그래프는 저장하면 안된다. 역주행이 안된다고 했으니까.
문제풀이:
시작 노드를 0, 도착 노드를 D로 설정하고 1,2,3,4 ~ D 모두 노드로 간주한다.
그래프를 인접리스트 형식으로 저장한다. 이때 지름길의 종료 위치가 도착지보다 멀리 있을 경우에 그래프는 저장하지 않는다. 그리고 거리를 저장하는 리스트 distance를 만들고, 최대값으로 채우고 인덱스 0의 값을 0으로 갱신해준다. 큐를 최소힙으로 선언하고 while문 안에서 각 지름길에 대한 그래프를 순회하며 그 중 더 작은 값을 더해주면 반복한다. 반복문을 탈출하면 거리를 저장한 리스트의 인덱스 d를 출력한다. 거리를 저장한 리스트를 이전의 거리보다 1씩 증가시키고 지름길이 있는 위치라면 지름길 중 가장 짧은 길이를 선택해서 그 지름길의 길이로 거리를 갱신해주고 다시 1을 증가시켜준다.
import sys
import heapq
N, D = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(D+1)] #그래프를 인접리스트 형식으로 저장
for i in range(D):
graph[i].append((i+1, 1))
for i in range(N):
start, end, length = map(int, sys.stdin.readline().split())
if end > D: continue #지름길의 종료 위치가 도착지보다 멀리 있을 경우에 그래프는 저장하면 안된다. 역주행이 안된다는 조건이 있기 때문.
graph[start].append((end, length)) #graph리스트에 지름길 정보 저장
INF = 987654321
distance = [INF]*(D+1) #최대값을 INF에 저장하고, 거리를 저장할 리스트 distance를 INF d+1개로 채운다.
distance[0] = 0 #거리 저장하는 리스트
q = []
heapq.heappush(q, (0, 0))
while q:#큐가 비어있지 않다면
d, now = heapq.heappop(q) #가장 최단거리가 짧은 노드에 대한 정보 꺼내기
if distance[now] < d: continue #distance[now]는 테이블에 기록된 값
for x in graph[now]: #x는 인접 노드
cost = d + x[1] # 현재 확인하는 거리값 + 인접노드 거리값
if distance[x[0]] > cost: #다른 노드로 이동하는 거리가 더 짧은 경우
distance[x[0]] = cost #갱신
heapq.heappush(q, (cost, x[0]))
print(distance[D]) #거리를 저장한 리스트의 인덱스 D를 출력n,d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dist = [i for i in range(d+1)]
for i in range(d+1):
dist[i] = min(dist[i], dist[i-1]+1)
for start, end, short in graph:
if i == start and end <= d and dist[i]+short < dist[end]:
dist[end] = dist[i]+short
print(dist[d])