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

Hyo Kyun Lee·2022년 1월 23일

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

알고리즘

목록 보기

33/45

1. 최단경로 알고리즘

특정노드에서 다른 노드로 향하는 가장 적은 비용, 최단 거리를 도출하는 알고리즘을 의미한다.

최단경로를 도출하는 알고리즘을 활용할 수 있는 형태는 크게 3가지로 나뉘어져있다.

한 지점에서 다른 한 지점으로 향하는 최단경로(최소비용)
한 지점에서 모든 노드 지점까지 향하는 최단경로(최소비용)
모든 지점에서 다른 모든 노드 지점까지 향하는 최단경로(최소비용)

2. 다익스트라 알고리즘

한 노드에서 다른 모든 노드까지의 최단 경로를 도출

graph가 가지는 최초 연결상태에 상관없이, 최단경로 테이블은 일단 모든 노드에 대해 INF(무한)값을 가진다(단, 출발노드를 설정하였을때 그 값을 최초 0으로 초기화).

다익스트라가 제시한 최단경로 알고리즘으로, 한 노드에서 다른 모든 노드로 향하는 최소 비용을 도출할 수 있는 알고리즘이다. 즉, 모든 노드에 대한 최단 경로를 구한다.

다익스트라 알고리즘을 적용할 수 있는 조건이 정해져 있는데, 음의 간선이 없을 경우에만 적용가능하다.

매 상황에서 항상 최소비용의 경우를 생각하는 일종의 그리디 알고리즘이기도 하다.

출발노드 설정
최단거리 테이블 초기화
방문하지않은 노드 중 최단거리(비용이 가장 짧은 노드)를 선택하여 방문한다.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 최단거리 테이블을 update 한다.
※ 기존 출발점을 선택한 상태에서 특정 노드를 거쳐가는 경로를 고려해야 하며, 최소값을 그대로 테이블에 갱신하는 것임을 기억한다.
위 과정을 반복한다.

알고리즘 동작과정에서 최단거리 테이블은 현재 상황에서 그 노드를 출발점으로, 다른 노드로 향하는 최단거리 정보를 이미 담고 있다. 그 노드를 거쳐 다른 노드로 가는 경로 중 최소값이 나타난다면 그 경로를 그대로 반영한다.

step 1

최초 출발노드를 설정하고, 출발노드에서 다른 노드까지의 최초 간선정보를 초기화한다.

step 2

방문하지 않은 노드 중에서 출발 노드(최초 설정한 노드)을 시작으로 하여, 거쳐가는 노드(=인접한 노드(graph 상 2/3/4))로 이동하면서 경로를 한번씩 확인한다.

step 3

그 후 출발점의 인접 노드 중 가장 경로가 짧은 노드를 선택하여 방문하고, 그 노드를 거쳐가는 노드로 설정하여, 출발노드에서 노드를 거쳐가서 다른 노드로 향하는 경로를 계속 업데이트한다.

출발노드는 정해져 있는 상태이며, 거쳐가는 노드(인접노드)를 바꿔가면서 최단경로 테이블을 update한다.

1노드가 출발점인 상태에서 방문하지 않은 노드(2,3) 중 출발노드로 부터 경로가 짧은(비용이 작은) 노드를 방문한다(비용이 같으면 노드가 가장 작은 곳부터 방문).
같은 거리라면 노드 숫자가 작은 곳부터 방문한다.

step 4

마찬가지로 거쳐가는 노드를 설정(인접노드)한 후 최단경로 테이블을 update 한다.

step 5

단 거쳐가는 노드를 선택할때 그 노드가 최초 출발점 노드와 인접하지 않은 경우가 있다.

그때 시점에서 최단경로 테이블에 기재되어있는 경로값이 최단 경로로 반영되어있다고 가정하고, 그 경로에서 그대로 거쳐가는 노드의 인접노드까지의 거리를 반영하여 최단경로 테이블에 기재한다.

