Dijkstra Shortest Path Finder (javascript, written by Claude Code)

Claude Code wrote this javascript project from the task below. It installed and ran on a clean Ubuntu 22.04 machine as written.

Task given to the agent:

TASK: Dijkstra Shortest Path Finder

Write a program that finds the shortest path between nodes in a weighted graph using Dijkstra's algorithm, supporting multiple graph input formats, path visualization, and batch queries.

FUNCTIONAL REQUIREMENTS:
- Accept a graph definition file as a command-line argument (support adjacency list in JSON and edge list in CSV format)
- Accept source and destination nodes via --source and --destination flags
- Implement Dijkstra's algorithm with a priority queue (min-heap) for optimal performance
- Support both directed and undirected graphs via --directed flag (default: undirected)
- Report for the shortest path: total distance/weight, the complete node sequence, and the number of edges
- Support finding shortest paths from one source to all other nodes via --all flag (single-source shortest path)
- Support negative edge weight detection: warn if negative weights are found (Dijkstra doesn't handle them correctly) and suggest using Bellman-Ford instead
- Display the path in multiple formats via --format flag: text (default, showing node sequence with edge weights), json (structured output), and dot (Graphviz DOT format for visualization)
- Support batch queries: read multiple source-destination pairs from a file via --queries flag and compute shortest paths for all pairs
- Print graph statistics: total nodes, total edges, average degree, connected components count, and graph density
- Save results as JSON with --output flag (default: shortest_path.json)
- If no input is given, generate a sample weighted graph with 15 nodes and 25 edges, find shortest paths between several pairs of nodes, and demonstrate the all-pairs output
- Handle errors: disconnected nodes (no path exists), self-loops, duplicate edges, invalid node references, and malformed graph files

Create a complete JavaScript project for a clean Ubuntu 22.04 machine with only Node.js 20+ (LTS) installed. Include:
- Source code
- package.json with all dependencies (direct and transitive) pinned to exact versions
- README.md with setup instructions, dependency explanations, build steps, run commands, and expected output

[]

#!/usr/bin/env node
"use strict";

/**
 * Dijkstra Shortest Path Finder - Trial 1 (graphlib 2.1.8 + chalk 4.1.2)
 *
 * Finds shortest paths in weighted graphs using Dijkstra's algorithm with
 * priority queue optimization. Supports batch queries.
 */

const graphlib = require("graphlib");
const chalk = require("chalk");

// ---------------------------------------------------------------------------
// Priority Queue (min-heap) for Dijkstra
// ---------------------------------------------------------------------------
class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(item) {
    this.heap.push(item);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) return null;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return top;
  }

  get size() {
    return this.heap.length;
  }

  _bubbleUp(idx) {
    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);
      if (this.heap[parent].dist <= this.heap[idx].dist) break;
      [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
      idx = parent;
    }
  }

  _sinkDown(idx) {
    const length = this.heap.length;
    while (true) {
      let smallest = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;
      if (left < length && this.heap[left].dist < this.heap[smallest].dist) smallest = left;
      if (right < length && this.heap[right].dist < this.heap[smallest].dist) smallest = right;
      if (smallest === idx) break;
      [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
      idx = smallest;
    }
  }
}

// ---------------------------------------------------------------------------
// DijkstraPathFinder
// ---------------------------------------------------------------------------
class DijkstraPathFinder {
  constructor() {
    this.graph = new graphlib.Graph({ directed: true, multigraph: false, compound: false });
  }

  addEdge(source, target, weight) {
    if (weight < 0) throw new Error(`Edge weight must be non-negative, got ${weight}`);
    if (!this.graph.hasNode(source)) this.graph.setNode(source);
    if (!this.graph.hasNode(target)) this.graph.setNode(target);
    this.graph.setEdge(source, target, { weight });
  }

  addUndirectedEdge(nodeA, nodeB, weight) {
    this.addEdge(nodeA, nodeB, weight);
    this.addEdge(nodeB, nodeA, weight);
  }

  loadFromObject(graphData) {
    const directed = graphData.directed !== undefined ? graphData.directed : true;

    if (graphData.nodes) {
      for (const node of graphData.nodes) {
        const id = typeof node === "object" ? node.id : String(node);
        if (!this.graph.hasNode(id)) this.graph.setNode(id);
      }
    }

    if (graphData.edges) {
      for (const edge of graphData.edges) {
        const src = String(edge.source);
        const tgt = String(edge.target);
        const wt = parseFloat(edge.weight);
        if (directed) {
          this.addEdge(src, tgt, wt);
        } else {
          this.addUndirectedEdge(src, tgt, wt);
        }
      }
    }
  }

  loadFromFile(filepath) {
    const fs = require("fs");
    const data = JSON.parse(fs.readFileSync(filepath, "utf8"));
    this.loadFromObject(data);
  }

  dijkstra(source, target = null) {
    const nodes = this.graph.nodes();
    if (!nodes.includes(source)) {
      throw new Error(`Source node '${source}' not found in graph`);
    }

    const distances = {};
    const predecessors = {};
    const visited = new Set();

    for (const node of nodes) {
      distances[node] = Infinity;
      predecessors[node] = null;
    }
    distances[source] = 0;

    const pq = new MinHeap();
    pq.push({ dist: 0, node: source });

    while (pq.size > 0) {
      const { dist: currentDist, node: currentNode } = pq.pop();

      if (visited.has(currentNode)) continue;
      visited.add(currentNode);

      if (target !== null && currentNode === target) break;

      const outEdges = this.graph.outEdges(currentNode) || [];
      for (const edge of outEdges) {
        const neighbor = edge.w;
        if (visited.has(neighbor)) continue;

        const edgeData = this.graph.edge(edge);
        const weight = edgeData.weight;
        const newDist = currentDist + weight;

        if (newDist < distances[neighbor]) {
          distances[neighbor] = newDist;
          predecessors[neighbor] = currentNode;
          pq.push({ dist: newDist, node: neighbor });
        }
      }
    }

    const result = { distances, predecessors };

    if (target !== null) {
      result.target_distance = distances[target] !== undefined ? distances[target] : Infinity;
      result.target_path = this._reconstructPath(predecessors, source, target);
    }

    return result;
  }

