[python] 다익스트라 알고리즘

07 Dec 2023

python

다익스트라 알고리즘은 그래프에서 하나의 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 도로 네트워크, 라우팅 등 다양한 분야에서 응용됩니다.

알고리즘 동작 원리

출발점을 설정하고, 출발점으로부터의 거리를 무한대로 설정합니다.
출발점의 거리를 0으로 설정하고 우선순위 큐에 삽입합니다.
우선순위 큐에서 최단 거리를 가진 정점을 선택하고, 해당 정점과 인접한 정점들의 거리를 갱신합니다.
갱신된 거리와 정점을 우선순위 큐에 삽입합니다.
우선순위 큐가 빌 때까지 3번과 4번의 과정을 반복합니다.
모든 정점까지의 최단 거리를 구할 때까지 3번부터 5번까지의 과정을 반복합니다.

예시 코드

import heapq

def dijkstra(graph, start):
    # 출발점에서 각 정점까지의 거리를 저장하는 배열
    distances = {vertex: float('inf') for vertex in graph}
    # 출발점에서 출발점까지의 거리는 0으로 설정
    distances[start] = 0
    # 우선순위 큐 생성 및 출발점 삽입
    queue = [(0, start)]

    while queue:
        # 가장 짧은 거리를 가진 정점 선택
        current_distance, current_vertex = heapq.heappop(queue)

        # 더 짧은 경로가 이미 발견된 경우 스킵
        if current_distance > distances[current_vertex]:
            continue

        # 인접한 정점들의 거리 갱신
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # 더 짧은 거리를 발견한 경우 거리 갱신 및 정점 삽입
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

사용 예시

# 그래프 생성
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'D': 2},
    'C': {'B': 1, 'D': 1},
    'D': {'A': 1, 'G': 2},
    'E': {'D': 4, 'F': 3},
    'F': {'G': 2},
    'G': {}
}

start = 'A'
distances = dijkstra(graph, start)
print(distances)

알고리즘 동작 원리

예시 코드

사용 예시

참고 문서