[정글 week03] 다익스트라 알고리즘

Woody Jo·2025년 5월 31일

kjungle

목록 보기

9/31

정글 3주차 공부 키워드 중 하나는 다익스트라 알고리즘이다.

그래서 다익스트라가 뭔데라고 한다면

이 알고리즘을 개발한 네덜란드 출신 컴퓨터 과학자 에츠허르 데이크스트라의 이름에서 유래가 된 알고리즘이다.

엥? 다익스트라라며...?
데이크스트라잖아?

네덜란드 발음으로 데이크스트라의 이름을 한국에서는 잘못된 읽기 사용의 시작으로 다익스트라가 된 데이크스트라

이런 사례들이 꽤나 많은 듯 하다...잘못된 것들은 좀 고칩시다...

어쨋든 그게 뭔데?

다익스트라 설명

DP 혹은 그리디 알고리즘이라고도 불리는 다익스트라는 최단 경로(최소의 비용)를 찾는 방법

행과 열이 있을 때 특정한 행 에서 열 로 가는 비용을 찾는 방법

대표적인 사용 예시로는

인공지능을 사용한 GPS

아아!
그리고 음의 간선이 존재하지 않는 알고리즘이다.

음의 간선이 뭔대?

이미 방문한 노드는 다시 보지 않는다.
예를 들어, A-C 비용이 10이라는 비용이 설정되었어.
A-B-C의 비용이 5가 되어 최단 경로가 되어도 다익스트라는 A-C로 그대로 사용한다.

다익스트라의 철학

“어떤 정점에 도달할 수 있는 최단 경로는,
항상 아직 방문하지 않은 정점 중 거리가 가장 짧은 곳에서부터 나올 것이다.”

즉, 먼저 방문한 게 제일 짧은 거야. 나중에 더 좋은 길은 없을 거야.
이걸 음의 간선 없는 그래프에서는 맞다고 “보장”할 수 있어.
하지만, 경로 중간에 돌아서 가면 오히려 더 짧아질 수도 있고,
한 번 확정해놓고 그 뒤에 더 좋은 걸 무시하면,
결과는 “빠르지만 잘못된 경로”가 되는 거지.

음...

다익스트라 실행 과정

출발 노드 설정 (인자 출발 노드 값 전달)
출발 노드 기준 각 노드의 최소 비용 저장 (배열 사용)
방문하지 않은 노드 중 가장 비용이 적은 노드 선택 (반복, 조건문)
반복 시 해당되는 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신
위 과정을 반복하면서 최소 거리를 찾아간다.

아무 노드도 선택되지 않은 상태

1번 노드 선택 상태

2번 노드 선택 상태

4번 노드 선택 상태

3번 노드 선택 상태

5번 노드 선택 상태
(모든 노드 순회 완료)

다익스트라 구현

알고리즘 : 다익스트라 (선형 탐색)
시간복잡도 : O(n^2)

시간 복잡도가 꽤 크다.
min_heap을 이용하면 O(n log n)으로 시간을 줄일 수 있다고 하지만 저는 해야될게 많아서 하하...

나중에 해보도록 하겠습니다.

count = 5
inf = float('inf')

g = [
    [0, 3, 6, 1, inf],
    [3, 0, 2, inf, 1],
    [6, 2, 0, 8, 2],
    [1, inf, 8, 0, 2],
    [inf, 1, 2, 2, 0]
]

visited = [False] * count
distances = [0] * count 

# 가장 최소 거리를 가지는 정점을 반환
def getSmallIndex():
    min_distance = float('inf')
    index = 0

    for i in range(count):
        if distances[i] < min_distance and not visited[i]:
            min_distance = distances[i]
            index = i
    return index

def dijkstra(start):
    # distances 초기화
    for i in range(count):
        distances[i] = g[start][i]

    # start 인덱스 방문 완료
    visited[start] = True
    
    for _ in range(0, count-2):
        currentIndex = getSmallIndex()
        visited[currentIndex] = True
        for j in range(count):
            if not visited[j]:
            # 현재 노드에서 방문하지 않은 모든 노드를 순회하면서 
            # 이전에 저장되어 있는 거리와 현재 계산한 거리를 비교하여 새로운 값을 넣어준다.
                if distances[currentIndex] + g[currentIndex][j] < distances[j]:
                    distances[j] = distances[currentIndex] + g[currentIndex][j]

dijkstra(0)
for i in range(iterator):
    print(f"{distances[i]}", end=" ")