최단 경로 알고리즘: 다익스트라(Dijkstra)

다익스트라 최단 경로 알고리즘

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

 

매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 볼 수 있다..

 

다익스트라 알고리즘의 원리

1. 출발 노드를 설정한다

2. 최단 거리 테이블을 초기화한다 (자기자신=0, 다른노드=무한으로 설정함)

3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

5. 위 과정에서 3번과 4번을 반복한다.

 

간단한 ver

파이썬 코드

import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split()) #노드개수n, 간선개수m
start = int(input()) #시작 노드번호
graph=[[] for i in range(n+1)] #노드 연결정보를 담을 리스트

visited=[False] * (n+1) #방문표시할 리스트
distance = [INF] * (n+1) #최단거리 테이블

for i in range(m): #간선정보 입력받기
    a,b,c=map(int,input().split())
    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 visited[i]:
            min_value = distance[i]
            index=i
    return index

def dijkstra(start):
    distance[start]=0 #시작지점~시작지점까지 거리=0
    visited[start]=True
    for j in graph[start]:
        distance[j[0]] = j[1] #j[0]으로 가는 거리 j[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]]: #기록되어있던 최단거리보다 now를 거쳐가는게 빠를 때
                distance[j[0]] = cost

dijkstra(start)

for i in range(1,n+1):
    if distance[i]==INF:
        print("INFINITY")
    else:
        print(distance[i])

"""
시간복잡도는 O(V^2)
노드의 개수가 5,000개 이하라면 문제를 해결할 수 있지만,
노드의 개수가 10,000개를 넘어간다면 시간초과..
"""

 

시간복잡도가..

O(V**2)임.

(노드개수V)

그래서 노드의 개수가 5000개를 넘어가면 시간초과가 뜰 수가 있다..

 

중간에 있는 get_smallest_node()함수를 보면

방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 반환하기 위해 반복문을 이용하는데

..원소를 하나하나 다 들여다봐야해서 수행시간이 오래걸린다..

 

그래서 개선된 다익스트라 알고리즘은 우선순위 힙큐를 이용한다

원소를 넣고 뺄 때 시간복잡도가 O(logN)이라 더 빨리 수행할 수 있다

 

import sys,heapq
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split()) #노드개수n, 간선개수m
start = int(input()) #시작 노드번호
graph=[[] for i in range(n+1)] #노드 연결정보를 담을 리스트

visited=[False] * (n+1) #방문표시할 리스트
distance = [INF] * (n+1) #최단거리 테이블

for i in range(m): #간선정보 입력받기
    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]]: #현재 노드를 거쳐 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("INFINITY")
    else:
        print(distance[i])

큐에서 (거리, 노드) 값을 꺼낸다.

distance 리스트에 저장되어있던 값과 큐에서 꺼낸 거리 값을 비교한다.

큐에서 꺼낸 거리값이 더 작은 값이라면..

해당 노드와 연결된 곳까지 가는 비용을 계산한다..

그 비용이 distance 리스트에 저장되어있던 값보다 더 적다면..

distance리스트의 값을 변경하고 힙큐에 (cost,노드)를 삽입한다..

이것을...큐에 값이 존재하는한 계속 반복..반복...반복...하면됨.