  _reconstructPath(predecessors, source, target) {
    if (predecessors[target] === null && target !== source) return null;

    const path = [];
    let current = target;
    while (current !== null) {
      path.push(current);
      current = predecessors[current];
    }
    path.reverse();
    return path;
  }

  batchShortestPaths(queries) {
    const results = [];
    const cache = {};

    for (const query of queries) {
      const source = String(query.source);
      const target = String(query.target);

      if (!cache[source]) {
        cache[source] = this.dijkstra(source);
      }

      const dijkstraResult = cache[source];
      const distance = dijkstraResult.distances[target] !== undefined
        ? dijkstraResult.distances[target] : Infinity;
      const path = this._reconstructPath(dijkstraResult.predecessors, source, target);

      results.push({ source, target, distance, path });
    }

    return results;
  }

  getGraphStats() {
    const nodes = this.graph.nodes();
    const edges = this.graph.edges();
    const v = nodes.length;
    const e = edges.length;
    const maxEdges = v * (v - 1);
    const density = maxEdges > 0 ? e / maxEdges : 0;

    return {
      num_nodes: v,
      num_edges: e,
      is_directed: true,
      nodes: [...nodes].sort(),
      density: Math.round(density * 10000) / 10000,
    };
  }
}

// ---------------------------------------------------------------------------
// Sample graph
// ---------------------------------------------------------------------------
function createSampleGraph() {
  return {
    directed: false,
    nodes: ["A", "B", "C", "D", "E", "F", "G"],
    edges: [
      { source: "A", target: "B", weight: 4 },
      { source: "A", target: "C", weight: 2 },
      { source: "B", target: "D", weight: 5 },
      { source: "B", target: "C", weight: 1 },
      { source: "C", target: "D", weight: 8 },
      { source: "C", target: "E", weight: 10 },
      { source: "D", target: "E", weight: 2 },
      { source: "D", target: "F", weight: 6 },
      { source: "E", target: "F", weight: 3 },
      { source: "E", target: "G", weight: 1 },
      { source: "F", target: "G", weight: 7 },
    ],
  };
}

// ---------------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------------
function main() {
  console.log(chalk.blue("=".repeat(60)));
  console.log(chalk.blue.bold("  Dijkstra Shortest Path Finder (graphlib + chalk)"));
  console.log(chalk.blue("=".repeat(60)));

  const finder = new DijkstraPathFinder();
  finder.loadFromObject(createSampleGraph());

  const stats = finder.getGraphStats();
  console.log(chalk.cyan("\nGraph Statistics:"));
  console.log(`  Nodes: ${stats.num_nodes}`);
  console.log(`  Edges: ${stats.num_edges}`);
  console.log(`  Directed: ${stats.is_directed}`);
  console.log(`  Density: ${stats.density}`);
  console.log(`  Vertices: ${stats.nodes.join(", ")}`);

  const sep = "\u2500".repeat(60);

  // Single query
  console.log(`\n${sep}`);
  console.log(chalk.yellow("Single Query: A -> G"));
  console.log(sep);

  const result = finder.dijkstra("A", "G");
  const path = result.target_path;
  const distance = result.target_distance;
  console.log(`  Shortest distance: ${chalk.green(distance)}`);
  console.log(`  Path: ${chalk.green(path ? path.join(" -> ") : "No path found")}`);

  // All distances from A
  console.log(`\n${sep}`);
  console.log(chalk.yellow("All Distances from A:"));
  console.log(sep);

  const allResult = finder.dijkstra("A");
  const sortedNodes = Object.keys(allResult.distances).sort();
  for (const node of sortedNodes) {
    const dist = allResult.distances[node];
    const nodePath = finder._reconstructPath(allResult.predecessors, "A", node);
    const pathStr = nodePath ? nodePath.join(" -> ") : "N/A";
    const distStr = isFinite(dist) ? String(dist).padStart(5) : "  Inf";
    console.log(`  A -> ${node}: distance = ${distStr}, path = ${pathStr}`);
  }

  // Batch queries
  console.log(`\n${sep}`);
  console.log(chalk.yellow("Batch Queries:"));
  console.log(sep);

  const queries = [
    { source: "A", target: "G" },
    { source: "A", target: "F" },
    { source: "B", target: "G" },
    { source: "C", target: "F" },
    { source: "D", target: "A" },
    { source: "G", target: "A" },
  ];

  const batchResults = finder.batchShortestPaths(queries);
  for (const r of batchResults) {
    const pathStr = r.path ? r.path.join(" -> ") : "No path";
    const distStr = isFinite(r.distance) ? String(r.distance) : "unreachable";
    console.log(`  ${r.source} -> ${r.target}: ${distStr.padStart(12)}  |  ${pathStr}`);
  }

  console.log(`\n${chalk.green("Done!")}`);
}

main();

{
  "name": "dijkstra-shortest-path-trial1",
  "version": "1.0.0",
  "description": "Dijkstra Shortest Path Finder using graphlib and chalk",
  "main": "dijkstra.js",
  "scripts": {
    "start": "node dijkstra.js"
  },
  "dependencies": {
    "graphlib": "2.1.8",
    "chalk": "4.1.2"
  }
}