다익스트라 알고리즘 (파이썬 구현)
1. 다익스트라 알고리즘이란?
그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다.
출발노드에서 갈 수 있는 모든 노드들의 최단 경로를 구할 수 있다.
다익스트라 알고리즘은 그리디 기반으로 작동하므로 가중치가 음수일 경우 최단거리를 구할 수 없다.
2. 동작 순서
1) 출발 노드를 설정한다.
2) 출발 노드에서 각 노드로 갈 수 있는 최단 거리를 저장하는 테이블을 만든다.
3) 출발노드부터 시작하여 각 노드로 갈 수 있는 거리가 현재 최단거리 테이블에 저장되어 있는 값보다 작으면 최단거리 테이블을 업데이트 하고 현재 노드에서 갈 수 있는 노드들을 확인한다.
4) 3번 과정을 반복하여 갈 수 있는 모든 노드들을 확인한다.
3. 다익스트라 함수 로직 구현
1) 파라미터로 받은 출발지의 가중치와 해당 노드의 인덱스를 힙큐에 저장한다.
(가중치를 함께 저장하면 힙큐를 사용하여 시간복잡도를 줄 일 수 있고, 만약 현재 저장된 가중치보다 최단거리 테이블의 값이 더 적을 경우 해당 경로를 다시 보지 않아도 되는 이점이 있다.)
2) 힙큐의 가장 위에 존재하는 현재노드와 가중치를 꺼내서 최단거리 테이블의 있는 값과 비교한다.
3) 최단거리 테이블에 있는 값보다 작으면 최단거리 테이블을 업데이트 하고 해당 노드와 가중치를 힙큐에 저장한다,
4) 힙큐의 값이 없을때까지 2-3 과정을 반복한다.
5) 최단거리 테이블에 있는 도착지의 최단거리를 반환한다.
4. 파이썬 구현
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]
for i in range(m):
a,b,c = map(int,input().split(' '))
graph[a].append([b,c])
#print(graph)
distance=[INF for i in range(n+1)]
def dijkstra(start):
q =[]
heapq.heappush(q,(0,start))
#힙큐에 가중치를 함께 넣으면 아래 if문 (if dist>distance[now])을 통해 불필요한 반복을 줄일 수 있고 가중치가 최소인 값부터 pop하기 때문에 최단경로를 더 빨리 찾을 수 있음
distance[start]=0
while(q):
dist,now=heapq.heappop(q)
if dist>distance[now]:
#dist보다 distance[now]가 더 작다면 distance[now]값이 아래 if문에 의해 더 작은 값으로 업데이트 되면서 힙큐에 들어갔음을 의미
continue
for next,cost in graph[now]:
if distance[next] > distance[now]+cost:
distance[next] = distance[now]+cost
heapq.heappush(q, (distance[next],next))
start,end=map(int,input().split(' '))
dijkstra(start)
print(distance[end])