[파이썬] 다익스트라 알고리즘의 원리와 구현
다익스트라(Dijkstra) 알고리즘은 그래프에서 단일 출발점 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 네덜란드의 컴퓨터 과학자인 에츠헨 다익스트라가 1956년에 개발하였으며, 전체 그래프에서 특정 출발점부터 다른 모든 정점까지의 최단 경로를 계산합니다.
알고리즘 원리
다익스트라 알고리즘은 다음과 같은 원리로 동작합니다.
- 출발점을 설정하고, 출발점에서 자기 자신까지의 최단 경로를 0으로 설정합니다.
- 출발점에서 직접 연결된 모든 정점들의 거리를 계산합니다. 이때, 연결되지 않은 정점들의 거리는 무한대로 설정합니다.
- 아직 방문하지 않은 정점들 중에서 가장 최단 거리를 갖는 정점을 선택합니다.
- 해당 정점과 연결된 정점들의 거리를 갱신합니다. 이때, 현재까지의 최단 거리와 새로운 경로를 비교하여 더 짧은 거리로 갱신합니다.
- 출발점부터 모든 정점까지의 최단 거리를 구할 때까지 3번과 4번의 과정을 반복합니다.
파이썬으로 다익스트라 알고리즘 구현하기
이제 파이썬으로 다익스트라 알고리즘을 구현해보겠습니다. 아래의 예제 코드는 인접 행렬과 우선순위 큐(priority queue)를 사용하여 다익스트라 알고리즘을 구현한 것입니다.
import heapq
def dijkstra(graph, start):
distances = [float('inf')] * len(graph)
distances[start] = 0
queue = []
heapq.heappush(queue, (distances[start], start))
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for adjacent_node, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[adjacent_node]:
distances[adjacent_node] = distance
heapq.heappush(queue, (distance, adjacent_node))
return distances
위의 코드에서 graph는 인접 행렬로 표현된 그래프를 나타냅니다. start는 출발점의 인덱스를 의미합니다. 알고리즘의 결과로 각 정점까지의 최단 거리를 담은 리스트 distances를 반환합니다.
실행 예제
다음은 예제 그래프와 출발점을 설정하여 다익스트라 알고리즘을 실행하는 예제입니다.
graph = [
[(1, 7), (2, 9), (5, 14)],
[(0, 7), (2, 10), (3, 15)],
[(0, 9), (1, 10), (3, 11), (5, 2)],
[(1, 15), (2, 11), (4, 6)],
[(3, 6), (5, 9)],
[(0, 14), (2, 2), (4, 9)]
]
start = 0
distances = dijkstra(graph, start)
print(distances)
위의 코드를 실행하면 출발점인 정점 0으로부터 각 정점까지의 최단 거리를 계산하여 출력합니다.
이렇게 다익스트라 알고리즘을 구현하고 실행할 수 있습니다. 다익스트라 알고리즘은 네트워크 라우팅 등 다양한 문제에 활용되며, 그래프에서 최단 경로를 구하는 데 유용한 알고리즘입니다.