5를 거쳐가는 노드로 설정하였다면, 최초 출발노드를 1로 설정하였으므로 1에서 5를 거쳐, 5의 인접노드인 3과 6이 각각 최종 도착지점이 된다.

2-1. 다익스트라 알고리즘의 특징

그리디 알고리즘 : 최단경로를 거쳐간다는 기준이 일정하다는 점에서 그리디 알고리즘이고, 매 상황에서 방문하지 않은 노드 중 가장 비용이 작은 노드를 선택하여 반복한다.
단계를 거치면서 처리된 거쳐가는 노드와 이 노드를 통해 다른 노드로 향하는 최단거리 정보는 이미 최적의 해로 고정되어 바뀌지 않는다.
알고리즘을 완전히 수행한 후 각 노드까지의 최단거리 정보가 저장되는 것이고, 부가적인 조건이 있다면 소스코드에 추가한다.

2-2. 선형탐색을 이용한 알고리즘 구현

import sys
INF = int(1e9) #1*10^9

#노드 개수와 간선 개수
n, m = map(int, sys.stdin.readline().split())
#각 노드에 연결된 노드 정보를 담는 리스트 만들기
graph = [[] for _ in range(n+1)] #노드 0은 제외
#방문정보
visited = [False] * (n+1)
#최단거리 테이블
distance = [INF] * (n+1)

#간선정보 입력받기
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().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 visited[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]
    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):
    if distance[i] == INF:
        print("no path")
    else:
        print(distance[i])

2-3. 시간복잡도

시간복잡도는 각 노드별 선형탐색을 진행하므로 노드별 O(V), 전체적인 시간복잡도는 O(V^2)을 가진다.

따라서 노드 개수가 많아지는 경우엔 본 알고리즘은 사용하기 어려워진다.

3. 우선순위 Queue(min heap)

우선순위 Queue(데이터 우선순위를 기준으로 데이터를 선별하는 자료구조)

Queue 자료구조를 활용하며, 기존 리스트를 통한 선형탐색을 이용하면 log(N)의 선형적인 시간복잡도가 소요된다.

단순히 데이터 선입선출(삽입순서)가 아닌, 우선순위(혹은 가치)가 높은 데이터부터 삭제하는 자료구조를 의미한다.

리스트를 사용하면 O(N), 힙을 사용하면 O(logN)으로 시간복잡도면에서 유리한 점이 있다.

힙은 python에서 별도로 라이브러리를 제공, 메소드를 사용하여 구현할 수 있다.

import heapq

#오름차순 힙(min heap)
def heapsort(iterable):
#iterable은 무작위로 나열된 배열(리스트)
  h = [] #heapq 자체는 heap 객체이고, 이에 대한 heap 리스트 선언
         #h리스트를 heapq를 이용한 메소드 인자로 사용하면 heap자료구조로 된다.
  result = []
  
  #원소를 heap에 삽입, 자동적으로 min heap으로 정렬됨
  for value in iterable:
    heapq.heappush(h, value)
  
  #힙(h)에 선언된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
  	#min heap에서 가장 작은 원소부터 차례로 추출한다.
    result.append(heapq.heappop(h))
  
  return result

#기본적으로 제공되는 힙 자료구조를 사용한다면 오름차순으로 나열된다.
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

3-1. Queue를 이용한 알고리즘 구현

step 1

최초 출발노드를 설정하고, Queue에 넣는다.
※ Queue에 넣는 정보는 노드와 거리정보이다.

step 2

Queue에서의 노드를 추출해오고, 추출해온 노드는 출발점에서 "거쳐가는 노드"가 된다. 이 거쳐가는 노드를 계속 탐색/반복해가면서 최단거리 테이블에 반영한다.

출발노드를 1로 설정하고, 이를 Queue에 넣은 후 추출해온 상태이므로 거쳐가는 최초 노드는 1이 된다.

이때 1에 대해 인접한 노드를 차례로 탐색하되,

