다익스트라

- 그래프의 정점이 다른 모든 정점으로 가는 최단 거리를 구한다

function solution(n, edges, end) {
  let answer = 0;
  let minH = new minHeap();
  let graph = Array.from(Array(n+1), () => Array());
  let dist = Array.from({length:n+1}, () => 1000); // 각 노드의 최소값을 가지고 있는 배열 
  for(let [a, b, c] of edges){ // r가중치 그래프
      graph[a].push([b, c]);
  }
  dist[1] = 0;
  minH.insert([1, 0]);
  while(minH.size() > 0){
      let tmp = minH.get();
      let now = tmp[0]; // 현재정점
      let nowCost = tmp[1]; // 그 정점의 비용 
      if(nowCost > dist[now]) continue; // 더 큰 비용이 들어오면 그냥 나가라 
      for(let [next, cost] of graph[now]){  //next, cost 연결된 정점 
          if(nowCost + cost < dist[next]){
              dist[next] = nowCost + cost;
              minH.insert([next, dist[next]]);
          }
      }
  }
  if(dist[end] === 1000) answer = -1;
  else answer = dist[end];
  return answer;
}

관련문제 -프로그래머스 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

function solution(N, road, K) {
  let answer = 0;
  
  let minH = new minHeap();  // minheap을 쓰면 최소값을 가져오는 시간이 줄어든다 (log n)
  let graph=Array.from(Array(N+1), ()=>Array());

  let dist = Array(N+1).fill(1e9); // 다익스트라를 위한 디스턴스 배열 선언 ,인접한 노드별 가중치 정보를 담은 배열 
  
  for(let [a, b, c] of road){ // 무방향 그래프 [마을 a, 마을 b , 두곳을 진가는데 걸리는 시간 ]
    graph[a].push([b,c]);
    graph[b].push([a,c]);
  }
  

  dist[1] = 0; // 다익스트라 그래프로 구조화 하려면 시작점이 있어야 하므로 0으로 선언  

  minH.insert([1,0]); 
  
  while(minH.size() > 0){
      let tmp = minH.get() // 최소 값을 꺼내준다 
      let now = tmp[0]; // 현재 노드
      let nowTime = tmp[1]; // 가는데 걸리는 시간 

      if(nowTime > dist[now]) continue; // dist 배열안에 있는 시간보다 크면 아래 for문을 검사하지 않고 통과 처리 (최소값이기 때문)
    
      for(let [next,time] of graph[now]){   // next 이동할 마을, time 걸리는 시간 
        if(nowTime + time < dist[next]){ // 연결된 노드의  시간이 더 작다면 
              dist[next] = nowTime + time;  // dist 에 값을 저장 
              minH.insert([next,dist[next]]); // min heap에도 insert
              
        }
      }
  }

  for(let x of dist){ // 각 구간들의 걸리는 시간 중에 최소 4시간 이하인 애들만 찾아서 count 해준다 
      if(x <= K){
          answer++;
      }
  }

  return answer;
}