[다익스트라 알고리즘] 한 살도 이해하는 다익스트라 알고리즘

들어가기 전에

다익스트라 알고리즘을 이해하기 위해 여러 유튜브와 블로그를 방문했었는데 대체로 설명이 어렵거나 생략이 많다.. 코드 설명도 자세하지 않아 아쉬움이 있었다. (특히, 블로그에 있는 표나 그림은 왜이렇게 딱딱한걸까.. 잘 모르는 사람에겐 거부감이 든다)

직접 하나하나 그려가보며 이해한 나의 깨달음을 다른 분들께 자세하고 쉽게, 마치 아무것도 모르는 어린 아이에게 설명하듯이 설명해보려고 한다. 그리고 시간이 지나면 잊어버리는 미래의 나를 위하여 상세히 기술해보았다.

자세한 예시부터 점점 과정을 추상화해나가므로 이해하기 쉬울 것이라고 생각한다.

 

다익스트라 알고리즘이란?

그래프의 한 정점(Vertex 또는 Node)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘으로, 최단 경로 문제에 사용된다.

그래프 방향의 유무는 상관 없으나, 간선(Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다.

핵심은 출발지에서 도착지까지의 가장 짧은 거리를 구하는 알고리즘이다!

 

우선 다음과 같은 그래프가 존재하다고 하자.

(이 그래프는 'EBS 링크 소프트웨어 세상, "가장 빠른길을 찾아라, 최단경로 알고리즘"'에서 나오는 그래프와 같다. 동영상 설명이 듣고 싶으면 이 제목으로 유튜브에서 검색해보면 이해에 도움이 된다.)

 

출발지는 '집' 이고,

도착지는 '학교' 이다.

 

그래프

 

 

출발지부터 각 위치에 대한 최단 거리를 기록할 표를 하나 사용할 것이다.

편의를 위해서 이 표를 distance라고 부르겠다.

distance

지금까지 우리에겐 그래프와, distance가 주어졌다.

앞으로 각 노드들을 돌아다니면서

1. 바로 이웃한 노드들과의 거리를 계산한다. 

2. 지금까지의 최단거리와 비교해서, 더 작은 값을 distance에 넣어준다.

우선은 가장 처음 거리를 distance에 넣을 때는 어떤 값이라도 들어갈 수 있도록 가장 큰 값인 무한대로 초기화를 해놓자.

 

출발지에서 출발지까지는 거리가 0이므로 집의 최단 거리를 0으로 바꿔준다.

지금까지 방문했던 노드들은 연두색으로 표시해둔다. 

distance[집] = 0

Cycle 1

우선 출발지부터 시작해보자.

현재 노드: 미용실

출발지의 이웃 노드들

위의 그림을 보면 집에서 갈 수 있는 이웃한 노드들은 '미용실', '슈퍼마켓' '영어학원'이다.

빨간색 선이 현재 이웃한 노드로 이동할 수 있는 경로를 표시한다.

그리고 각각 거리를 미용실은 5, 슈퍼마켓은 10, 영어학원은 9를 가진다.

우리는 distance에 출발지로부터 각 노드들로 가는 '최단거리'를 기록하고 있음을 잊지 말아야 한다.

집을 거쳐가는 거리가(예를들어 미용실까지 거리가 5) 현재 distance에 있는 노드들의 최단거리(예를들어 현재 distance에서 미용실까지 최단거리는 무한대)보다 작으므로, distance 최단거리를 수정해준다.

 

이제 집에서 갈 수 있는 이웃노드들은 모두 가봤다.

 

이제 집 노드는 방문했고, 다음으로 어떤 위치 노드로 가야할까? 미용실로 가야할까 또는 슈퍼마켓으로 가야할까..?

이 부분이 다익스트라 알고리즘을 이해하는데 중요한 포인트다. (다익스트라 알고리즘을 이해하는데 있어 필자는 가장 헷갈렸다.)

해야할 행동을 한 문장으로 정리해보겠다.

" distance에서 방문하지 않았던 노드 중에 '가장 최단 거리가 작은' 노드로 이동한다."

즉, distance에서 집은 방문했던 노드이니 제외하고, 나머지에서 가장 작은 값을 갖는 미용실이 다음 노드가 된다.

 

 

이후에는, 바로 윗 부분에서 집 노드에서 했던 것 처럼!  최단 거리를 비교하고 갱신하는 똑같은 과정을 수행해주면 된다.

---

Cycle 2

현재 노드: 미용실

이제 미용실로 다시 사이클이 반복된다. 집에서 했던 것처럼 똑같이 반복되니 잘 따라와보자.

 

연두색은 방문했던 경로, 빨간색은 현재 이웃한 노드로 이동하는 경로

위의 그림을 보면 미용실에서 갈 수 있는 이웃 노드들은 '슈퍼마켓' '은행'이다.

그리고 각각 거리를 슈퍼마켓은 8(5 + 3), 은행은 16(5 + 11)을 가진다.

 

여기서 중요한 부분이 이웃 노드까지의 최단 거리를 구할 때

'출발지부터 미용실까지의 현재 최단거리 + 미용실부터 이웃 노드까지의 거리' 를 구한다는 것이다!=(출발지~미용실)+(미용실~이웃노드)

우리는 '출발지'부터 각 노드까지 '최단거리'를  distance 표에 기록하고 있음을 잊지 말아야 한다.

출발지(집)에서 현재 노드(미용실)을 거쳐 이웃 노드(슈퍼마켓)을 가는 최단 거리를 비교하려면,

'출발지부터 미용실까지의 현재 최단거리 (distance[미용실]) + 미용실에서 이웃 노드까지의 거리를 더한 값'

                                                                      VS

'현재 이웃 노드까지의 최단 거리 (distance[슈퍼마켓])' 를 비교해야 한다.

이 두 값중 더 작은 값이 현재까지의 최단거리이므로, 최단거리가 바뀌는 경우 distance에 기록해주면 된다.

 

 

'출발지부터 미용실까지의 현재 최단거리 (distance[미용실]) + 미용실에서 슈퍼마켓까지의 거리를 더한 값' 즉, 출발지부터 미용실을 거쳐 슈퍼마켓까지 가는 거리가

'현재까지 슈퍼마켓까지의 최단 거리'보다  작으므로 => 슈퍼마켓까지의 최단 거리를 8로 바꿔준다.

 

은행도 이웃노드이므로 한 번 해보자.

최단 거리를 비교하고 갱신하는 똑같은 과정을 수행해주면 된다.

 

이제 이웃 노드들의 distance 비교와 갱신이 끝나면, 앞서 '집'에서 했던 것처럼

" distance에서 방문하지 않았던 노드 중에 '가장 최단 거리가 작은' 노드로 이동한다."

distance에서 지금까지 방문했던 집과 미용실을 제외한 노드들 중,  슈퍼마켓이 가장 작은 값을 가지므로 다음 노드는 슈퍼마켓이다!

---

Cycle 3

현재 노드: 슈퍼마켓

슈퍼마켓 노드로부터 이웃한 노드까지 이동

자, 지금 부터는 조금 간략하지만 큰 흐름을 보자.

위에서 했던 것과 정확히 똑같다.

1. 출발지부터 슈퍼마켓까지의 최단거리 + 슈퍼마켓에서 이웃 노드까지의 거리  vs 출발지부터 이웃 노드까지의 최단거리 비교,

더 작은 값을 distance에 갱신

2. 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 노드로 이동 

의 반복이다!

 

1.  슈퍼마켓 까지의 최단거리 +  슈퍼마켓 에서 이웃 노드까지의 거리  vs 이웃 노드까지의 최단거리 비교, 더 작은 값을 distance에 갱신

2. 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 영어학원으로 이동

 

---

Cycle 4

현재 노드: 영어학원

 

영어학원 노드로부터 이웃한 노드까지 이동

1. 출발지부터 현재노드까지의 최단거리 + 현재노드에서 이웃 노드까지의 거리  vs 출발지부터 이웃 노드까지의 최단거리 비교,

더 작은 값을 distance에 갱신

2. 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 노드로 이동 

1.  영어학원 까지의 최단거리 +  영어학원 에서 이웃 노드까지의 거리  vs 이웃 노드까지의 최단거리 비교, 더 작은 값을 distance에 갱신

2. 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 레스토랑으로 이동

---

Cycle 5

현재 노드: 레스토랑

 

레스토랑 노드로부터 이웃한 노드까지 이동

1. 출발지부터 현재노드까지의 최단거리 + 현재노드에서 이웃 노드까지의 거리  vs 출발지부터 이웃 노드까지의 최단거리 비교,

더 작은 값을 distance에 갱신

2. 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 노드로 이동 

1.  레스토랑 까지의 최단거리 +  레스토랑 에서 이웃 노드까지의 거리  vs 이웃 노드까지의 최단거리 비교, 더 작은 값을 distance에 갱신

2. 방문하지 않은 노드 중 distance에서 가장 작은 값을 갖는 은행으로 이동

---

Cycle 6

현재 노드: 은행

은행 노드로부터 이웃한 노드까지 이동

1. 출발지부터 현재노드까지의 최단거리 + 현재노드에서 이웃 노드까지의 거리  vs 출발지부터이웃 노드까지의 최단거리 비교, 더 작은 값을 distance에 갱신

2. 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 노드로 이동 

1.  레스토랑 까지의 최단거리 +  레스토랑 에서 이웃 노드까지의 거리  vs 이웃 노드까지의 최단거리 비교, 더 작은 값을 distance에 갱신

최종 distance

---

우리에게 주어졌던 노드는 총 7개,

도착지 노드에선 다른 노드로 이동하지 않으므로 총 6번의 사이클이 반복된다.

우리는 최종 distance를 통해 출발지부터 각 노드들까지의 최단 거리를 구할 수 있었다.

 

이를 Python 코드로 구현해보자!

우선, 그래프를 코드로 표현하기 위해서 Dictionary를 사용했다.

각 노드들로부터 이웃한 노드들까지의 거리를 표현하고 있다.

graph = {
    '집': {'미용실': 5, '슈퍼마켓': 10, '영어학원': 9},
    '미용실': {'슈퍼마켓': 3, '은행': 11},
    '슈퍼마켓': {'레스토랑': 3, '은행': 10, '영어학원': 7},
    '영어학원': {'은행': 7, '학교': 12},
    '레스토랑': {'은행': 4},
    '은행': {'학교': 2},
    '학교': {}
}

여기에 사용된 핵심적인 원리를 짚고 코드를 읽어보면 이해가 더 쉬울 것이다.

1. 매개변수로 graph와 출발지(start)가 들어온다.

2. distance는 dictionary로 구현한다.

3. 우선순위 큐(min heap)을 사용해  ' 방문하지 않은 노드들 중 distance에서 가장 작은 값을 가지는 노드'를 구한다. 

import heapq

def dijkstra(graph, start):
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    queue = []
    # start부터 시작하기 위해 queue에 start 넣어준다.
    heapq.heappush(queue, [distance[start], start])
    print("distance",distance)
    print("visited",visited)
    print("----start----")
    
    # queue에 남아 있는 노드가 있을 때 까지 반복
    while queue:
        # 탐색 할 노드, 거리를 queue에서 꺼내온다. (최소 cur_dist를 갖는 노드)
        cur_dist, cur_node = heapq.heappop(queue)
        
        print(f'cur_dist: {cur_dist}, cur_node: {cur_node}')
        # cur_dist값이 '현재까지 cur_node의 최단거리'보다 크면 continue로 지나간다.
        if(cur_dist > distance[cur_node]):
            print("continue")
            continue
            
        for neighbor in graph[cur_node]:
            # 'cur_node를 거쳐서 neighbor까지 가는 거리'와 '현재까지 neighbor까지의 최단거리'를 비교해서 더 작은 것으로 distance 설정
            if( distance[cur_node] + graph[cur_node][neighbor] < distance[neighbor]):
                distance[neighbor] =  distance[cur_node] + graph[cur_node][neighbor]
                # distance가 변경되었으면, 그 값으로 queue에 넣어준다.
                heapq.heappush(queue, [distance[cur_node] + graph[cur_node][neighbor], neighbor])
            print(queue)
    print(distance)

 

 

출력 과정 및 결과