[Algorithm] 다익스트라 알고리즘

 

다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 

다른 최단거리 알고리즘으로는 벨만 포드와 플로이드 와샬 알고리즘이 있는데 이는 다른 포스팅에서 다루기로 하겠다. 

 

다익스트라 알고리즘의 핵심은

1. 노드간의 거리를 나타내는 매트릭스와 방문 기록 배열을 만든다. 

2. 매트릭스에 노드간 거리를 넣는다.

3. 출발 노드에서 가장 작은 비용으로 갈 수 있는 노드를 구한다.

4. 최소거리 노드로 이동하며 방문 기록을 True로 변경한다. 

5. 최소거리 노드까지 이동하는 거리를 더한 참조 배열을 만들고 출발 노드와의 거리와 비교해 더 작은 값을 대입한다.

6. 과정을 반복한다. 

 

아래 예제를 풀어보자.

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

음... 일단은 아래와 같이 풀긴했는데 문제를 통과하진 못했다. 

 

const INF = Infinity;
const matrix = [
  [0,2,3,INF,1],
  [2,0,4,5,INF],
  [3,4,0,6,INF],
  [INF,5,6,0,INF],
  [1,INF,INF,INF,0]
]
const isVisited = Array(matrix.length).fill(false);

const getMin = (arr) => {
  let min = INF;
  let idx = 0;
  arr.forEach((item, index) => {
    if (!isVisited[index] && item < min) {
      min = item;
      idx = index;
    }
  })
  return idx; 
};

const dist = (start) => {
  isVisited[start -1] = true;
  let distance = matrix[start -1].slice();
  let counter = 0;
  let end = distance.length;
  let startN = distance;
  let min = 0;

  while (counter < end) {
    const index = getMin(startN);
    if (index === 0) {
      min = 0;
    } else {
      min += startN[index];
    }
    isVisited[index] = true;
    const nextN = matrix[index];
    startN.forEach((el, idx) => {
      if (!isVisited[idx] && distance[idx] > nextN[idx] + min) {
        distance[idx] = nextN[idx] + min;
      }
    })
    startN = matrix[index];
    counter ++; 
  }
  console.log(distance)
}

 

한 가지 의아한 부분이 있다. 

 

문제를 보면 그래프를 아래와 같이 그릴 수 있는데, 

 

const matrix = [
  [0,2,3,INF,1],
  [2,0,4,5,INF],
  [3,4,0,6,INF],
  [INF,5,6,0,INF],
  [1,INF,INF,INF,0]
]

 

1번 노드와 5번 노드 사이에는 분명 간선이 있는데 정답에는 INF로 표시가 되어 있다. 

 

아마 문제를 잘못 이해한 듯 한데, 다시 읽어봐도 찾을 수가 없다 ㅠ