[최단경로] 다익스트라(Dijkstra) 알고리즘

🍀 목차
다익스트라 알고리즘
같은 목적을 가진 알고리즘
최단경로 알고리즘과 MST와의 차이점은 뭐지?
기본 이해
구현(JavaScript)
왜 음수 가중치에서는 사용이 불가능한 것일까?
시간 복잡도
따라서...

 

다익스트라 알고리즘

• 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 최단 경로를 찾기 위한 알고리즘 중 하나.
• 기본적으로 그리디 알고리즘을 바탕으로 하고 있다. 거리를 기록하며 이미 최단 경로를 구한 곳은 다시 구할 필요가 없기 때문에 다이나믹 프로그래밍으로 보기도 한다.
  • 항상 최단 경로를 찾고 탐욕적으로 선택한다. - 그리디
  • 이미 계산된 경로를 저장후, 그를 활용해 중복된 하위 문제를 푼다. - DP
• 다익스트라 알고리즘은 음수 가중치가 포함된 그래프에서는 사용할 수 없다. 이유 알아보기

 

같은 목적을 가진 알고리즘

• BFS : 가중치가 없는 그래프. 시작점에서 큐에 인접노드를 넣어가며 방문하지 않은 노드들을 탐색하여 목적점에 도착하면 종료하는 탐색방식인데, 가중치가 있으면 돌아서 오는 가중치 합이 최단 경로가 될 수 있어 순수 BFS 탐색방식으로는 탐색할 수 없는 것이다. 하지만 BFS는 다익스트라 알고리즘의 기본 아이디어다. BFS + 우선순위 큐로 삽입된 정보 중 가장 최단 거리부터 꺼내 방문하는 방식이 다익스트라 알고리즘이다. 
• 벨만-포드(Bellman-Ford) : 음수 가중치가 포함되어도 최단 거리를 찾을 수 있다. 시간 복잡도가 다익스트라보다 느리다. 그 이유는 미방문 노드 중 가중치가 가장 짧은 노드를 선택해 뽑아오는 다익스트라와는 달리 각 정점들을 차례로 탐색하며 해당 정점의 간선들을 모두 탐색한다. 벨만-포드의 이러한 특성은 음수 가중치가 포함되어도 최단 거리를 찾을 수 있는 이유기도 하다. 또한 음수 사이클 유무를 판단 가능하다.
• 플로이드-워셜(Floyd-Warshall) : 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 앞 방식들에 비해 플로이드-워셜은 모든 노드 간의 최단 거리를 구할 수 있다. 음수 가중치가 포함되어도 된다. 다만 3중 for문을 사용하기에(최악 O(n^3)), 문제의 범위를 잘 확인한 후 적용해야 한다.

 

최단경로 알고리즘과 MST와의 차이점은 뭐지?

 매번 너무 헷갈렸던 MST(Minimum Spanning Tree : 최소 신장 트리)와의 차이점... (개념이 제대로 안 잡혀있다. 😅)

최단 경로는 말 그대로 시작 정점 -> 목적 정점으로의 최단 경로를 알아내는 것이라면(플로이드-워셜은 모든정점) MST는 정의 자체가 모든 정점을 잇는 최소 비용 Spanning Tree를 구하는 것이다. 사무실 모든 전화기를 가장 적은 간선과 비용으로 이어주는 느낌인 것... MST는 두 노드 사이의 최단 거리를 보장하지 않으며(모든 정점을 이어야 하니까 전체적인 최소 비용을 고름), 다익스트라는 유/무향 그래프에서 모두 동작하지만, MST 알고리즘은 무향 가중치 그래프에서만 동작한다. 

 

기본 이해

 다익스트라 알고리즘은 다음과 같은 순서로 실행된다. 위의 그림에서 A -> D(출발지 A부터 목적지 E까지)의 가중치 합이 최소인 최단 경로를 알아보자. 알파벳 순서가 인덱스 순서라고 가정, G[A][B]는 A와 B사이의 거리(가중치)이다.

 

1. 최단 경로를 저장할 Distance 배열을 만든다. 출발 노드 A(index 0)는 자기 자신이니 0으로 초기화한다. 

Dist=[0, Infinity, Infinity, Infinity, Infinity]

 

