다익스트라 알고리즘

다익스트라란

그래프 이동 알고리즘 중 하나.

어느 한 vertex 에서 다른 vertex 로 이동할 때 과정을 최소비용으로 구성할 수 있습니다.

BFS 와는 조금 다른 것이 BFS 에서는 모든 경로에 대한 비용이 같은 값인 셈입니다. 우선순위가 동등한 상태입니다.

다익스트라의 추가적인 조건으로는 비용이 음수여서는 안된다.

 

시간복잡도, 공간복잡도

다익스트라의 시간복잡도는 O(ElogV)이고, 공간복잡도는 O(V+E)입니다.

 

시간복잡도와 공간복잡도를 먼저 알려드린건 어떤 식으로 진행될지 대략적으로 참고를 하셨으면 해서 입니다.

 

E 는 Edge 간선의 수, V 는 Vertex 노드의 수 입니다.

 

시간복잡도는 최악의 경우 모든 간선을 이동하며(E) 접근하게된 노드들을 우선순위 큐에 삽입하는 정도의 시간(logV)이라 생각하면 되겠습니다.
공간복잡도는 간선정보의 E, 우선순위 큐와 비용정보를 담기 위한 V 가 각각 있습니다.

 

흐름

시작노드를 정했으면 해당 노드에서 갈 수 있는 모든 간선에 대한 정보 (해당 노드 번호와 거기까지 가기 위한 비용(시작노드부터 해당 노드까지 전체 비용)) 를 우선순위 큐에 넣습니다.

이렇게 가장 비용이 적은 간선을 이용해 아직 접근하지 못한 노드에 가장 적은 비용으로 접근합니다. 그리고 새로운 노드에 도착하였다면 그 노드에서 갈 수 있는 모든 간선에 대한 정보를 우선순위 큐에 넣고 이를 반복합니다.

 

구현

필요한 요소들로는 그래프이다보니 인접행렬이나 인접 리스트가 필요합니다. 그리고 우선순위 큐가 필요하고 방문기록과 거리에 따른 비용을 저장해야합니다. 방문기록과 거리는 하나의 행렬로 대처가능합니다.
방문기록과 거리를 하나의 행렬로 사용하는 것은 매번 최소한의 값이 다뤄짐이 보장되므로 이미 방문한 곳엔 최소한의 값을 저장하여 다른 곳에서 해당 노드를 방문하려하면 이보다 값이 클 것이기 때문에 크기비교만으로 방문기록을 따질 수 있다. 비용도 저장하고 방문기록도 처리하고 일석이조 만만세다.

 

소스코드

BOJ 1916 문제풀이 (다익스트라 사용)

from sys import stdin
from heapq import heappush, heappop

n = int(stdin.readline())
m = int(stdin.readline())

edges = [[] for _ in range(n+1)]

for _ in range(m):
    f1, f2, cost = map(int, stdin.readline().split())
    edges[f1].append((f2, cost))

st, dst = map(int, stdin.readline().split())

dist = [500000000 for _ in range(n+1)]
pq = [(0,st)]
while pq:
    cur_cost, cur_id = heappop(pq)
    if dist[cur_id] < cur_cost: continue
    for next_id, next_cost in edges[cur_id]:
        if dist[next_id] <= cur_cost + next_cost: continue #  < 아니라 <= 인것은 비용 0일 시 순환 방지.
        dist[next_id] = cur_cost + next_cost
        heappush(pq, (cur_cost + next_cost,  next_id))

print(dist[dst])