다익스트라 알고리즘

에르허츠 데이크스트라가 여친이랑 데이트하다가 10분만에 고안한 최단경로 알고리즘으로 알려져 있다.
O(V^2)의 시간 복잡도를 가지지만, 우선순위 큐를 적용할 시에 O((V+E) log V)의 시간 복잡도로 소폭 개선할 수 있다. (우선순위 큐로 최단거리의 노드를 찾는 데에 V log V, 최단 거리를 비교하고 갱신하는 데에 E Log V)
참고- 안경잡이 개발자

다익스트라 알고리즘의 동작 원리

1. 최단거리 테이블을 만들고, 충분히 큰 값(가령 자바스크립트의 Infinity나 Number.MAX_SAFE_INTEGER)로 초기화 한다.
2. 시작 노드를 우선순위 큐에 넣고, 최단거리 테이블에서 시작 노드의 값을 0으로 한다.
3. 우선순위 큐에서 최소힙으로 최단거리가 가장 작은 노드를 꺼낸다.
4. 해당 노드와 인접한 노드들의 최단거리 테이블을 조회하여 해당 노드까지의 최단거리 + 인접한 노드로 가는 거리가 인접한 노드의 최단거리보다 작다면 최단 거리를 갱신하고, 인접한 노드의 인접한 노드를 우선순위 큐에 넣는다.
5. 우선순위 큐가 빌 때까지 3, 4를 반복한다.

다익스트라 알고리즘의 구현

문제: 시작점에서 모든 정점으로 가는 최단 경로를 구하시오.

다음과 같은 그래프가 있다고 가정해보겠습니다.


이 그래프에서 1번 정점이 시작점이라고 가정합니다. 다익스트라 알고리즘을 적용하여 모든 정점으로 가는 최단 경로를 찾아보겠습니다.

시작점에서 출발합니다. 초기에는 시작점에서 직접 연결된 정점의 거리와 나머지 정점의 거리는 무한대로 설정합니다.

시작점에서 직접 연결된 정점의 거리를 갱신합니다. 이제 2번 정점까지의 거리는 7, 3번 정점까지의 거리는 9, 4번 정점까지의 거리는 20입니다.

다음으로 방문할 정점을 선택합니다. 이번에는 2번 정점을 선택합니다. 2번 정점에서 연결된 정점들의 거리를 갱신합니다. 이제 3번 정점까지의 거리는 10, 4번 정점까지의 거리는 15입니다.

다음으로 방문할 정점을 선택합니다. 이번에는 3번 정점을 선택합니다. 3번 정점에서 연결된 정점들의 거리를 갱신합니다. 이제 4번 정점까지의 거리는 11입니다.

마지막으로 방문할 정점을 선택합니다. 이번에는 4번 정점을 선택합니다. 4번 정점에서 연결된 정점들의 거리를 갱신합니다. 더 이상 갈 수 있는 정점이 없으므로 알고리즘이 종료됩니다.

이제 최단 거리를 출력하면 다음과 같습니다.

1번 정점에서 1번 정점까지의 거리는 0입니다.
1번 정점에서 2번 정점까지의 거리는 7입니다.
1번 정점에서 3번 정점까지의 거리는 9입니다.
1번 정점에서 4번 정점까지의 거리는 11입니다.

// 그래프 정의
const graph = {
  1: { 2: 7, 3: 9, 6: 14 },
  2: { 1: 7, 3: 10, 4: 15 },
  3: { 1: 9, 2: 10, 4: 11, 6: 2 },
  4: { 2: 15, 3: 11, 5: 6 },
  5: { 4: 6, 6: 9 },
  6: { 1: 14, 3: 2, 5: 9 },
};

// 시작점
const startNode = 1;

// 초기화
const distances = {};
const visited = {};
for (const node in graph) {
  distances[node] = Infinity;
  visited[node] = false;
}
distances[startNode] = 0;

// 다익스트라 알고리즘
for (let i = 0; i < Object.keys(graph).length - 1; i++) {
  let currentNode = null;
  let shortestDistance = Infinity;
  for (const node in graph) {
    if (!visited[node] && distances[node] < shortestDistance) {
      currentNode = node;
      shortestDistance = distances[node];
    }
  }
  visited[currentNode] = true;
  for (const neighbor in graph[currentNode]) {
    const tentativeDistance =
      distances[currentNode] + graph[currentNode][neighbor];
    if (tentativeDistance < distances[neighbor]) {
      distances[neighbor] = tentativeDistance;
    }
  }
}

console.log(JSON.stringify(distances));

{"1":0,
 "2":7,
 "3":9,
 "4":20,
 "5":20,
 "6":11}

위 코드의 시간 복잡도는 O(V^2)이다.

힙 구현하기