2. A에서 다음으로 갈 수 있는 지점들의 가중치를 변경한다.

 이때, Dist[A]+G[A][B]와 Dist[B]를 비교한다.

Dist에 기록된 A까지의 최단 경로에 추가될 B의 가중치를 합한 값(G[A][B])과 Dist에 기록된 B의 최단 경로를 비교하는 것.

0 + 10 < Infinity이므로 Dist를 갱신한다.

Dist=[0, 10, Infinity, Infinity, Infinity]

 

3. A가 갈 수 있는 또다른 이웃 정점인 C도 똑같이 갱신해준다.

Dist[A]+G[A][C]와 Dist[C]의 비교

Dist=[0, 10, 5, Infinity, Infinity]

 

4. A를 visited 처리해준다.

A는 더이상 사용하지 않는다.

 

5. 미탐색 정점 중 최단 경로를 가진 정점으로 간다.

현재 Dist배열에서 최단 경로를 가진 정점은 C 정점이다.

 

6. C 정점을 선택하고 경로를 확정한다.

이 경로는 추후에도 값이 바뀌지 않는다.

 

7. C에서 다음으로 갈 수 있는 지점들의 가중치를 변경한다.

Dist[C](5)+G[C][B](3)와 Dist[B](10),

Dist[C](5)+G[C][D](9)와 Dist[D](Infinity),

Dist[C](5)+G[C][E](2)와 Dist[E](Infinity)를 각각 비교해 최단 경로를 갱신한다. 

Dist=[0, 8, 5, 14, 7]

 

8. C를 visited 처리해준다. 

 

9. 미탐색 정점 중 최단 경로를 가진 정점으로 간다.

현재 Dist배열에서 A,C를 제외한 최단 경로를 가진 정점은 E 정점이다. 

 

10. 목적 정점인 D가 visited 처리가 되거나, 더 이상 미탐색 정점이 없을 때까지 반복한다.

 

선택된 간선들

//최종 Dist
Dist=[0, 8, 5, 9, 7];

 

구현(JavaScript)

 유/무향 그래프에서 두 노드가 연결되었다는 것을 표시하기 위해 크게 두 가지 방법을 사용한다. 인접행렬 만들기, 인접리스트 만들기.

 인접행렬 adjMatrix[i][j]의 경우는 정점 개수 X 정점 개수로 2차원배열을 만들어 이어져 있으면 가중치 값 혹은 true를 기록한다. A->A는 있어서는 안 되니 보통 adjMatrix[i][j]에서 (i===j) 일 경우는 false(무향 그래프에서 이어져 있지 않다는 뜻), INF 혹은 0(유향그래프, 요구사항에 따라 다름.)을 기록해준다. 구현이 쉽고 배열의 특성인 인덱스를 알고 있을 때 탐색시간이 O(1)라는 장점이 있으나 특정 정점과 연결된 정점들을 확인할 때 O(정점의 개수)만큼의 시간이 매번 걸리게 된다. 따라서, 정점의 개수에 비해 간선의 개수가 적은 희소 그래프라면 인접행렬은 좋은 방법이 아닐 수 있다. 밀집 그래프라면 인접행렬이 좋은 방법이다. 하지만, 이 경우에도 2차원 배열이기 때문에 공간 복잡도를 잘 고려해보자.

👉 자바스크립트의 경우, Number 자료형이 8B라고 생각했을 때.
5000X5000 이차원 배열은 200MB이다.

 

 인접리스트는 직접 class를 구현하는 경우도 있으나, 최소 힙도 구현해야 하는 상황에서 많이 힘들기도 해서 보통 객체로 구현한다. 인접행렬과 반대로 희소 그래프라면 굉장히 효율적인 방법이다. 다만 인접리스트는 탐색시간이 O(정점의 개수)만큼의 시간이 걸린다. 특정 정점과 연결된 정점들을 확인할 때는 좋지만, 특정 정점과 특정 정점이 연결되었는지 여부를 확인하는 연산이 많을 경우에는 좋은 방법이 아닐 수 있다.

 

이 그래프로 인접행렬, 인접리스트를 구현해보자!

	A	B	C	D	E
A	INF	10	5	INF	INF
B	INF	INF	2	1	INF
C	INF	3	INF	9	2
D	INF	INF	INF	INF	4
E	7	INF	INF	6	INF

