Today I learned
2022/02/07
회고록
2/07
항해 99, 알고리즘 4주차
교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)
다익스트라
1. 이론
다익스트라(Dijkstra) 알고리즘이란?
다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.
다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능)
다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다.
- 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)
- 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.
위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자.
1차원 배열 dist[]에 각 정점까지의 최단거리를 갱신해 나갈 것이다. 초기에는 모두 INF(무한대)로 설정한다.
가장 먼저 시작정점을 방문한다.
시작 정점에서 방문 할 수 있는 정점들에 대한 거리를 갱신한다.
방문하지 않은 정점 중 가장 가중치가 작은 2번 정점을 방문한다.
0번 정점에서 2번 정점을 거쳐서 4번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다 ( INF > 11)
0번 정점에서 2번 정점을 거쳐서 3번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다 ( 7 > 6 )
방문하지 않은 정점 중 가장 가중치가 작은 3번 정점을 방문한다.
0번 정점-2번 정점-3번정점을 거쳐서 4번 정점을 가면 기존 거리보다 최단 거리이므로 갱신한다( 11> 10 )
방문하지 않은 정점 중 가장 가중치가 작은 4번 정점을 방문한다.
갱신할 거리가 없다.
방문하지 않은 정점 중 가장 가중치가 작은 1번 정점을 방문한다.
갱신할 거리가 없다.
모든 정점을 방문했으므로 종료한다.
위와 같은 과정을 거치면 dist 배열에 0번정점부터 각 정점까지의 최단거리가 기록되게 된다.
2. 구현
힙구조 없이 구현
시간복잡도 O(N^2)
import sys
def dijkstra(graph, start):
visited = [False] * (n + 1) # 방문처리 기록용
distance = [INF] * (n + 1) # 거리 테이블용
def smallest_cost():
min = INF
idx = 0
for i in range(len(distance)):
if visited[i] is False and distance[i]!=INF:
if min > distance[i]:
min = distance[i]
idx = i
return idx
def algo(start):
#시작지점 처리
visited[start] = True
distance[start] = 0
#시작노드에서 가는 지점들의 거리와 비용 업데이트
for dest_cost in graph[start]:
distance[dest_cost[0]] = dest_cost[1]
for _ in range(n-1):
now = smallest_cost()
visited[now] = True
#해당 노드에서 뻗어나가는 길, 비용 계산 후 업데이트
for dest_dist in graph[now]:
cost = distance[now] + dest_dist[1]
#목적지가 방문처리 전이고, 거리가 재산정 비용보다 크면
if distance[dest_dist[0]] > cost:
distance[dest_dist[0]] = cost
algo(start)
return distance
if __name__ == '__main__':
input = sys.stdin.readline
INF = int(1e9)
n, m = 6, 11
start = 1
graph = [
[],
[[2,2],[3,5],[4,1]],
[[3,3],[4,2]],
[[2,3],[6,5]],
[[3,3],[5,1]],
[[3,1],[6,2]],
[]
]
result = dijkstra(graph, 1)
print(f'{result}')힙구조를 이용한 다익스트라 구현
시간복잡도 O(NlogN)
import heapq # 우선순위 큐 구현을 위함
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph} # start로 부터의 거리 값을 저장하기 위함
distances[start] = 0 # 시작 값은 0이어야 함
queue = []
heapq.heappush(queue, [distances[start], start]) # 시작 노드부터 탐색 시작 하기 위함.
while queue: # queue에 남아 있는 노드가 없으면 끝
current_distance, current_destination = heapq.heappop(queue) # 탐색 할 노드, 거리를 가져옴.
if distances[current_destination] < current_distance: # 기존에 있는 거리보다 길다면, 볼 필요도 없음
continue
for new_destination, new_distance in graph[current_destination].items():
distance = current_distance + new_distance # 해당 노드를 거쳐 갈 때 거리
if distance < distances[new_destination]: # 알고 있는 거리 보다 작으면 갱신
distances[new_destination] = distance
heapq.heappush(queue, [distance, new_destination]) # 다음 인접 거리를 계산 하기 위해 큐에 삽입
return distances
if __name__ == '__main__':
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}
}
result = dijkstra(graph, 'A')
print(f'{result}')```
