[Algorithm] 다익스트라 알고리즘 인접리스트로 풀기

인접 리스트로 풀기

다익스트라 문제의 경우 인접 리스트로 푸는 경우가 많다고 한다. 왜냐하면 힙을 이용해 시간 복잡도를 줄일 수 있기 때문이다. 

 

여기서 힙이란 스택과 대비되는 자료구조 중의 하나로 개발자가 직접 할당해서 사용하는 메모리 부분이다. 

 

그렇다면 아래 문제를 한번 인접리스트로 풀이해 보겠다.

 

문제

무방향 그래프의 한 정점(vertex)에서 다른 정점까지의 최단 거리를 리턴해야 합니다.

입력

인자 1: num

• number 타입의 자연수
• 그래프에 존재하는 정점의 개수
• 정점은 1부터 num까지 존재

인자 2: edges

• 배열(간선에 대한 정보)을 요소로 갖는 배열
• edges [i]는 number 타입을 요소로 갖는 배열
• edges [i]. length는 3
• edges [i]의 요소는 차례대로 정점, 정점, 거리
• edges [i][2]은 100 이하의 양의 정수
• [1, 2, 3]은 1번 정점과 2번 정점 사이의 거리가 양방향 모두 3 임을 의미함

입출력 예시

let num = 4;
let edges = [
  [1, 2, 6],
  [1, 3, 2],
  [2, 3, 3],
  [2, 4, 1],
  [3, 4, 5],
];
let start = 1;
let end = 4;
let output = Dijkstra(num, edges, start, end);
console.log(output); // --> 6 (1 - 3 - 2 - 4)

num = 7;
edges = [
  [1, 3, 100],
  [1, 2, 3],
  [1, 4, 4],
  [4, 3, 3],
  [4, 5, 8],
  [5, 6, 10],
  [2, 7, 9],
  [5, 7, 50],
];
start = 1;
end = 7;
output = Dijkstra(num, edges, start, end);
console.log(output); // --> 12 (1 - 2 - 7)

 

자바스크립트 코드 구현

function Dijkstra(num, edges, start, end) {
  let answer = 0;
  const dist = new Array(num + 1).fill(Infinity);
  const adj = Array.from({ length: num + 1}, () => []);
  const priorityQueue = [];

  edges.map((route) => {
    let [start, destination, weight] = route;

    adj[start].push({
      to: destination,
      cost: weight
    });
    adj[destination].push({
      to: start,
      cost: weight
    })
  })

  priorityQueue.push({to: start, cost: 0});
  dist[start] = 0;

  while (priorityQueue.length !== 0) {
    priorityQueue.sort((a, b) => {
      return a.cost - b.cost;
    });

    const { to, cost } = priorityQueue.shift();
    adj[to].forEach((nextNode) => {
      if (dist[nextNode.to] > dist[to] + nextNode.cost) {
        dist[nextNode.to] = dist[to] + nextNode.cost;
        priorityQueue.push(nextNode);
      }
    })
  }

  return dist;
}