adjMatrix[A][B] => A->B로 가는 길

adjMatrix[B][A] => B->A로 가는 길

👉 무향 그래프의 경우는 기록해줄때 이 점을 잊지말고 두개 다 기록해주기!

 

//input.txt
//첫번째 줄 : 정점의 개수, 간선의 개수
//두번째 줄 ~ : 간선 정보가 주어진다. (시작 정점, 목적 정점, 가중치)
5 10
1 2 10
1 3 5
2 3 2
2 4 1
3 2 3
3 4 9
3 5 2
4 5 4
5 1 7
5 4 6

 

 이러한 그래프 정보가 주어질 경우 인접 리스트는 다음과 같은 방식으로 구현하면 된다.

 

const fs = require('fs');
const input = fs.readFileSync('input.txt').toString().trim().split('\n');

const [V, E] = input[0].trim().split(' ').map(Number);

const adjList = {};

for (let i = 1; i <= V; i++) {
  adjList[i] = [];
}

for (let j = 1; j <= E; j++) {
  const [from, to, price] = input[j].trim().split(' ').map(Number);
  adjList[from].push([to, price]);
}

배열로 구현해도 상관은 없다.

배열이라면 이런식으로 구현.

 정보를 기록했으니 다음으로 구현해야 할 것은 우선순위 큐이다. 우선순위 큐를 사용하지 않으면 매 탐색마다 최단 경로를 찾기 위해 탐색하는 로직이 들어가게 되고, 해당 다익스트라 알고리즘은 효율적인 탐색이 힘들게 된다. 

 

 우선 Heap을 구현하자. 기본적인 기능만 구현했다.

class Heap {
  constructor() {
    this.items = [];
  }

  swap(idx1, idx2) {
    [this.items[idx1], this.items[idx2]] = [this.items[idx2], this.items[idx1]];
  }

  findParentIdx(idx) {
    return Math.floor((idx - 1) / 2);
  }

  findLeftChildIdx(idx) {
    return idx * 2 + 1;
  }

  findRightChildIdx(idx) {
    return idx * 2 + 2;
  }

  findParent(idx) {
    return this.items[this.findParentIdx(idx)];
  }

  findLeftChild(idx) {
    return this.items[this.findLeftChildIdx(idx)];
  }

  findRightChild(idx) {
    return this.items[this.findRightChildIdx(idx)];
  }

  peek() {
    return this.items[0];
  }

  size() {
    return this.items.length;
  }
}

 그리고 힙을 상속받은 최소 힙을 구현한다.

class MinHeap extends Heap {

  //값을 넣을 때 최소 힙이 유지될 수 있게 알맞은 위치로 넣어주는 bubbleUp
  bubbleUp() {
    let index = this.items.length - 1; //마지막으로 추가된 원소를 찾기

    while (this.findParent(index) && this.findParent(index)[1] > this.items[index][1]) {
      //부모값이 존재 && 자식이 부모보다 최솟값이라면
      this.swap(index, this.findParentIdx(index)); //두 값을 바꿔준다.
      index = this.findParentIdx(index); //계속해서 최소 힙을 만들어줌.
    }
  }

  //최솟값이 빠지면 마지막 노드를 root로 보내고 재배치하는 bubbleDown
  bubbleDown() {
    let index = 0;

    while ((this.findLeftChild(index) && this.findLeftChild(index)[1] < this.items[index][1]) ||
    		(this.findRightChild(index) && this.findRightChild(index)[1] < this.items[index][1])) {
      //자식 중 부모보다 더 작은 값이 존재
      let smallerIndex = this.findLeftChildIdx(index);

      if (
        this.findRightChild(index) &&
        this.findRightChild(index)[1] < this.items[smallerIndex][1]
      ) {
        //오른쪽 자식이 존재하고, 왼쪽 값보다 더 작은 값이라면
        smallerIndex = this.findRightChildIdx(index);
      }

      this.swap(index, smallerIndex);

      index = smallerIndex;
    }
  }

  add(value) {
    this.items.push(value);
    this.bubbleUp();
  }

