[TIL] 다익스트라 Dijkstra

다익스트라 Dijkstra

최단 경로 Shortest Path 탐색 알고리즘 
가중 방향 그래프 G = (V, E) 에서 모든 간선의 가중치가
음이 아닌 경우에 단일 출발점 최단 경로 문제를 푼다 

 

다익스트라 특징

1. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다 

2. 가중치가 음수인 경우는 적용이 될 수도 있고 안 될 수도 있다

3. 무방향 그래프, 방향 그래프 모두 사용 가능하다 

 

다익스트라 동작 과정

1. 시작 정점 설정 - 시작 정점을 설정하고, 그 정점에서 다른 모든 정점으로 가는 최단 거리를 계산한다
                 처음에는 시작 정점의 거리를 0으로, 나머지 모든 정점의 거리는 무한대로 설정
2. 미방문 정점 중 최단 거리 선택 - 아직 방문하지 않은 정점들 중에서 가장 짧은 거리를 가진 정점을 선택한다
3. 거리 갱신 - 선택된 정점에서 연결된 이웃 정점들로 가는 거리를 계산하고, 기존 거리보다 짧다면 갱신한다
4. 방문 처리 - 선택된 정점을 방문 처리하여 이후 다시 선택되지 않도록 한다
5. 반복 - 모든 정점을 방문할 때까지 2-4 단계를 반복한다 

 

다익스트라 코드 구현

1. 딕셔너리를 이용한 다익스트라 코드 구현 

import heapq

def dijkstra(graph, start):
    # 거리 테이블을 무한대로 초기화하고, (노드, 거리) 형태로 저장
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 우선순위 큐 초기화 
    # 거리를 기준으로 정렬하기 위해 (거리, 노드) 형태로 저장 
    queue = [(0, start)]  

    while queue:
    	# heapq.heappop() 로 queue 에서 제일 짧은 거리를 가진 노드를 꺼낸다 
        current_distance, current_node = heapq.heappop(queue)

        # 현재 처리 중인 노드의 거리가 기록된 거리보다 크다면 
        # 이미 최적의 경로로 처리되었으므로 무시한다 
        # current_distance 는 우선순위 큐에서 꺼낸 값
        # dist[current_node] 현재 노드까지의 최단 거리
        if current_distance > dist[current_node]:
            continue

		# for 문으로 인접 노드와 가중치 차례로 확인 
        for next_cost, next_node in graph[current_node].items():
            new_distance = current_distance + next_node

            # 더 짧은 경로가 발견되면 거리 테이블을 갱신하고 우선순위 큐에 추가
            if dist[next_cost] > new_distance:
                dist[next_cost] = new_distance
                heapq.heappush(queue, (new_distance, next_cost))

    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}
}

start_node = 'A'
print(dijkstra(graph, start_node))
# 결과 출력
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

 .items() 메서드

딕셔너리의 키와 값을 모두 가져와서 튜플 형태로 반환한다

ex. graph[current_node] = {'B': 1, 'C': 4} 라면, items() 는 ('B', 1) 과 ('C', 4) 반환

example = {'a': 1, 'b': 2}
for key, value = in example.items():
	print(key, value)
# 출력 결과
# a 1
# b 2

 

2. 리스트를 이용한 다익스트라 코드 구현