Dijkstra's Shortest Path Algorithm

dijkstra.js

function dijkstra(graph, startNode) {
  const distances = {};
  const visited = {};
  const queue = [];

  distances[startNode] = 0;
  queue.push({ node: startNode, distance: 0 });

  while (queue.length > 0) {
    queue.sort((a, b) => a.distance - b.distance);
    const { node, distance } = queue.shift();

    if (visited[node]) {
      continue;
    }

    visited[node] = true;

    for (const neighbor in graph[node]) {
      const totalDistance = distance + graph[node][neighbor];

      if (!distances[neighbor] || totalDistance < distances[neighbor]) {
        distances[neighbor] = totalDistance;
        queue.push({ node: neighbor, distance: totalDistance });
      }
    }
  }

  return distances;
}

const graph = {
  A: { B: 5, C: 2 },
  B: { A: 5, C: 1, D: 3 },
  C: { A: 2, B: 1, D: 2 },
  D: { B: 3, C: 2 },
};

console.log(dijkstra(graph, 'A')); // Output: { A: 0, B: 4, C: 2, D: 4 }