  poll() {
    if (this.items.length === 1) {
      return this.items.pop();
    }
    const value = this.items[0];
    this.items[0] = this.items.pop();
    this.bubbleDown();

    return value;
  }
}

 이제 다익스트라를 구현해준다. 우선순위 큐를 사용하면 방문 체크 배열은 사용하지 않아도 된다. 최단 거리 노드들을 계속 정렬하므로 기존 최단 거리보다 크면 continue 해주기 때문에 알아서 방문을 안한다. 

const dijkstra = (start, adjList, V) => {
  const minHeap = new MinHeap();
  const dist = Array(V + 1).fill(Infinity); 
  dist[start] = 0;
  minHeap.add([start, 0]);

  while (minHeap.size()) {
    const [vertex, cost] = minHeap.poll();

    if (!adjList[vertex]) continue;
    if (dist[vertex] < cost) continue;

    for (let i = 0; i < adjList[vertex].length; i++) {
      const [nextVertex, nextCost] = adjList[vertex][i];

      if (dist[nextVertex] > cost + nextCost) {
        dist[nextVertex] = cost + nextCost;
        minHeap.add([nextVertex, dist[nextVertex]]);
      }
    }
  }

  return dist;
};

0인덱스는 무시해주면 된다.

const main = (function () {
  const fs = require('fs');
  const input = fs.readFileSync('input.txt').toString().trim().split('\n');

  const [V, E] = input[0].trim().split(' ').map(Number);

  const adjList = {};

  for (let i = 1; i <= V; i++) {
    adjList[i] = [];
  }

  for (let j = 1; j <= E; j++) {
    const [from, to, price] = input[j].trim().split(' ').map(Number);
    adjList[from].push([to, price]);
  }

  const answer = dijkstra(1, adjList, V); // A:1 부터 시작.
  console.log(answer);
})();

 

왜 음수 가중치에서는 사용이 불가능한 것일까?

 다익스트라는 앞서 언급했듯이, 그리디 알고리즘을 컨셉으로 가져간다. 최소거리 + 최소거리 + ...  = 최단거리라는 논리다. 그리디는 근시안적으로 현재의 최선을 선택한다. 그것이 작은 문제부터 그 문제를 포함하고 있는 큰 문제까지 해결할 수 있는 선택이어야 한다. 그리디 알고리즘에서 이 개념이 깨지면 잘못된 선택법으로 접근하고 있다는 것. 

 결과적으로, 음수 가중치가 있으면 이러한 다익스트라 알고리즘에 모순이 생긴다. 

음수가 존재하는 가중 그래프.

  간선에 음의 가중치가 없는 다익스트라는 최솟값이 무한히 갱신되는 경우가 없어 우선순위 큐를 사용해 큐가 빌 때까지만 반복해주면 된다. 하지만, 음의 가중치가 있는 위의 그래프의 경우 다익스트라 알고리즘을 사용하면 음의 사이클인 B->C->D가 무한히 갱신되게 된다.

무한갱신!

 

 따라서 위의 예시는 다익스트라 알고리즘으로 해결할 수 없다. 다익스트라 알고리즘에서 미 탐색 정점 중 가장 가중치가 낮은 정점을 뽑는 이유는 더 이상 그 정점을 재방문해서 재기록할 일이 없기 때문이다. 그런데 음수 가중치가 존재할 경우는 이러한 규칙이 깨지게 된다. 돌아서 오는 것이 이미 탐색 완료한 것보다 짧아질 수 있기 때문이다. 음의 가중치가 있는 경우는 음의 사이클이 존재한다는 것을 판단할 수 있는 벨만-포드 알고리즘을 사용한다.

 

시간 복잡도

$$ O(ElogE) $$

 정점마다 인접 간선 탐색시간 + 우선순위 큐에 정보를 넣고 빼는 작업

• 간선의 개수가 E라면, 전체 간선 탐색시간은 O(E) 
• 우선순위 큐에 E개의 정보가 삽입되고 유지해야하므로 O(ElogE).
• 따라서 O(E+ElogE) => O(ElogE)가 된다. 

 

따라서...

가중치가 없는 최단거리 👉 BFS
모든 가중치가 양수 👉 다익스트라
음수 가중치가 있음 👉 벨만-포드
모든 정점 - 모든 정점 사이의 최단 경로 👉 플로이드-워셜