인접노드들은 Queue 자료구조에 삽입한다.
Queue에 삽입하면서 해당 노드에서 인접 노드까지의 거리를 기준으로, 최소값을 우선순위로 하여 넣는다.
import heapq를 이용, heapq 자료구조에 삽입하며 자동적으로 min heap이 구성되므로 인접노드 탐색시 해당 라이브러리를 활용하면 자동으로 최소경로값을 기준으로 거쳐가는 노드를 선택하게 된다.

위 개선전 알고리즘과 마찬가지로, 각 단계에서 정립한 최단경로 테이블은 이미 최적의 해가 반영된 상태이므로 테이블 반영 후엔 다른 경우의 수가 존재하지 않는다.

※ 다시 한번 상기하자면, heap에 넣는 노드들은 거쳐가는 노드들의 인접 노드들이고, 인접 노드들은 거리의 최소값에 따라 min heap 자료구조에 자동적으로 배열된다.

step 3

다음 탐색 노드는 heap에서 꺼내어 확인하며, 1에서 시작하여 거쳐가는 노드(이자 출발점인)를 고르는 것이다.

heap에서 이미 최단경로 순으로 노드들이 배열되어있는 상황이기 때문에, 노드들은 출발노드인 1로부터 거리가 짧은 인접노드들 순으로 정렬되어 있다.

과정상 노드4가 추출되고, 노드4에 대한 최단경로 테이블을 업데이트 한다.

※ 거쳐가는 노드의 인접노드인 3과 5가 Queue에 삽입되며, 이 역시 1을 출발해서 노드를 거쳐 각 노드로 향하는 최단경로를 의미함을 기억하자.
※ 최단거리테이블이 갱신된 후, 그 최단거리가 그대로 Queue(heap table)에 반영이 된다(최단경로에 따라 적절한 위치에 노드들이 삽입됨).
※ 이때 노드3에 대한 최단경로 값이 기존 5가 있었는데, 4로 감소되어 최소값이 4로 갱신 및 해당 튜플이 Queue에 넣어졌음을 확인한다(노드가 유지되고 있는 상태 유의).

step 4

step 3과정 후 최상단(우선순위) 노드인 2를 추출하고, 방문하지 않은 노드이므로 거쳐가는 노드로 설정하여 그대로 알고리즘을 진행한다.

step 5

위 과정을 반복한다.

이후 과정에서도 최단경로 테이블이 갱신됨에 따라 그대로 값들이 Queue(min heap)에 반영되었음에 유의한다.

visited table

각 step을 진행하기 전, 거쳐가는 노드를 설정하기 전에 해당 노드가 visited table에 존재하는 지, 즉 이미 거쳐간 노드인지 먼저 확인한다.

확인 후 방문한 이력이 있다면 생략한다.

최종적으로 이러한 min heap(queue)구조를 이용한 개선 다익스트라 알고리즘은 아래와 같다.

#거쳐가는 노드를 선택하는 과정에 heap을 활용하는 경우

import heapq
import sys

INF = int(1e9)

#노드개수, 간선개수
n, m = map(int, sys.stdin.readline().split())
#시작노드
start = int(input())
#그래프 연결 정보
graph = [[] for _ in range(n+1)]
#최단거리 테이블 초기화
distance = [INF] * (n+1)

#간선 정보
for _ in range(m):
    #a번 노드를 출발하여 b로 가는 비용이 c
    a, b, c = map(int, sys.stdin.readline().split())
    # 즉 graph에는 인접노드 정보와 함께 최초 상태의 비용까지 저장되어있게 된다.
    graph[a].append((b,c))

#개선 다익스트라
def dijkstra(start):
    q = []
    #heap에는 경로, 노드의 정보로 삽입하며
    #queue에 들어가는 정보는 거쳐가는 노드들에 대한 정보이다.
    #시작노드는 start에 저장된 상태
    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("INFINITY")
    else:
        print(distance[i])