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

Hyo Kyun Lee·2022년 1월 14일

다익스트라 알고리즘

알고리즘

목록 보기

16/45

16. 다익스트라 알고리즘

Dijkstra, 최단경로를 탐색하는 알고리즘으로 동적계획법을 활용한다.

특정 노드에서 다른 모든 노드를 향하는 최단 경로를 구할수 있고, 음의간선이 존재하지 않을 경우 활용할 수 있는 알고리즘이다.

정렬을 사용하여 그리디 알고리즘이라고도 일컫는다.

기본적으로 동적계획법을 활용하기 때문에, 이전까지 구한 최단거리 정보를 그대로 활용하는 알고리즘이며 GPS, 인공위성 등에 활용하는 가장 대표적인 알고리즘이기도 하다.

16-1. 기초 형태

다익스트라 알고리즘의 시작은 출발노드를 설정하는 것이다.

출발노드를 설정한다.
출발노드를 기준으로 인접노드의 최소비용(가중치)을 저장한다.
현재 방문할 수 있는 위치 중 가장 비용이 적은(가중치가 작은) 노드로 이동한다.
바뀐 현재 노드에서 다른 노드로 이동하는 가중치가 존재하고, 이 가중치의 누적된 합이 기존 가중치보다 더 적을 때 가중치를 교체한다.

16-2. 세부 과정

출발노드를 1이라 가정하자.

초기 상태에서의 graph 생성하기

1에서 인접노드가 있으면 가중치를 기재하고, 인접노드가 없으면 무한(INF) 수를 기재한다.
자기자신은 0으로 설정한다.
위 graph 상태는 다음과 같다.

[
[0 3 6 7],[3 0 1 INF],[6, 1, 0, 1],[7, INF, 1, 0]
]

출발노드는 1부터, 그 후 노드 설정은 가중치가 가장 작은 인덱스부터

먼저 1의 인접노드인 2, 3, 4에 대해 위와 같이 최초의 거리를 기재한다.

[0 3 6 7]

그 후 출발노드와 인접한 노드들 중 최단거리의 노드를 선택하고 인접노드의 가중치를 계산한다.

노드2(노드2는 방문)에서 방문하지 않은 노드들(3, 4)의 최소비용을 계산한다.
[3 0 1 INF]의 배열을 이용하여, 노드3/4로 향하는 최소비용을 구한다.

거쳐서가는 가중치를 위 배열에 업데이트한다.

1에서 3으로 가는 가중치가 6이었다.
현재 노드에서 3으로 가는 가중치가 존재하고(1), 1에서 현재노드로의 가중치(3)와 현재노드에서 3으로 가는 가중치(1)의 합(4)이 기존 가중치(6)보다 작으므로 교체한다.

현재 이동한 노드의 인접 노드 중 방문하지 않으면서 최소 가중치의 노드를 방문하고, 위 과정을 반복한다.

16-3. 기초알고리즘 - 방문배열 별도 설정 및 시간복잡도가 o(N^2)인 경우

node = 6
INF = 100000000

#graph 구성하기
graph = [
    [0, 2, 5, 1, INF, INF],
    [2, 0, 3, 2, INF, INF],
    [5, 3, 0, 3, 1, 5],
    [1, 2, 3, 0, 1, INF],
    [INF, INF, 1, 1, 0, 2],
    [INF, INF, 5, INF, 2, 0]
]

#방문여부
visited =  [False] * node

#거리
distance = [0] * node

#출발노드를 기준으로 해당 노드까지 최소비용이 구해진 후(배열생성)
#최소거리(비용)에 대한 노드를 반환(방문하지 않은 노드 중)
def getSmallIndex():
    min = INF
    index = 0
    for i in range(node):
        if distance[i] < min and visited[i] is not True:
            min = distance[i]
            index = i
    return index

#다익스트라를 수행하는 함수
def dijkstra(start):

    visited[start] = True
    for i in range(node):
        #graph에 적혀진 비용정보를 distance에 입력
        #원래 알고있는 최소비용
        distance[i] = graph[start][i]
    #방문하지않는 노드 중 최소 비용이 발생하였을때(거쳐가는 경우)
    #방문하지않는 노드의 우선노드는 distance 상에서 최소비용을 가지는 노드
    for i in range(node-2):
        #자기자신과 이전 기준점까지는 탐색완료(탐색대상이 node-2)
        currentIndex = getSmallIndex()
        visited[currentIndex] = True
        for j in range(node):
            if visited[j] is not True and distance[currentIndex]+graph[currentIndex][j] < distance[j]:
                distance[j] = distance[currentIndex] + graph[currentIndex][j]


dijkstra(1)
print((distance))

16-4. heap을 이용하여 방문배열없이 구현하는 알고리즘(시간복잡도 최소화)

node = 6
INF = 100000000

#graph 구성하기
graph = {
    1: {2: 2, 3: 5, 4: 1},
    2: {1: 2, 3: 3, 4: 2},
    3: {1: 5, 2: 3, 4: 3, 5: 1, 6: 5},
    4: {1: 1, 2: 2, 3: 3, 5: 1},
    5: {3: 5, 4: 1, 6: 2},
    6: {3: 5, 5: 2}
}

#distance
import heapq
#최소비용인 인접노드를 탐색하는 부분을 heap정렬을 이용해 구하는 경우
#시간복잡도를 기존 알고리즘 대비 개선시킬 수 있는 알고리즘
def dijkstra(start):
    distance = {node: INF for node in graph}
    distance[start] = 0
    queue = []
    #min heap
    heapq.heappush(queue, [distance[start], start])

    while queue:
        currentDistance, currentIndex = heapq.heappop(queue)

        #시작점이 정해진 상태임을 기억
        #현재 선택된 노드에 대해
        if distance[currentIndex] < currentDistance:
            continue
        #인접노드 방문 후 새로운 거리값 계산
        for newIndex, newDistance in graph[currentIndex].items():
            tempDistance = currentDistance + newDistance
            if tempDistance < distance[newIndex]:
                distance[newIndex] = tempDistance
                heapq.heappush(queue, [tempDistance, newIndex])
    return distance

print(dijkstra(1))