// JavaScript 구현 (가장 단순한 O(V^2) 방식 - 코딩테스트용)
const graph = {
  'A': { 'B': 2, 'C': 5 },
  'B': { 'C': 1, 'D': 3 },
  'C': { 'D': 6 },
  'D': {}
};

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  
  // 초기화
  for (let node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;
  
  while (true) {
    let currNode = null;
    let shortestDist = Infinity;
    
    // 방문하지 않은 노드 중 가장 거리가 짧은 노드 탐색 (내장 PQ가 없어서 선형 탐색)
    for (let node in distances) {
      if (!visited.has(node) && distances[node] < shortestDist) {
        shortestDist = distances[node];
        currNode = node;
      }
    }
    
    if (currNode === null) break;
    visited.add(currNode);
    
    // 인접 노드 거리 갱신 (Relaxation)
    for (let neighbor in graph[currNode]) {
      let cost = distances[currNode] + graph[currNode][neighbor];
      if (cost < distances[neighbor]) {
        distances[neighbor] = cost; // 최단 거리 갱신
      }
    }
  }
  
  return distances;
}

console.log("시작점 A 기준 최단 거리:", dijkstra(graph, 'A'));
// 출력: { A: 0, B: 2, C: 3, D: 5 }