1// Dijkstra's Algorithm: Finds shortest paths from start node to all other nodes
2// Input: graph (adjacency list with weights), start node, end node
3// Output: Object containing shortest distances and path
4function dijkstra(graph, start, end) {
5    // Keep track of distances from start to each node
6    const distances = {};
7    // Keep track of nodes we've already processed
8    const visited = new Set();
9    // Keep track of the previous node in the shortest path
10    const previous = {};
11    
12    // Initialize all distances to infinity except start node
13    for (let node in graph) {
14        distances[node] = Infinity;
15        previous[node] = null;
16    }
17    distances[start] = 0;
18    
19    while (true) {
20        let minDistance = Infinity;
21        let minNode = null;
22        
23        // Find the unvisited node with the smallest distance
24        for (let node in distances) {
25            if (!visited.has(node) && distances[node] < minDistance) {
26                minDistance = distances[node];
27                minNode = node;
28            }
29        }
30        
31        // If no more nodes to process or we reached the end, we're done
32        if (minNode === null || minNode === end) break;
33        visited.add(minNode);
34        
35        // Update distances to all neighbors of current node
36        for (let neighbor in graph[minNode]) {
37            let distance = distances[minNode] + graph[minNode][neighbor];
38            if (distance < distances[neighbor]) {
39                distances[neighbor] = distance;
40                previous[neighbor] = minNode;
41            }
42        }
43    }
44    
45    // Reconstruct the path
46    const path = [];
47    let current = end;
48    while (current !== null) {
49        path.unshift(current);
50        current = previous[current];
51    }
52    
53    return {
54        distance: distances[end],
55        path: path
56    };
57}