다익스트라 알고리즘

Jun·2021년 7월 2일
0

다익스트라 알고리즘은 그래프 형태로 여러 노드와 간선의 가중치가 주어졌을때, 하나의 정해진 노드에서 부터 모든 노드로 갈수 있는 최단거리를 구할때 사용하는 알고리즘 이다.

1.방문한 노드인지 아닌지를 구분하기위하여 방문 배열을 생성하고 최단거리를 업데이트 시켜줄 배열을 생성한다.

2.시작노드에서 연결되어 있는 간선중 가중치가 가장 적은 노드를 선택한다.

3.선택 되어진 노드에서 연결되어있는 노드들을 전부 탐색한다

4.선택되어진 노드의 가중치와 탐색하는 노드들의 가중치의 합과 탐색노드의 최단거리 배열의 값을 비교한다. 만약 선택되어진 노드의 가중차와 탐색노드의 가중치의 합이 해당 노드의 최단거리 배열보다 작으면 작은값으로 새로 갱신시켜준다.

모든 노드들을 방문할때까지 1~4를 반복한다. 전부 방문이 되어지면 최단거리의 배열은 최소의 값들로 갱신이 되어져있다.

밑의 코드는 다익스트라의 기본인 프로그래머스 '배달' 문제 이다.

function solution(N, road, K) {
  let visited = new Array(N).fill(false);
  let answer = new Array(N).fill(Infinity);

  let metrix = Array.from(new Array(N), () => new Array(N).fill(Infinity));

    
    
    
  road.forEach((el, idx) => {
    const [from, to, value] = el;  
    metrix[from-1][to-1] =  Math.min(metrix[from-1][to-1],value) 
    metrix[to-1][from-1] =  Math.min(metrix[to-1][from-1],value)
  });
    
  for(let i=0; i<N; i++){
      answer[i] = metrix[0][i];
  }
  
  visited[0] = true;
  answer[0] = 0;


  const smallest = () => {
    let min = Infinity;
    let minIdx = 0;

    answer.forEach((el, idx) => {
      if (visited[idx] === false && el <= min) {
        min = el;
        minIdx = idx;
      }
    });

    return minIdx;
  };

  const dijkstra = () => {
    answer.forEach((el, idx) => {
      let findMin = smallest();
      visited[findMin] = true;

      for (let i = 0; i < N; i++) {
        if (visited[i] === false) {
          if (metrix[findMin][i] + answer[findMin] < answer[i]) {
            answer[i] = metrix[findMin][i] + answer[findMin];
          }
        }
      }
    });
  };

  dijkstra();
  console.log(metrix,answer)
  let final = answer.filter(el => el <=K);

  return final.length;

}


solution(
  6,
  [
    [1, 2, 1],
    [2, 3, 3],
    [5, 2, 2],
    [1, 4, 2],
    [5, 3, 1],
    [5, 4, 2],
  ],
  4
);

0개의 댓글