Dijkstra's Algorithm

Sunday, February 19th 2023
function dijkstra(graph, startNode, endNode) { // Initialize distances to all nodes as infinity and the start node as 0 const distances = {}; distances[startNode] = 0; for (let node in graph) { if (node !== startNode) { distances[node] = Infinity; } } // Initialize an empty set and add the start node to it const visited = new Set(); // Loop until we've visited all nodes while (!visited.has(endNode)) { let currentNode = null; // Find the node with the shortest distance from the start node for (let node in graph) { if (!visited.has(node)) { if (currentNode === null || distances[node] < distances[currentNode]) { currentNode = node; } } } // Get the neighbors of the current node and update their distances const neighbors = graph[currentNode]; for (let neighbor in neighbors) { const distance = neighbors[neighbor]; const totalDistance = distances[currentNode] + distance; if (totalDistance < distances[neighbor]) { distances[neighbor] = totalDistance; } } // Add the current node to the visited set visited.add(currentNode); } // Return the shortest distance from the start node to the end node return distances[endNode]; }
const graph = { A: { B: 5, C: 2 }, B: { D: 4 }, C: { B: 1, D: 3 }, D: { A: 1 }, };
A ----5---- B ----4---- D \ | 2 1 \ | C ----3--
const shortestDistance = dijkstra(graph, 'A', 'D'); console.log(shortestDistance); // 4