[알고리즘 이론] 다익스트라(Dijkstra), 최단 경로 알고리즘

목차

이 글은 Notion에서 작성 후 재편집한 포스트입니다.

개요

---

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다

다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작한다.

음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문이다.

참고

---

https://www.youtube.com/watch?v=acqm9mM1P6o 

 

코드 GIT 주소

---

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

진행 과정

---

알고리즘의 원리

---

알고리즘의 원리를 간략히 설명하면 다음과 같다.

1. 출발 노드를 설정한다
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3과 4을 반복한다.

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. (이러한 1차원 리스트를 최단 거리 테이블이라고 한다.)

 

알고리즘 동작 원리 세부

---

다음과 같은 그래프가 있을 때, 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해보자.

초기 상태에서는 다른 모든 노드로 가는 최단거리를 ‘무한’ 으로 초기화하며, 이는 987654321, 혹은 int(1e9) 로 설정해주자.

1) 먼저 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 떄문에 처음에는 출발 노드가 선택된다.

2) 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 1번 노드와 연결된 노드는 2, 3, 4로, 각각 비용이 2, 5, 1 이다. 2, 3, 4번 노드에 대해 비용이 무한으로 설정되어 있는데, 세 노드에 대해 더 짧은 경로를 찾았으므로 각각 새로운 값으로 갱신한다. 처리된 결과는 다음과 같다. 현재 처리중인 노드와 간선은 하늘색, 이미 처리한 노드는 회색, 이미 처리한 간선은 점선으로 표기한다.

3) 이후 모든 단계에서도 방문하지 않은 노드중에서 최단거리가 가장 짧은 노드를 선택해야 한다. 따라서 2번째에서는 4번 노드가 선택된다. 이어서 4번 노드를 거쳐서 갈 수 있는 노드를 확인한다. 4번 노드에서 갈 수 있는 노드는 3번과 5번, 비용은 각각 4(1+3), 2(1+1) 이다.

4) 이 두 값은 기존 리스트에 담겨있던 값보다 작으므로 다음처럼 리스트가 갱신된다.

5) 이제 2번 노드를 선택한다. 왜냐하면 1번부터 2번, 5번까지의 최단거리가 2로 값이 같은데, 이럴 떄는 일반적으로 번호가 작은 노드를 선택한다. 그리고 2번 노드를 거쳐서 도달할 수 있는 노드 중에서 거리가 더 짧은 경우가 있는지 확인한다. 이번 단계에서 2번 노드를 거쳐서 가는 경우, 현재의 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.
예를 들어 2번 노드를 거쳐서 3번으로 이동하는 경우, 5(2 + 3) 만큼의 비용이 발생한다. 하지만 이미 현재 최단거리 테이블에서 3번 노드까지의 최단 거리는 4이므로, 값이 갱신되지 않는다.

6) 이번에는 5번 노드가 선택된다. 5번 노드를 거쳐서 6번 노드로 갈 수 있다. 현재 5번 노드까지는 최단거리가 2이므로 5번 노드에서 3번 노드로 가는 거리인 1을 더한 3이 기존 값인 4보다 작기 때문에 새로운 값 3으로 갱신된다. 또한 6번 노드로 가는 거리도 4로 갱신된다.

7) 이어서 3번 노드를 선택한 뒤에 동일한 과정을 반복, 6번 노드를 선택한 후 같은 과정을 반복한다.

간단한 다익스트라 알고리즘 소스코드

---

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

#노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
#시작 노드 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
#방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
#최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

#모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().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]
    #시작 노드를 제외한 전체 n - 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("무한")
    #도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

마치며

---

다익스트라 알고리즘을 살펴봤다.
사실 내용 자체는 이해되는데 코드로 구현하는게 진짜 너무 어렵다
이걸 뭐 외워야 되는건지.. 이해를 할 수 가 있는건지 ㅠ-ㅠ
알고리즘... 알면 정말 짜릿하고 재밌는데 모르면 막-막 할뿐이다..

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