Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-pro-preview-05-06· GoogleHugging Face LMArena Human Preference 140K

Dijkstra in js

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with chatgpt-4o-latest-20250326’s answer.
  1. User

    Dijkstra in js

  2. Gemini Assistant

    Okay, here's an implementation of Dijkstra's algorithm in JavaScript.

    This implementation will:

    1. Use an adjacency list to represent the graph.
    2. Find the shortest paths from a single source node to all other nodes.
    3. Provide a helper function to reconstruct the shortest path to a specific target node.

    We'll use a simple approach for the "priority queue" (finding the unvisited node with the smallest distance) for clarity. For very large graphs, a min-heap based priority queue would be more efficient.

    /**
     * Represents a graph using an adjacency list.
     * Example:
     * const graph = {
     *   'A': { 'B': 4, 'C': 2 },
     *   'B': { 'A': 4, 'C': 5, 'D': 10 },
     *   'C': { 'A': 2, 'B': 5, 'D': 3 },
     *   'D': { 'B': 10, 'C': 3 }
     * };
     * Here, graph['A']['B'] = 4 means the weight of the edge from A to B is 4.
     */
    
    function dijkstra(graph, startNode) {
        // 1. Initialization
        const distances = {};      // Stores the shortest distance from startNode to each node
        const previousNodes = {};  // Stores the previous node in the shortest path
        const unvisitedNodes = new Set(); // Set of all nodes we haven't finalized yet
    
        // Initialize distances: Infinity for all, 0 for startNode
        for (const node in graph) {
            distances[node] = Infinity;
            previousNodes[node] = null;
            unvisitedNodes.add(node);
        }
        distances[startNode] = 0;
    
        if (!graph[startNode]) {
            console.error("Start node does not exist in the graph.");
            return { distances: {}, previousNodes: {} };
        }
    
        // 2. Main loop
        while (unvisitedNodes.size > 0) {
            // Find the unvisited node with the smallest distance (this is where a priority queue would be efficient)
            let currentNode = null;
            for (const node of unvisitedNodes) {
                if (currentNode === null || distances[node] < distances[currentNode]) {
                    currentNode = node;
                }
            }
    
            // If the smallest distance among unvisited is Infinity, the remaining nodes are unreachable
            if (distances[currentNode] === Infinity) {
                break;
            }
    
            // For the current node, visit its unvisited neighbors
            const neighbors = graph[currentNode];
            for (const neighbor in neighbors) {
                if (unvisitedNodes.has(neighbor)) { // Only consider unvisited neighbors
                    const weight = neighbors[neighbor];
                    const potentialDistance = distances[currentNode] + weight;
    
                    // If a shorter path to the neighbor is found
                    if (potentialDistance < distances[neighbor]) {
                        distances[neighbor] = potentialDistance;
                        previousNodes[neighbor] = currentNode;
                    }
                }
            }
            // Mark the current node as visited (finalized)
            unvisitedNodes.delete(currentNode);
        }
    
        return { distances, previousNodes };
    }
    
    // Helper function to reconstruct the shortest path to a target node
    function getShortestPath(previousNodes, startNode, endNode) {
        const path = [];
        let currentNode = endNode;
    
        // If endNode is not reachable or not in the graph
        if (!previousNodes.hasOwnProperty(endNode) || previousNodes[endNode] === null && endNode !== startNode) {
             if (distances[endNode] === Infinity || !distances.hasOwnProperty(endNode)) {
                return []; // No path found
             }
        }
    
    
        while (currentNode !== null) {
            path.unshift(currentNode); // Add to the beginning of the array
            if (currentNode === startNode) {
                break; // We've reached the start node
            }
            currentNode = previousNodes[currentNode];
        }
    
        // If the first element is not the startNode, it means no path was found to endNode
        // (This can happen if endNode is unreachable or if endNode was the startNode and loop exited early)
        if (path.length === 0 || path[0] !== startNode) {
            if (endNode === startNode && previousNodes.hasOwnProperty(startNode)) { // Special case: startNode is endNode
                return [startNode];
            }
            return []; // No path found or endNode not reachable from startNode
        }
    
        return path;
    }
    
    
    // --- Example Usage ---
    const graph = {
        'A': { 'B': 4, 'C': 2 },
        'B': { 'A': 4, 'C': 5, 'D': 10 },
        'C': { 'A': 2, 'B': 5, 'D': 3, 'E': 8 }, // Added E
        'D': { 'B': 10, 'C': 3, 'E': 4, 'F': 11 }, // Added E, F
        'E': { 'C': 8, 'D': 4, 'F': 7 },         // Added F
        'F': { 'D': 11, 'E': 7 }
    };
    
    const startNode = 'A';
    const { distances, previousNodes } = dijkstra(graph, startNode);
    
    console.log("Distances from", startNode + ":");
    for (const node in distances) {
        console.log(`  ${node}: ${distances[node] === Infinity ? 'Infinity' : distances[node]}`);
    }
    // Expected Distances:
    // A: 0
    // B: 4
    // C: 2
    // D: 5 (A -> C -> D)
    // E: 9 (A -> C -> D -> E)
    // F: 16 (A -> C -> D -> E -> F)
    
    console.log("\nPrevious nodes for path reconstruction:");
    console.log(previousNodes);
    // Expected Previous Nodes:
    // { A: null, B: 'A', C: 'A', D: 'C', E: 'D', F: 'E' }
    
    
    console.log("\nShortest paths:");
    const targetNodes = ['D', 'E', 'F', 'A', 'G']; // 'G' is not in graph
    
    for (const targetNode of targetNodes) {
        const path = getShortestPath(previousNodes, startNode, targetNode);
        if (path.length > 0) {
            console.log(`  Path from ${startNode} to ${targetNode}: ${path.join(' -> ')} (Cost: ${distances[targetNode]})`);
        } else {
            console.log(`  No path found from ${startNode} to ${targetNode}`);
        }
    }
    // Expected Paths:
    // Path from A to D: A -> C -> D (Cost: 5)
    // Path from A to E: A -> C -> D -> E (Cost: 9)
    // Path from A to F: A -> C -> D -> E -> F (Cost: 16)
    // Path from A to A: A (Cost: 0)
    // No path found from A to G
    
    // Example with disconnected component (or node not reachable)
    const disconnectedGraph = {
        'A': { 'B': 1 },
        'B': { 'A': 1 },
        'C': { 'D': 1 },
        'D': { 'C': 1 }
    };
    
    console.log("\n--- Disconnected Graph Example ---");
    const startNode2 = 'A';
    const { distances: dist2, previousNodes: prev2 } = dijkstra(disconnectedGraph, startNode2);
    console.log("Distances from", startNode2 + ":");
    for (const node in dist2) {
        console.log(`  ${node}: ${dist2[node] === Infinity ? 'Infinity' : dist2[node]}`);
    }
    // Expected Distances:
    // A: 0
    // B: 1
    // C: Infinity
    // D: Infinity
    
    const pathAC = getShortestPath(prev2, startNode2, 'C');
    if (pathAC.length > 0) {
        console.log(`Path from ${startNode2} to C: ${pathAC.join(' -> ')}`);
    } else {
        console.log(`No path found from ${startNode2} to C`); // Expected
    }
    

    Explanation:

    1. dijkstra(graph, startNode) Function:

      • distances: An object to store the shortest known distance from startNode to every other node. Initialized to Infinity for all nodes and 0 for startNode.
      • previousNodes: An object to keep track of the "parent" node in the shortest path. This is used later to reconstruct the path.
      • unvisitedNodes: A Set of nodes that have not yet been finalized (i.e., their shortest path is not yet definitively known).
      • Main Loop (while (unvisitedNodes.size > 0)):
        • Select currentNode: It finds the node in unvisitedNodes that has the smallest current distances value. This is the step where a true priority queue (like a min-heap) would offer better performance (O(log N) for extraction instead of O(N) for searching).
        • Handle Unreachable Nodes: If distances[currentNode] is Infinity, it means all remaining unvisited nodes are unreachable from startNode, so we can break the loop.
        • Update Neighbors: For each neighbor of currentNode:
          • Calculate potentialDistance = distances[currentNode] + weight_of_edge(currentNode, neighbor).
          • If potentialDistance is less than the current distances[neighbor], it means we've found a shorter path to neighbor. So, update distances[neighbor] and set previousNodes[neighbor] to currentNode.
        • Mark as Visited: unvisitedNodes.delete(currentNode) removes the currentNode from the set, signifying its shortest path has been found and finalized.
      • Return: The function returns an object containing distances and previousNodes.
    2. getShortestPath(previousNodes, startNode, endNode) Function:

      • This function takes the previousNodes map (from dijkstra), the startNode, and the endNode as input.
      • It reconstructs the path by backtracking from endNode to startNode using the previousNodes map.
      • path.unshift(currentNode) adds the current node to the beginning of the path array to get the correct order.
      • It handles cases where no path exists (e.g., endNode is unreachable or not in the graph).

    Efficiency:

    • Time Complexity:
      • With the current simple way of finding the minimum distance node in unvisitedNodes (iterating through the set), the complexity is O(V^2) where V is the number of vertices, because the outer loop runs V times, and finding the minimum takes O(V) in the worst case.
      • If you use a min-heap based priority queue, the complexity becomes O((V + E) log V), where E is the number of edges. This is generally better for sparse graphs.
    • Space Complexity: O(V) for storing distances, previous nodes, and the unvisited set.

    This implementation provides a good foundation for understanding Dijkstra's algorithm. For production use with very large graphs, consider implementing or using a library for a min-heap priority queue.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.