Dijkstra Algorithm

데이크스트라(Dijkstra) 알고리즘

그래프에서 최단 경로를 찾는 알고리즘 중 하나로, 1956년에 에츠허르 데이크스트라(Edsger W. Dijkstra)에 의해 고안되었습니다. 데이크스트라 알고리즘은 주로 가중치가 있는 그래프에서 사용되며, 각 간선의 가중치는 음수가 아닌 값으로 가정합니다.

진행 순서

1 .시작 노드 설정

2. 시작 노드로부터의 최단 거리를 나타내는 배열 dist를 초기화, 시작 노드의 거리는 0, 나머지 노드의 거리는 무한대로 설정

3. 방문하지 않은 노드 중에서 거리가 최소인 노드를 선택, 현재 노드로 설정

4. 현재 노드와 연결된 이웃 노드들에 대해 거리를 업데이트
   -> dist[이웃 노드] = min(dist[이웃 노드], dist[현재 노드] + 현재 노드와 이웃 노드 사이의 거리)

5. 모든 노드를 방문할 때까지 3번과 4번의 과정을 반복

시간 복잡도

인접 리스트를 사용한 경우: O(|V|^2) (|V|: 노드의 개수)
우선순위 큐를 사용한 경우: O(|E|log|V|) (|E|: 간선의 개수)

데이크스트라 알고리즘은 너비 우선 탐색(BFS)과 비슷한 구조를 가지지만, BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데에 적합하고, 데이크스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 사용됩니다. 또한, 데이크스트라 알고리즘은 음수 가중치를 갖는 그래프에서 정확한 결과를 얻을 수 없으므로, 음수 가중치가 있는 경우 벨만-포드 알고리즘(Bellman-Ford Algorithm) 등의 다른 알고리즘을 사용해야 합니다.

파이썬 예제

import heapq

def dijkstra(graph, start):
    # 거리를 나타내는 dist 배열을 초기화합니다.
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    # 우선순위 큐를 사용하여 방문하지 않은 노드를 관리합니다.
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 이미 방문한 노드는 스킵합니다.
        if current_distance > dist[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 현재 노드를 거쳐 이웃 노드로 가는 거리가 더 짧다면, 거리를 업데이트하고 큐에 추가합니다.
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return dist

# 그래프 예제 (노드와 간선의 가중치를 나타냅니다)
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# 다익스트라 알고리즘을 사용하여 시작 노드 A로부터의 최단 거리를 구합니다.
shortest_distances = dijkstra(graph, 'A')
print(shortest_distances)

출력 결과:

{'A': 0, 'B': 1, 'C': 3, 'D': 4}