다익스트라

다익스트라(Dijkstra)는 간선에 비용이 있는 그래프에서

시작점부터 다른 정점까지의 최단거리를 구할 수 있는 단일 시작점 최단거리 알고리즘입니다.

이 때 간선의 비용이 음수가 아닐 경우에만 가능하며 간선의 비용이 음수일 경우 추후 배울 벨만 포드 알고리즘을 사용합니다.

다익스트라 알고리즘은 dist배열을 사용하며, dist[i]는 시작점에서 i번 정점까지의 최단거리를 뜻합니다.

시작점의 dist값은 0, 나머지 모든 정점은 무한대로 초기화한 뒤 시작점을 방문하는 것을 시작으로,

아직 방문하지 않은 정점들 중 시작점으로부터 가장 거리가 작은 정점(u)을 방문한 뒤

해당 정점(u)을 거쳐서 인접한 정점(v)으로 가는 거리(cost)가 dist에 있는 값보다 더 작을 경우(dist[v] > dist[u] + cost)

dist값을 갱신하며 모든 정점을 방문 할 때까지 반복합니다.

이 때 효율성을 위하여 dist값을 갱신할 때마다 시작점부터 그 정점까지의 거리(dist[v])와 그 정점(v)을 우선순위 큐에 넣어

시작점으로 부터 가장 거리가 작은 정점을 빠르게 찾아낼 수 있습니다.

이로인하여 그래프를 인접리스트로 표현하였을 경우 다익스트라 알고리즘의 시간복잡도는

정점 개수가 V 간선 개수가 E일 때 O(ElgV)이며

최단거리 문제에 많이 응용되므로 동작과정의 확실한 이해가 필요한 알고리즘입니다.

기본 문제

1753번: 최단경로

1504번: 특정한 최단경로

1261번: 알고스팟