최단 경로 문제
- 두 노드를 잇는 가장 짧은 경로를 찾는 문제
- 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적
최단 경로 문제 종류
- 단일 출발 및 단일 도착 최단 경로 문제
- 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로 찾는 문제
- 단일 출발 최단 경로 문제
- 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
- 전체 쌍 최단 경로
- 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제
다익스트라 알고리즘
다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제에 적절
다익스트라 알고리즘 로직
- 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며 최단 거리를 갱신하는 기법
- 다익스트라 알고리즘은 BFS와 유사
- 첫 정점부터 각 노드 간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드 간의 가장 짧은 거리를 해당 배열에 업데이트
- 우선순위 큐를 활용 : 우선순위 큐는 Min Heap방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
- 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
- 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장(inf)
- 우선순위 큐에 (첫 정점, 0)만 먼저 넣음
- 우선순위 큐에서 노드를 꺼냄
- 처음에는 첫 정점만 저장되어 있으므로, 첫 정점만 꺼내짐
- 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교
- 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우 배열에 해당 노드의 거리를 업데이트
- 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다
-> 결과적으로 너비 우선 탐색과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
-> 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우에 해당 노드와 인접한 노드 간의 거리 계산을 하지 않음
- 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복
- 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
알고리즘 구현
graph = {
'A': {'B': 8, 'C': 1, 'D': 2},
'B': {},
'C': {'B': 5, 'D': 2},
'D': {'E': 3, 'F': 5},
'E': {'F': 1},
'F': {'A': 5}
}import heapq
def dijkstra(graph, start):
distances = { node: float('inf') for node in graph }
distances[start] = 0
pq = []
heapq.heappush(pq, [distances[start], start])
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for adjacent, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[adjacent]:
distances[adjacent] = distance
heapq.heappush(pq, [distance, adjacent])
return distances
*A부터 F까지의 최단 경로 출력 코드
import heapq
def dijkstra(graph, start, end):
distances = {node: [float('inf'), start] for node in graph}
distances[start][0] = 0
pq = []
heapq.heappush(pq, [distances[start][0], start])
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node][0]:
continue
for adjacent, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[adjacent][0]:
distances[adjacent] = [distance, current_node]
heapq.heappush(pq, [distance, adjacent])
path = end
path_output = [end]
while distances[path][1] != start:
path_output.append(distances[path][1])
path = distances[path][1]
path_output.append(start)
path_output = list(reversed(path_output))
return path_output
result = dijkstra(graph, 'A', 'F')
print(result)
print("->".join(result))
"""
['A', 'D', 'E', 'F']
A->D->E->F
"""
시간 복잡도
- 과정 1: 각 노드마다 인접한 노드 간선(E)들을 모두 검사 => O(E)
- 과정 2: 우선순위 큐에 노드/거리 정보를 넣고 삭제하는 과정 => O(ElogE)
- 과정 1 + 과정 2의 시간을 합치면 결국 O(ElogE)
'Algorithm > 탐색' 카테고리의 다른 글
| BFS와 DFS (0) | 2020.03.26 |
|---|---|
| 이진탐색(Binary search) (0) | 2020.03.13 |