Dijkstra algorithm (다익스트라)

# 정의

다익스트라 알고리즘은 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 음의 가중치를 가지는 간선이 없을 때(BFS와 큰 차이점)만 사용할 수 있습니다. 

다익스트라를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. 다른 글에서 설명을 이미 했기 때문에 링크만 올려두겠다.

https://whitem4rk.tistory.com/18

BFS (Breadth First Search )

 

# Code

알고리즘의 동작 방식

1. 시작 정점을 선택합니다.
2. 선택한 정점과 인접한 정점들의 가중치를 계산합니다.
3. 가장 작은 가중치를 가지는 정점을 선택합니다.
4. 선택한 정점을 통해 인접한 정점들의 가중치를 갱신합니다.
5. 모든 정점들이 선택될 때까지 3~4번을 반복합니다.

 

가장 기본적인 다익스트라 파이썬 코드이다.

import heapq

def dijkstra(graph, start):
    dist = [float('inf')] * len(graph)
    dist[start] = 0
    path = [[] for _ in range(len(graph))]
    heap = [(0, start)]
    
    while heap:
        cost, node = heapq.heappop(heap)
        if dist[node] < cost:
            continue
        for neighbor, weight in graph[node]:
            new_cost = dist[node] + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                path[neighbor] = path[node] + [node]
                heapq.heappush(heap, (new_cost, neighbor))
    
    return dist, path

 

# 수행시간

다익스트라 알고리즘의 수행시간은 크게 두 부분으로 나뉩니다.

1. 우선순위 큐에 노드를 추가하거나 삭제하는데 걸리는 시간 O(log|V|)
2. 각 노드의 이웃 노드들을 확인하고, 거리를 갱신하는 과정입니다. 각 노드의 이웃 노드들을 확인하는 과정에서는 모든 간선을 확인해야 하므로 O(|E|)의 시간이 소요됩니다. 이 부분에서 거리를 갱신하는 과정은 우선순위 큐를 사용하므로 O(log|V|)의 시간이 소요됩니다. 따라서 이 부분의 수행시간은 O(|E| log|V|)입니다.

따라서 전체 다익스트라 알고리즘의 수행시간은 O(|E| log|V|)입니다. 이 수행시간은 최악의 경우에도 평균적으로 거의 같은 수준을 유지하기 때문에, 다익스트라 알고리즘은 실제로도 매우 효율적인 알고리즘이며, 대부분의 실제 문제에서도 사용됩니다.

 

# 다익스트라의 실제쓰임

1. 라우팅 테이블을 구성할 때 
2. 네트워크의 최단 경로를 찾을 수 있으며, 이를 통해 네트워크의 중심성과 연결성을 파악
3. GPS 시스템의 효율적인 경로 선택
4. 게임 내에서 NPC의 이동 경로를 결정

 

 

 

 

# Reference

ChatGPT