우선순위 큐를 위해서는 최소힙을 구현해야 한다.
트리 자료구조에서 구현한 대로 최소힙의 heappush, heappop을 구현한다.

const minHeap = [];

const heappush = (element) => {
  minHeap.push(element);
  let crrIndex = minHeap.length - 1;
  while (crrIndex) {
    parentIndex = Math.floor((crrIndex - 1) / 2);
    if (minHeap[crrIndex] <= minHeap[parentIndex]) {
      [minHeap[crrIndex], minHeap[parentIndex]] = [
        minHeap[parentIndex],
        minHeap[crrIndex],
      ];
      crrIndex = parentIndex;
    } else {
      break;
    }
  }
};

const heappop = () => {
  let lastElement = minHeap.pop();
  if (!minHeap[0]) return lastElement;
  [minHeap[0], lastElement] = [lastElement, minHeap[0]];

  let parentIndex = 0;

  while (parentIndex <= Math.floor(minHeap.length / 2)) {
    let smallerChindIndex = parentIndex * 2 + 1;
    const rightChildIndex = parentIndex * 2 + 2;

    if (minHeap[smallerChindIndex] > minHeap[rightChildIndex])
      smallerChindIndex = rightChildIndex;

    if (minHeap[parentIndex] > minHeap[smallerChindIndex]) {
      [minHeap[parentIndex], minHeap[smallerChindIndex]] = [
        minHeap[smallerChindIndex],
        minHeap[parentIndex],
      ];

      parentIndex = smallerChindIndex;
    } else {
      break;
    }
  }

  return lastElement;
};

최소 힙 적용하기

위의 코드를 다익스트라에 적용하면서 몇가지 수정사항이 있었다.

1. 최소 힙에 [노드 번호, 가중치]로 heappush를 하도록 코드를 수정한다.
2. 마찬가지로 heappush, heappop에서 노드[1]로 크기를 비교하도록 수정한 후, 노드가 undefined일 때에 대한 예외처리를 해준다.
3. 마지막으로 minHeap에 요소가 존재할 때에 while문을 반복하도록 수정한다.

// 그래프 정의
const graph = {
  1: { 2: 7, 3: 9, 6: 14 },
  2: { 1: 7, 3: 10, 4: 15 },
  3: { 1: 9, 2: 10, 4: 11, 6: 2 },
  4: { 2: 15, 3: 11, 5: 6 },
  5: { 4: 6, 6: 9 },
  6: { 1: 14, 3: 2, 5: 9 },
};

// 시작점
const startNode = 1;

// 초기화
const distances = {};
const visited = {};
for (const node in graph) {
  distances[node] = Infinity;
  visited[node] = false;
}
distances[startNode] = 0;

const minHeap = [];
heappush([startNode, 0]);

// 다익스트라 알고리즘
while (minHeap.length) {
  const [currentNode, currentDistance] = heappop();
  if (visited[currentNode]) continue;
  visited[currentNode] = true;

  for (const neighbor in graph[currentNode]) {
    const tentativeDistance =
      distances[currentNode] + graph[currentNode][neighbor];
    if (tentativeDistance < distances[neighbor]) {
      distances[neighbor] = tentativeDistance;
      heappush([neighbor, tentativeDistance]);
    }
  }
}

// 최소 힙 알고리즘
function heappush(element) {
  minHeap.push(element);
  let crrIndex = minHeap.length - 1;
  while (crrIndex) {
    parentIndex = Math.floor((crrIndex - 1) / 2);
    if (minHeap[crrIndex][1] <= minHeap[parentIndex][1]) {
      [minHeap[crrIndex], minHeap[parentIndex]] = [
        minHeap[parentIndex],
        minHeap[crrIndex],
      ];
      crrIndex = parentIndex;
    } else {
      break;
    }
  }
}

function heappop() {
  let lastElement = minHeap.pop();
  if (!minHeap[0]) return lastElement;
  [minHeap[0], lastElement] = [lastElement, minHeap[0]];

  let parentIndex = 0;

  while (parentIndex <= Math.floor(minHeap.length / 2)) {
    let smallerChindIndex = parentIndex * 2 + 1;
    const rightChildIndex = parentIndex * 2 + 2;

    if (
      minHeap[rightChildIndex] &&
      minHeap[smallerChindIndex][1] > minHeap[rightChildIndex][1]
    )
      smallerChindIndex = rightChildIndex;

    if (
      minHeap[smallerChindIndex] &&
      minHeap[parentIndex][1] > minHeap[smallerChindIndex][1]
    ) {
      [minHeap[parentIndex], minHeap[smallerChindIndex]] = [
        minHeap[smallerChindIndex],
        minHeap[parentIndex],
      ];

      parentIndex = smallerChindIndex;
    } else {
      break;
    }
  }

  return lastElement;
}

console.log(JSON.stringify(distances));

