[바킹독 강의] 다익스트라

 

https://blog.encrypted.gg/1037

[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

위 강의자료를 공부하면서 한번 더 생각해본 점들을 기록합니다.

 

왜 O(VE) 일까?

강의 자료 1 ~ 13 페이지 설명을 구현한 로직은 O(VE) 를 가진다고 설명해주셨습니다. 

왜 O(VE)일까를 한번 생각해봤습니다.

 

https://blog.encrypted.gg/1037

 

해당 로직에서는 다음 정점을 찾기위해서 fix 된 정점(노란색 표시된)에서 간선을 탐색하여 4번 5번 정점으로 이동할 수 있습니다. 

따라서 정점의 모든 간선을 탐색하기 때문에 O(VE) 가 되는 것입니다.

 

위와 같은 방식에서 보통 정점의 갯수(V)가 간선의 갯수(E) 보다 작기 때문에 아래 O(VE) 정점의 간선들을 순회하지 않고, 미리 테이블에 거리를 저장해두고 최소값을 찾는 방식 O(V² + E)을 사용합니다.

 

그럼 왜 O(V² + E) 일까?

그럼 미리 테이블에 거리를 저장하는 방식은 왜 O(V² + E) 인 걸까요?

 

강의 자료는 아래의 코드를 예시로 들어주셨습니다.

 

아래는 위 코드를 자바스크립트로 바꾼 코드 입니다.

// (간선 번호, 비용)
const adj = Array.from({ length: 20005 }, () => 0);
const INF = Number.MAX_SAFE_INTEGER;
const fix = Array.from({ length: 20005 }, () => false);
const V = 10;

function dijkstra_naive(st) {
  const d = Array(v + 1).fill(INF); // 거리 테이블을 무한대로 초기화 합니다.
  d[st] = 0;

  while (true) {
    let idx = -1;

    for (let i = 1; i <= v; i++) {
      if (fix[i]) continue;
      if (idx === -1) idx = i;
      else if (d[i] < d[idx]) idx = i;
    }
    if (idx === -1 || d[idx] === INF) break;
    fix[idx] = true;

    for (let [nxt, w] of adj[idx]) {
      d[nxt] = Math.min(d[nxt], d[idx] + w); // 거리를 업데이트 합니다.
    }
  }
}

 

우선 while 문 내부의 for문이 V 만큼 순회하기 때문이고 , 상위 스코프인 while 문은 fix[방문정점] = true 가 되는 조건에 의해 break 되므로  O(V²) 가 됩니다.

그리고 O(E) 인 이유는 idx 가 방문 정점으로 할당되면 해당 정점의 간선을 탐색하기 때문입니다.

 

따라서 위 코드의 시간복잡도는  O(V² + E)가 됩니다.

 

 

다익스트라는 왜 음수 간선이 있는 경우 사용할 수 없는 걸까?

해당 글에서 잘 설명해주시긴하지만, 제가 이런걸 궁금해했구나~ 라는걸 기록하고 싶어서씁니다.

 

다익스트라의 알고리즘 동작을 보면 아직 서거리가 확정되지 않은 정점들 중에서 가장 가까운 정점을 찾아 거리를 확정합니다. 따라서 일종의 그리디 라고 할 수 있습니다.

 

그럼 이를 어떻게 증명해야할까요?

 

https://blog.encrypted.gg/1037

 

1번 정점에서 2,3,4 번 정점으로 뻗어나갔다가 그 중에서 가장 가까운 3번 정점의 거리를 확정짓습니다. 이 상황에서 3번 정점까지의 거리가 2라고 확신할 수 있을까요? 귀류법으로 생각해서 중간에 다른 정점을 거치면 거리 2보다 더 짧은 경로로 갈 수 있다고 가정해보겠습니다.

 

* 귀류법 : 한 명제가 참인 것을 증명할때에 그 명제에 부정을 참이라고 가정하여 거기서 나오는 불합리성을 증명함으로써 원래 명제가 참인것을 보여주는 증명법

 

https://blog.encrypted.gg/1037

 

애초에 이것은 말이될 수 없습니다. 예를 들어 1번에서 2번 정점을 거쳐 3번으로 가는게 , 1번에서 3번으로 바로 가는 것 보다 더 짧은 경로라고 할때 그럼 처음 부터 1번에서 2번 정점을 거쳐 3번으로 가는 경로의 값이 선택되었을 것이기 때문입니다. 음수 간선이 없는 이상 말이죠. 

 

이를 통해 왜 음수 간선이 있을 때 다익스트라를 사용할 수 없는지 또한 알 수 있습니다. 그리디를 사용하는 다익스트라의 논리가 깨져버리기 때문이죠.

 

 

왜 다익스트라 로직 짤 때 우선순위 큐를 사용하게 된 걸까?

다익스트라 알고리즘에서는 매번 가장 가까운 정점을 뽑아내야하기 때문에 원소의 추가가 가능하고 최솟값의 확인/삭제가 효율적인 자료구조인 우선순위 큐(힙)을 사용하게 되었습니다.

 

 

왜 O(E logV) 일까?

 

우선순위 큐에 원소를 넣는 시간복잡도는 O(logN) 입니다. 우선순위 큐에서 꺼낸 정점의 연결된 모든 간선을 탐색하고, 현재 최단거리 테이블에 있는 값보다 작다면 우선순위 큐에 해당 데이터를 넣기 때문에 O(E logV) 를 가진다고 할 수 있습니다.

 

* 힙정렬에 소요되는 시간복잡도도 O(N logN) 입니다.

* O(E logE) 로 알고 계시는 분들도 있으실텐데 big-O 측면에서 O(E logE) 와 O(E logV)는 동일합니다.