[Python] 최단경로를 찾는 다익스트라(Dijkstra) 알고리즘

- 첫 화면 -

 

---

다익스트라(Dijkstra) 알고리즘

1. 다익스트라 알고리즘은  도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.

 

2. 각 꼭짓점을 최대 한 번씩만 방문가능하며 방문하지 않은 점 중 최단거리인 점을 찾아 방문하여 최단 거리를 정하고 이를 반복한다.

 

---

코드

import heapq

def dijkstra(graph, start):
    # 그래프에서 모든 노드까지의 최단거리를 저장할 딕셔너리 초기화
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    
    # 시작 노드부터의 최단거리를 저장할 우선순위 큐 초기화
    priority_queue = [(0, start)]
    
    while priority_queue:
        # 현재까지의 최단거리와 현재 노드
        current_dist, current_node = heapq.heappop(priority_queue)
        
        # 현재 노드까지의 최단거리가 이미 계산한 거리보다 크다면 무시
        if current_dist > distance[current_node]:
            continue
        
        # 인접한 노드와의 거리 계산 및 업데이트
        for neighbor, weight in graph[current_node].items():
            distance_to_neighbor = current_dist + weight
            if distance_to_neighbor < distance[neighbor]:
                distance[neighbor] = distance_to_neighbor
                heapq.heappush(priority_queue, (distance_to_neighbor, neighbor))
    
    return distance

# 그래프 예제 (딕셔너리 형태로 표현)
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}
}

start_node = str(input("시작 점을 지정 : "))
shortest_distances = dijkstra(graph, start_node)

for node, distance in shortest_distances.items():
    print(f'{start_node}와 {node}의 최단경로 : {distance}')

 

 

---

실행

01234

- 실행 -

 

 

---

마무리

목적지까지의 최단경로를 찾는 다익스트라 알고리즘을 파이썬을 사용해 구현해봤습니다.

 

 지금 배우는 것은 웹개발인데 파이썬에 홀려서 파이썬 공부만 미친듯이 한 것 같습니다.

앞으로 지금처럼 간단한 파이썬 코드는 계속 올리되 주말에는 웹개발 연습해 놓은 것도 천천히 포스팅 해볼 생각입니다.

감사합니다.