다익스트라 알고리즘 - 최단 경로 알고리즘

다익스트라 알고리즘은 최단 경로 알고리즘 중에 하나로,

시작점에서부터 모든 점까지의 최단 경로를 구하는 알고리즘이다.

다익스트라 알고리즘은 다음과 같이 진행된다.

위와 같이 최단 경로를 항상 갱신하면서

최단 거리가 가장 짧은 노드를 선택해 알고리즘을 진행한다.

만약 그때마다 최소를 구한다면 최악의 경우 $O(V^2)$이 소요되기에

다른 방식이 필요하다.

항상 최소를 선택해야 하기 때문에 우선순위 큐를 사용한다.

향상된 알고리즘의 시간복잡도는 $O(ElogV)$이다.

간선의 총 수가 E개 라고 할 때 간선 개수만큼 소요되고,

그때마다 우선순위 큐에 push pop 을 수행하기 때문에

최악의 경우 $ElogV^2$이 소요된다. (노드끼리 간선이 양방향 연결돼 있을 때)

근데 $logV^2$은 $2logV$로 표현되어 최종 시간복잡도는 $O(ElogV)$이다.

시간 복잡도에서 다시 돌아와서, 아래는 본 과정이 진행되는 것의 이미지이다.

먼저 시작점을 우선순위 큐에 넣고, 거리를 0으로 만든다.

그리고 1에서 갈 수 있는 노드들을 우선순위 큐에 넣게 되는데,

이때 최단 거리 테이블이 갱신되면 큐에 넣고, 그렇지 않으면 넣지 않는다.

그리고 이 과정을 게속 반복한다.

이미지 출처 : 이것이취업을위한코딩테스트다