게시글

5만명이 선택한 평균 별점 4.9의 제로초 프로그래밍 강좌! 로드맵만 따라오면 됩니다! 클릭
강좌20 - Algorithm - 8년 전 등록 / 4년 전 수정

최단 경로 알고리즘

다익스트라(dijkstra) 알고리즘

안녕하세요. 이번 시간에는 단일 출발지에서 최단 경로를 찾는 다익스트라 알고리즘에 대해 알아보겠습니다.

단일 출발지에서 최단 경로가 무슨 소리냐면, 한 버텍스에서 다른 모든 버텍스까지의 최단 경로를 찾는다는 소리입니다.

undefined

다익스트라 알고리즘을 사용하여 A로부터 시작하면, B, C, D, E, F 모든 버텍스에 대한 최단 경로를 구할 수 있습니다. 생각만 해도 신나죠? 저만 신나나요? ㅠㅠ

일단 모든 버텍스의 최단 거리값을 Infinity(무한)으로 설정합니다. 그리고 시작점(A) 최단 거리값을 0으로 설정합니다. 이제 A와 연결된 B, C의 거리값을 조정하는데, 시작점 거리값에 아크 값을 더한 것보다 도착점 거리값이 크면 도착점 거리값을 더한 값으로 낮춥니다.

무슨 말인지 글로 보면 헷갈리죠? 시작점 거리값(A, 0)에 아크 값(6)을 더한 것(0+6 = 6)보다 도착점 거리값(B, 무한)이 크면 도착점 거리값을 더한 값(6)으로 바꿉니다. 이제 B는 6이 되는 거죠. C도 0 + 3보다 무한(C값)이 더 크기 때문에 C는 3이 됩니다.

이제 A(0), B(6), C(3), 나머지는 무한인 상황에서 B를 기준으로 반복합니다. A, C, D가 연결되어 있습니다. A에서는 B + 아크(6 + 6)보다 A(0)가 작기 때문에 넘어갑니다. C에서는 B + 아크(6 + 2)보다 C(3)가 작기 때문에 역시 넘어갑니다. D에서는 B + 아크(6 + 5)보다 D(무한)이 크기 때문에 D값을 11로 낮춥니다.

A(0), B(6), C(3), D(11), 나머지는 무한인 상황에서 C를 기준으로 반복합니다. A, B, D, E가 연결되어 있습니다. A에서는 C + 아크(3 + 3)보다 A(0)이 작기 때문에 넘어갑니다. B에서는 C + 아크(3 + 2)보다 B(6)가 크기 때문에 B값을 5로 낮춥니다. D에서는 C + 아크(3 + 3)보다 D(11)이 크기 때문에 D값을 6으로 낮춥니다. E에서는 C + 아크(3 + 4)보다 E(무한)값이 크기 때문에 E의 값을 7로 낮춥니다.

이제 A(0), B(5), C(3), D(6), E(7), F(무한)입니다. 이렇게 남은 D, E, F에서도 반복하면 모든 버텍스의 최단 거리가 나옵니다. 거리가 짧을 때만 값을 낮추고, 크면 넘어가기 때문에 최단 거리를 찾을 수 있는 겁니다.

다익스트라 알고리즘은 기본적으로 동적 프로그래밍도 가능하지만 그리디 알고리즘으로 최적화할 수 있다는 점에서 프림 알고리즘과 상당히 비슷합니다. 사실상 프림 알고리즘을 살짝 변형한 것과 다름없습니다.

코드로 볼까요?지난 시간 그래프 코드 를 재사용합니다.

