[파이썬 알고리즘]다익스트라 알고리

다익스트라 (Dijkstra) 알고리즘

최단거리 구하는 알고리즘

하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있다.

가중치 방향 그래프 가 주어질때 사용가능하며 만약

가장 짧은 경로를 찾을때 사용 가치가 없다면 bfs 사용해서 풀수 있다.

알고리즘 개요

1. 출반노드설정
2. 최단거리 테이블 초기화
3. 방문하지 않는 노드중 최단거리 가장짧은거
4. 해당 노드를 거처가는 비용 계산후 테이블 갱신
5. 3,4, 과정 반복

 

이때 코드를 작성할때 우선순위 큐를 사용하는데 사용하는 이유는 우선순위 큐로 인해서 가장 짧은 경로를 가진 노드를 빠르게 찾을수 있어 시간 복잡도가 줄어들기 때문이다.

 

우선순위큐를 사용하지 않은 코드

n,m=map(int,input().split()) #노드간선정보
start=int(input()) # 시작노드
graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가
distance=[inf]*(n+1) # 거리테이블
visited = [False] * n  # 방문 여부 확인

for _ in range(m): # 간선정보 입력 a:출발노드 b :도착노드 c:가치
	a,b,c=map(int, input().split()) 
	graph[a].append((b,c))


#최단경로 구하는부분
def min_distance():
  min_val = INF
  index = 0
  for i in range(1, n+1):
    if distance[i] < min_val and not visited[i]: 
      min_val = distance[i]
      index = i
  return index



def dijkstra(graph, start):
    distance[start] = 0 # 시작 노드는 0으로 초기화
    visited[start] = True
    
    for i in graph[start]:
    	distance[i[0]]=i[1] #시작지점에 연결지점까지의 거리 입력
    
    for _ in range(n-1):
    	now=min_distance()
        visited[now]=True
        
        for j in graph[now]: #인접노드 탐색
        	cost=distance[now]+j[1]
			if cost<distance[j[0]]:
				distance[j[0]]=cost

 

우선순위큐를 사용한경우

import heapq
n,m=map(int,input().split()) #노드간선정보
start=int(input()) # 시작노드
graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가
distance=[inf]*(n+1) # 거리테이블

for _ in range(m): # 간선정보 입력 a:출발노드 b :도착노드 c:가치
	a,b,c=map(int, input().split()) 
	graph[a].append((b,c))
	
	

def dijkstra(start):
	q=[]
	heapq.heappush(q,(0,start)) #0은 현재위치에서의 비용이다.
	distance[start]=0
	
	while q:
		dist,now = heapq.heappop(q)
		if distance[now]<dist
			continue
		for i in graph[now]: #인접노드 탐색
			cost=dist+i[1]
			if cost<distance[i[0]]:
				distance[i[0]]=cost
				heapq.heappush(q,(cost,i[0])
	

dijkstra(start)
for i in range(1,n+1):
	if distance[i]==inf:
		print(무한)
	else:
		print(distance[i]

 

결국 두개의 코드는 결과값은 같지만 우선순위 큐를 사용한경우는에는 가장 값이 적은 노드를찾는 코드가 우선순위큐가 그역할을 하여 코드와 시간이 줄어든다.