알고리즘 중에서 다익스트라 알고리즘에 대해서 조금 정리해보고자 한다. 다 익스트라 알고리즘은 그래프에서 여러 개의 노드가 존재할 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
이 알고리즘은 간선의 값이 양수일 때만 정상적으로 동작한다. 해당 알고리즘은 GPS에서 많이 사용되는 분야이다.
다익스트라 최단 경로 알고리즘은 쉽게 정리하면 매번 가장 거리가 짧은 노드를 선택해서 크기를 비교해 최소값을 업데이트하는 과정을 계속해서 반복하게 된다.
간단하게 도식화한 내용은 아래와 같다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 간선 비용을 계산하여 최단거리 테이블을 업데이트.
- 3~4 과정을 반복한다.
이를 구현하기 위해서는 그래프 이외에도 두개의 리스트가 추가로 더 필요한다. 첫번째는 출발노드로부터 최단 거리를 정리하기 위한 리스트이다. 두번째는 방문했던 노드를 다시 방문하지 않기 위해 방문 여부를 체크하기 위한 리스트이다.
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
intmax = sys.maxsize
#N은 노드의 개수, M은 간선의 개수
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
#start는 우리가 알려고 하는 시작 지점
start = int(input())
for j in range(M):
a, b, c = map(int, input().split())
graph[a].append((b,c))
###이 아래는 그냥 기본 리스틀 이용해서 구현하는 방법
visited = [False] *7
distance = [intmax]*7
def smallindex():
global intmax
min = intmax
index = 0
for i in range(1, N+1):
if not visited[i] and distance[i] < min:
min = distance[i]
index = i
return index
def dijkstra(start):
#시작노드에서 -> 시작노드로 가는 거리는 0으로 바꿔줘야지 / 시작노드는 방문처리 실시함
distance[start] = 0
visited[start] = True
#시작노드의 인접한 노드들에 대해 최단 거리 계산
for i in graph[start]:
distance[i[0]] = i[1]
#시작노드를 제외한 n-1개의 노드들 처리
for _ in range(N-1):
now = smallindex() #방문 한적 없으면서 시작노드와 최단거리인 노드 반환
visited[now] = True #해당 노드 방문처리
#해당 노드의 인접한 노드들 간의 거리 계산
for next in graph[now]:
cost = distance[now] + next[1] #시작 -> {now 거리} + {now -> now 의 인접노드 거리}
if cost < distance[next[0]]: # cost < 시작 ->now의 인접노드 다이렉트 거리
distance[next[0]] = cost
dijkstra(start)
for i in range(1, N+1):
if distance[i] == intmax:
print('도달할 수 없음')
else:
print(distance[i])위의 코드는 가장 단순한 구조로 필요한 만큼 리스트를 생성하여 확인하는 방식이다. 하지만, 이 방식을 사용하게 되면 시간 복잡도가 O(V^2)이다. 노드 개수의 제곱만큼의 시간 복잡도를 가지게 되기 때문에, 더욱 개선된 방식으로 다익스트라를 구현하면 시간 복잡도를 개선시킬 수 있다. 아래의 코드에 이를 적어놓았다.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
intmax = sys.maxsize
#N은 노드의 개수, M은 간선의 개수
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
#start는 우리가 알려고 하는 시작 지점
start = int(input())
for j in range(M):
a, b, c = map(int, input().split())
graph[a].append((b,c))
###힙을 사용한 다익스트라 구현방법 // 입력까지는 동일하다.
def dijkstra_heap(start):
q = []
heappush(q,(0,start))
distance[start] = 0
while q:
dist, node = heappop(q)
#큐에서 뽑아낸 거리가 더 먼 경우에는 실행을 안해버려
if dist > distance[node]:
continue
for next in graph[node]:
cost = distance[node] + next[1]
if cost < distance[next[0]]:
distance[next[0]] = cost
위의 코드는 힙을 사용한 정렬이다. 간선 연결 정보 및 데이터를 저장하는 방식을 사용 할때, 우선순위 큐를 사용해서 만든다. 이렇게 만들게 되면 간선의 가중치가 더 작은(우선순위가 더 큰) 데이터가 우선하여 pop되고, 큐에서 pop되어 나온 데이터 중에서 판단할 가치가 없는 경우 무시하고 넘어갑니다.
해당 방식을 사용하면 시간복잡도가 O(ElogV)로 크게 개선됩니다. 이때, E는 간선의 개수, V는 노드의 개수입니다. 간선의 개수E 가 시간복잡도에 관여하는 이유는, 소스코드를 보면 알 수 있다. 우선순위 큐에서 pop된 노드를 탐색할 때 해당 노드와 연결된 노드들만을 탐색하므로 최악의 경우, 모든 간선의 개수만큼 반복할 수 도 있습니다.
우선순위를 활용한 다익스트라 알고리즘은 E개의 간선을 힙에 넣었다가 빼는 것으로 볼 수 있으므로, O(ElogE)가 되게 하는데, E는 항상 V^2 보다 작으므로 하나의 간선에 대한 시간복잡도는 O(logV)가 되고, 최악의 경우 최대 간선 개수를 고려하면 O(ElogV)가 된다.