{"1":0,
 "2":7,
 "3":9,
 "4":20,
 "5":20,
 "6":11}

잘 작동했다.

프림 알고리즘

프림 알고리즘은 최소 신장 트리를 찾는 과정에 다익스트라 같은 걸 끼얹는 방식이다. 크루스칼 알고리즘은 모든 간선을 탐색하면서 시간복잡도가 O(E log E)가 된다. 반면 프림 알고리즘은 모든 노드를 탐색하면서 진행하게 되고 시간 복잡도는 다익스트라 알고리즘과 동일한 O((V+E) log V)가 된다. 노드에 비해 간선의 갯수가 그리 많이 많은 일반적인 경우에는 크루스칼 알고리즘의 실행 속도가 더 적지만, 간선의 갯수가 아주 많은(dense한) 경우에는 프림 알고리즘을 고려해볼 수 있다.

참고 - weeklyps

프림 알고리즘의 동작 원리

다익스트라와 프림의 차이는 '경로'와 '트리'의 차이임을 염두에 두자.
'경로'는 어떠한 시작지점에서 어떠한 도착지점을 잇는 것이다.
'트리'는 어떠한 시작지점(루트 노드)에서 모든 노드를 잇는 것이다.

따라서
다익스트라에는 경로에 포함되지 않는 노드를 배제하며 진행하지만,
프림은 트리에 포함되지 않은 노드들에 대해 하나씩 확장해가고 최단 거리를 업데이트 하며 진행해간다.

프림 알고리즘의 구현

다익스트라의 기본적인 로직에서 최소 신장 트리를 저장하고 출력하도록 수정했다.

const graph = {
  1: { 2: 7, 3: 9, 6: 14 },
  2: { 1: 7, 3: 10, 4: 15 },
  3: { 1: 9, 2: 10, 4: 11, 6: 2 },
  4: { 2: 15, 3: 11, 5: 6 },
  5: { 4: 6, 6: 9 },
  6: { 1: 14, 3: 2, 5: 9 },
};

// 시작점
const startNode = 1;

// 초기화
const distances = {};
const visited = {};
const parent = {};
for (const node in graph) {
  distances[node] = Infinity;
  visited[node] = false;
  parent[node] = null;
}
distances[startNode] = 0;

const minHeap = [];
heappush([startNode, 0]);

const mst = {}; // 최소 신장 트리를 저장할 객체

// 프림 알고리즘
while (minHeap.length) {
  const [currentNode, currentDistance] = heappop();
  if (visited[currentNode]) continue;
  visited[currentNode] = true;

  // 현재 노드와 연결된 모든 간선을 검사하며 최소값을 찾음
  for (const neighbor in graph[currentNode]) {
    const distance = graph[currentNode][neighbor];
    if (distance < distances[neighbor]) {
      distances[neighbor] = distance;
      parent[neighbor] = currentNode;
      heappush([neighbor, distance]);
    }
  }

  // 최소값을 가진 간선을 mst 객체에 추가
  if (parent[currentNode]) {
    const key =
      parent[currentNode] < currentNode
        ? `${parent[currentNode]}-${currentNode}`
        : `${currentNode}-${parent[currentNode]}`;
    const value = graph[parent[currentNode]][currentNode];
    mst[key] = value;
  }
}

console.log(mst);

function heappush(element) {
  minHeap.push(element);
  let crrIndex = minHeap.length - 1;
  while (crrIndex) {
    parentIndex = Math.floor((crrIndex - 1) / 2);
    if (minHeap[crrIndex][1] <= minHeap[parentIndex][1]) {
      [minHeap[crrIndex], minHeap[parentIndex]] = [
        minHeap[parentIndex],
        minHeap[crrIndex],
      ];
      crrIndex = parentIndex;
    } else {
      break;
    }
  }
}

function heappop() {
  let lastElement = minHeap.pop();
  if (!minHeap[0]) return lastElement;
  [minHeap[0], lastElement] = [lastElement, minHeap[0]];

  let parentIndex = 0;

  while (parentIndex <= Math.floor(minHeap.length / 2)) {
    let smallerChindIndex = parentIndex * 2 + 1;
    const rightChildIndex = parentIndex * 2 + 2;

    if (
      minHeap[rightChildIndex] &&
      minHeap[smallerChindIndex][1] > minHeap[rightChildIndex][1]
    )
      smallerChindIndex = rightChildIndex;

    if (
      minHeap[smallerChindIndex] &&
      minHeap[parentIndex][1] > minHeap[smallerChindIndex][1]
    ) {
      [minHeap[parentIndex], minHeap[smallerChindIndex]] = [
        minHeap[smallerChindIndex],
        minHeap[parentIndex],
      ];

      parentIndex = smallerChindIndex;
    } else {
      break;
    }
  }

  return lastElement;
}