다익스트라

다익스트라 알고리즘은 방향 그래프 혹은 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구한다.

플로이드 알고리즘 (은 이후 글에서 다루겠다)은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이지만, 다익스트라는 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하게 된다. 뭔가 효율적이고 그리고 쓸 곳이 있으니 이런 것을 배우게 된다.

제약 조건은 음수 가중치가 포함되어 있는 그래프에서는 사용 할 수 없다.

알고리즘 작동 방식

1. 시작 노드를 선택한다. 해당 노드의 거리는 0으로 초기화하고, 다른 노드와의 거리는 infinity로 초기화한다.
2. 우선순위 큐 자료구조를 이용하여 가장 작은 가중치를 가진 노드를 반복적으로 선택한다.
   • 정확하게 말해서 이 상황에서는 우선순위 큐가 별 다른 커맨드 없이 자동정렬을 해주는 것이 크다.
3. 선택된 노드를 통해 갈 수 있는 인접 노드의 거리를 업데이트한다. 더 짧은 경로를 발견하면 갱신한다.

예제

A를 기준으로 시작하자. A에서 연결된 B와 C까지의 거리를 업데이트 한다.

A	0
B	4
C	2
D	Inf
E	Inf

B와 C중 우선 C를 선택한다. C와 연결된 E, D를 본다 :

D로의 거리는 6이다. D를 업데이트 한다. (C (2) + D (4))
E로의 거리는 3이다. E를 업데이트 한다. (C (2) + E (1))

A	0
B	4
C	2
D	6
E	3

E를 우선 선택한다. E의 연결된 노드는 D이다.

D로의 거리는 6이지만, A C E D 순으로 했을 때 4가 나오니 갱신이 필요해졌다.

A	0
B	4
C	2
D	4
E	3

이후 B D 중 아무거나 방문한다. 어쨌든 여기서 더 갱신 될일이 없다. (4 == 4라서 크게 상관이 없다)

 

import heapq

def dijkstra(graph, start):
    # 최단 거리 테이블 초기화
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # 우선순위 큐 생성
    priority_queue = [(0, start)]  # (거리, 노드)

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

        # 이미 계산된 거리보다 큰 경우 무시
        if current_distance > distances[current_node]:
            continue

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

# 예제 그래프
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 3, 'D': 2},
    'C': {'D': 4, 'E': 1},
    'D': {'E': 1},
    'E': {}
}

# 시작 노드
start_node = 'A'
shortest_distances = dijkstra(graph, start_node)

# 결과 출력
print("최단 거리:")
for node, distance in shortest_distances.items():
    print(f"{start_node}에서 {node}까지: {distance}")

끝!