Data Structure and Algorithms (11)
1.최단경로 알고리즘
최단경로 문제
두 노드를 잇는 가장 짧은 경로를 찾는 문제
가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제
최단경로문제 종류
1) 단일 출발 및 단일 도착
그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로 찾는 문제
2) 단일 출발 최단 경로 문제
그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로 찾는 문제
3) 전체 쌍 최단 경로 : 그래프 내의 모든 노드 쌍 (u,v) 각각 가장 짧은 경로를 찾는 문제
다익스트라 알고리즘 (Dijkstra Algorithm)
(2번 문제에 해당)
- 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며 최단거리를 갱신하는 기법
- BFS와 유사 : 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
-> 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식에 집중
우선순위 큐를 활용한 다익스트라 알고리즘
-> 우선순위 큐는 Min Heap 방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장 (inf라고 표현)
우선순위 큐에 (첫 정점, 거리0) 먼저 넣음
2) 우선순위 큐에서 노드를 꺼냄
처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트
배열에 해당 노드의 거리가 업데이트 된 경우, 우선순위 큐에 넣는다
-> 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문
-> 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴거리를 가진 경우에는 해당 노드와 인접한 노드간의거리계산을 하지않음
3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때가지 반복
정리
1) 먼저 본인 말고 inf
2) 인접한 노드부터 거리 확인 후 우선순위 큐에 넣음
3) pop을 해서 해당 노드와 인접한 거리의 가중치 계산 (큐에 넣음)
4) 이 때 인접 노드 값의 업데이트가 필요 (해당 노드 전 거리 + 해당 노드와의 거리)
5) 주의 : 기존 값과 비교해서 더 낮은 값을 저장 or 남김
6) 계속 pop 반복
코드
큐라는 구조에 힙형태로 넣음
그래프의 자료구조
mygraph = ( ‘A’ : {‘B’ : 8, ‘C’ : 1, ‘D’ : 2}, ‘B’ = {}, ‘C’ : {‘B’ : 5, ‘D’ : 2}, ‘D’ : {‘E’ : 3, ‘F’ : 5}, ‚E‘ : {‚F‘ : 1}, ‚F‘ : { ‚A‘ : 5} )code
import heapq ㅤ def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 queue = [] heapq.heappush(queue, [start, distances[start]) ㅤ while queue: current_node, current_distance = heapq.heappop(queue) if distances[current_node] < current_distance: continue // distances 딕셔너리 에저장된 값보다 heap에서 꺼낸 값이 더 크다면 값을 업데이트 할 필요가 없기 때문에 아래 반복문이 불필요하다. ㅤ for adjacent, weight in graph[current_node].items(): //딕셔너리 내부의 딕셔너리 (인접노드 : 거리) distance = current_distance + weight // 이전 노드까지의 거리 + 가중치 if distance < distances[adjacent]: // 새로운 값보다 원래 값이 크다면 distances[adjacent] = distance // 값 업데이트 heapq.heappush(queue, [adjacent, distance]) // enqueue ㅤ return distances
최단 경로 출력
code
import heapq ㅤ def dijkstra(graph, start, end): distances = {node: [start, float('inf')] for node in graph} distances[start] = [start, 0] queue = [] heapq.heappush(queue, [start, distances[start][1]) ㅤ while queue: current_node, current_distance = heapq.heappop(queue) if distances[current_node][0] < current_distance: continue // 더 짧은 경로가 있다면 무시한다. ㅤ for adjacent, weight in graph[current_node].items(): distance = current_distance + weight if distance < distances[adjacent][1]: // 만약 시작 정점에서 인접 정점으로 바로 가는 것보다 현재 정점을 통해 가는 것이 더 가까울 경우에는 distances[adjacent] = [current_node, distance] heapq.heappush(queue, [adjacent, distance]) // 거리를 업데이트합니다. ㅤ path = end path_output = end + '->' while distances[path][0] != start: path_output += distances[path][0] + '->' path = distances[path][0] path_output += start print (path_output) ㅤ return distances ㅤ *방향그래프* mygraph = { 'A': {'B': 8, 'C': 1, 'D': 2}, 'B': {}, 'C': {'B': 5, 'D': 2}, 'D': {'E': 3, 'F': 5}, 'E': {'F': 1}, 'F': {'A': 5} } ㅤ print(dijkstra(mygraph, 'A', 'F'))
시간복잡도
과정1 : 각 노드마다 인접한 간선들을 모두 검사
과정2 : 우선순위 큐에 노드/거리 정보를 넣고 삭제하는 과정
과정1 : 각 노드는 최대 한 번씩 방문 / 그래프의 모든 간선은 최대 한 번씩 검사 : O(E)
과정2 : 우선순위 큐에 가장 많은 노드, 거리정보 들어가는 경우, 우선 순위 큐에 노드/거리정보를 넣고 삭제하는 과정이 최악의 시간
-> 그래프의 모든 간선이 검사될때마다 배열의 최단거리가 갱신되고 + 우선순위 큐에 노드/거리가 추가되는 경우가 최악의 상황
-> 이 때 추가는 각 간선마다 최대 한 번, 최대 O(E), + 우선순위 큐를 유지하는 작업 O(log E) : O(E log E)
총 : O(E log E)
본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.
