djkstra's algorithm in javascript

index.tsx
function dijkstra(graph, startNode, endNode) {
  // Initialize distances with infinity except for the startNode which is 0
  let distances = {};
  for (let node in graph) {
    distances[node] = Infinity
  }
  distances[startNode] = 0;
  
  // Set up a queue for unvisited nodes
  let unvisitedNodes = new Set(Object.keys(graph));
  
  // Create an object to keep track of the shortest path
  let shortestPath = {};
  while (unvisitedNodes.size !== 0) {
    let closestNode = null;
    // Find the closest unvisitedNode to the startNode
    for (let node of unvisitedNodes) {
      if (closestNode === null || distances[node] < distances[closestNode]) {
        closestNode = node;
      }
    }
    
    // Find the distance from the closestNode to its neighbors
    for (let neighbor in graph[closestNode]) {
      let distance = graph[closestNode][neighbor];
      let newPath = distances[closestNode] + distance;
      if (newPath < distances[neighbor]) {
        distances[neighbor] = newPath;
        shortestPath[neighbor] = closestNode;
      }
    }
    
    // Remove the closestNode from the unvisitedNodes set since we have visited it
    unvisitedNodes.delete(closestNode);
  }
  
  // If no path exists, return null
  if (distances[endNode] === Infinity) {
    return null;
  }
  
  // Trace the path back from the endNode to the startNode
  let path = [endNode];
  let lastNode = endNode;
  while (lastNode !== startNode) {
    path.unshift(shortestPath[lastNode]);
    lastNode = shortestPath[lastNode];
  }
  
  return { distance: distances[endNode], path: path };
}
1584 chars
52 lines

index.tsx
let graph = {
  "A": { "B": 3, "C": 4 },
  "B": { "C": 1 },
  "C": {}
};
73 chars
6 lines

index.tsx
let shortestPath = dijkstra(graph, "A", "C");
console.log(shortestPath); // { distance: 4, path: ["A", "B", "C"] }
115 chars
3 lines