다익스트라(Dijkstra) 알고리즘에 대해서 알아보기

다익스트라(Dijkstra) 알고리즘에 대해서 알아보기

300x250

다익스트라 알고리즘이란?

하나의 출발점(단일 노드)으로 부터 시작하여 다른 도착점(도착 노드)으로 가는 모든 경로(간선) 중 가장 짧은 경로 를 구하는 알고리즘입니다.-대표적으로 최단경로 구하기, 미로 탐색 알고리즘을 해결하는데 쓰입니다.

다익스트라 알고리즘의 구현 과정

1. 최단 거리가 담겨있는 배열을 만들고 출발점을 선택하여 출발 노드에는 0, 다른 노드에는 INF값을 채워 넣습니다.

(보통 각 노드 사이의 거리 중 max값을 INF값으로 설정합니다.)

2. 현재 노드를 출발점으로 초기화하고 현재 노드로부터 이어져 있는 노드 간의 경로를 INF값과 비교하며 최단 거리 값을 경신합니다.

3. 미방문 노드 중에서 최단거리가 가장 짧은 노드를 선택하고 출발점으로 갱신합니다. 기존 출발점과 현재 출발점의 거리와 현재 출발점에서 다른 노드 간의 거리 합과 기존 최단거리 배열에 저장돼 있던 값을 비교하면서 재갱신합니다.

4. 현재 출발점은 방문 처리를 하고 방문이 안된 다른 노드에 한하여 위와 같은 과정을 반복합니다.

이러한 과정은 모든 노드를 방문하거나 미방문 노드를 선택할 수 없게 될 때까지 반복하게 되며 최단 거리가 담겨있는 배열의 값이 출발점과 특정 노드까지의 최단거리가 됩니다.

과정만 설명하고 이해하기에는 어려움이 있으므로 백준 온라인 저지의 1753번 '최단경로' 문제를 풀면서 풀이를 통하여 설명해 보도록 하겠습니다.

1753번 '최단경로' 문제

예제는 다음과 같이 주어져 있습니다.

문제 푸는 데에 직접적인 도움이 된다고 할 수 없지만 문제를 보다 쉽게 이해하는데 도움이 될 듯하여 예제의 구조를 이미지로 나타내 보았습니다.

예제 구조

풀이(python)

import sys input=sys.stdin.readline INF=sys.maxsize #시스템이 지정할 수 있는 최댓값 V,E=map(int,input().split()) #정점의 개수V, 간선의 개수E start=int(input()) #시작 노드 번호 graph = [[] for _ in range(V+1)] #연결 노드에 대한 정보를 담은 리스트 visited = [False] * (V+1) #방문 체크 리스트 distance = [INF] * (V+1) #최단 거리 리스트 for _ in range(E): #a번 노드에서 b번 노드로 가는 비용이 c a,b,c = map(int, input().split()) graph[a].append((b,c)) def smallest_node(): #미방문 노드 중 가장 짧은 노드를 반환 min_value=INF index=0 for i in range(1,V+1): if distance[i]

출력 결과

결과는....

위와 같은 방법으로 최단거리를 구할 수 있지만 최단 거리가 가장 짧은 노드(smallest_node)를 구하는 과정에서 시간을 추가적으로 소요(선형 탐색 과정을 거침) 하기 때문에 전체 노드의 개수가 많을 경우 매우 비효율적입니다.

시간 복잡도= O(V^2)

따라서 최단 거리를 보다 빨리 구하기 위해서는 이러한 탐색에 걸리는 시간을 단축해야 하는데 이때 쓰이는 자료구조가 우선순위 큐입니다. (우선순위 큐를 해결하기 위해 힙(heap) 사용)

시간 복잡도= O(E*logV)

E=우선순위 큐에 들어갈 수 있는 최대 원소의 크기

힙을 이용한 풀이

import sys import heapq input = sys.stdin.readline INF = sys.maxsize V, E = map(int, input().split()) start = int(input()) graph = [[] for _ in range(V+1)] visited = [False] * (V+1) distance = [INF] * (V+1) for i in range(E): a,b,c = map(int, input().split()) graph[a].append((b,c)) def dijkstra(start): q = [] distance[start] = 0 heapq.heappush(q, (0, start)) while q: dist, check = heapq.heappop(q) if visited[check] == True: continue for i in graph[check]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) dijkstra(start) for i in range(1, V+1): if distance[i] == INF: print('INF') else: print(distance[i])

+공부에 도움이 된 자료들의 출처입니다.

다익스트라 알고리즘 개념 확립

https://www.youtube.com/watch?v=tZu4x5825LI&t;=204s

본 출처: EBS링크 소프트웨어 세상(가장 빠른 길을 찾아라, 최단경로 알고리즘)

다익스트라 알고리즘 문제 적용

https://www.youtube.com/watch?v=acqm9mM1P6o&t;=2705s

동빈나님의 이코테2021 강의 몰아보기

from http://lbdiaryl.tistory.com/164 by ccl(A) rewrite - 2021-09-24 21:26:28