Graph.prototype.shortest = function(startKey) {
  var from = this.first;
  while (from) {
    if (from.key === startKey) {
      break;
    }
    from = from.next;
  }
  console.log('시작점은 %s입니다', from.key);
  var temp = this.first;
  var current;
  var arc;
  while (temp) { // 모든 버텍스 최단거리를 Infinity로 초기화
    temp.distance = Infinity;
    temp = temp.next;
  }
  temp = this.first;
  temp.distance = 0;
  while (temp) { // 반복문을 돌며 최단 거리를 찾음
    current = temp;
    temp = temp.next;
    arc = current.arc;
    while (arc) {
      if (arc.destination.distance > current.distance + arc.data) {
        arc.destination.distance = current.distance + arc.data;
      }
      arc = arc.nextArc;
    }
  }
  temp = this.first;
  while (temp) {
    console.log('%s까지의 최단 거리는 %d입니다', temp.key, temp.distance);
    temp = temp.next;
  }
};
var graph = new Graph();
graph.insertVertex('A');
graph.insertVertex('B');
graph.insertVertex('C');
graph.insertVertex('D');
graph.insertVertex('E');
graph.insertVertex('F');
insertTwoWayArc(graph, 6, 'A', 'B');
insertTwoWayArc(graph, 3, 'A', 'C');
insertTwoWayArc(graph, 2, 'B', 'C');
insertTwoWayArc(graph, 5, 'B', 'D');
insertTwoWayArc(graph, 3, 'C', 'D');
insertTwoWayArc(graph, 4, 'C', 'E');
insertTwoWayArc(graph, 2, 'D', 'E');
insertTwoWayArc(graph, 3, 'D', 'F');
insertTwoWayArc(graph, 5, 'E', 'F');
graph.shortest('A');
// A까지의 최단 거리는 0입니다.
// B까지의 최단 거리는 5입니다.
// C까지의 최단 거리는 3입니다.
// D까지의 최단 거리는 6입니다.
// E까지의 최단 거리는 7입니다.
// F까지의 최단 거리는 9입니다.
undefined

한 가지 제약점은 모든 아크의 값이 양수여야 한다는 겁니다. 음수일 경우에는 다른 알고리즘(벨만-포드)을 써야 합니다. 다익스트라 알고리즘의 시간 복잡도는 자료구조를 어떤 것을 쓰느냐에 따라 다르지만, 배열에서는 O(V^2), 이진 힙에서는 O(ElgV), 피보나치 힙에서는 O(E+VlgV)가 됩니다. 프림 알고리즘과 똑같습니다.

위의 상황에서는 시작점 하나에 대한 최단 경로만 알려줍니다. 만약 모든 점에서의 최단 경로를 찾고 싶으면 어떻게 해야 할까요? 간단합니다. 모든 점에서 다익스트라 알고리즘을 한 번씩 실행하면 됩니다. 점의 개수가 V이니까 복잡도는 배열에서 O(V^3), 이진 힙에서 O(VElgV), 피보나치 힙에서는 O(VE + V^2lgV)가 됩니다.

다음 시간에는 네트워크 플로우에 대해 알아보겠습니다!

조회수:
0
목록
투표로 게시글에 관해 피드백을 해주시면 게시글 수정 시 반영됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright 2016- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.
5만명이 선택한 평균 별점 4.9의 제로초 프로그래밍 강좌! 로드맵만 따라오면 됩니다! 클릭

댓글

3개의 댓글이 있습니다.
5년 전
안녕하세요, 공부하다가 예외가 있는것 같아서 따로 찾아보니까 계산후 다음 버텍스 고를때 방문하지 않으면서 최소값을 가지는 버텍스를 선택해야 된다고 되있네요. 글에는 설명없이 ABC 순으로 고르는 것처럼 설명되있어서 그 내용이 안나와있는것 같아요
6년 전
저번에 git에 관해 쓰신 글도 너무 잘 봤는데, 다익스트라도 잘 읽고 갑니다. 갖고 계신 지식을 저도 하루 빨리 따라 잡고 싶습니다! 좋은 글 감사합니다.
6년 전
감사합니다~
7년 전
C를 기준으로 반복하는 부분에서 C + 아크(3 + 3)보다 D(11)이 크기 때문에 D값을 6으로 낮춰야하는 것 아닌가요?
7년 전
오타 잡아주셔서 감사합니다!