Dijkstra Shortest Path Finder (javascript, written by Codex)

Codex 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

[]

{
  "name": "dijkstra-shortest-path-finder",
  "version": "1.0.0",
  "lockfileVersion": 3,
  "requires": true,
  "packages": {
    "": {
      "name": "dijkstra-shortest-path-finder",
      "version": "1.0.0",
      "license": "MIT"
    }
  }
}

{
  "name": "dijkstra-shortest-path-finder",
  "version": "1.0.0",
  "description": "Shortest path finder using Dijkstra",
  "type": "module",
  "main": "src/index.js",
  "scripts": { "start": "node src/index.js" },
  "engines": { "node": ">=20.0.0" },
  "license": "MIT"
}

# Dijkstra Shortest Path Finder (JavaScript)

## Requirements
- Ubuntu 22.04
- Node.js 20+

## Install
```bash
npm install
```

## Run
```bash
node src/index.js graph.csv --source A --destination D
node src/index.js graph.json --source A --all --directed
node src/index.js graph.csv --queries pairs.txt --format json --output shortest_path.json
```

If no input is provided, a sample weighted graph is generated and demonstrated.

import fs from "node:fs";
import path from "node:path";
import process from "node:process";

class MinHeap {
  constructor() { this.a = []; }
  push(item) { this.a.push(item); this.up(this.a.length - 1); }
  up(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.a[p].dist <= this.a[i].dist) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  pop() {
    if (!this.a.length) return null;
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this.down(0); }
    return top;
  }
  down(i) {
    const n = this.a.length;
    while (true) {
      let m = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && this.a[l].dist < this.a[m].dist) m = l;
      if (r < n && this.a[r].dist < this.a[m].dist) m = r;
      if (m === i) break;
      [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
      i = m;
    }
  }
  get size() { return this.a.length; }
}

function parseArgs(argv) {
  const cfg = {
    file: null,
    source: null,
    destination: null,
    directed: false,
    all: false,
    format: "text",
    queries: null,
    output: "shortest_path.json"
  };
  const pos = [];
  for (let i = 0; i < argv.length; i += 1) {
    const a = argv[i];
    if (!a.startsWith("--")) { pos.push(a); continue; }
    if (a === "--source") cfg.source = argv[++i];
    else if (a === "--destination") cfg.destination = argv[++i];
    else if (a === "--directed") cfg.directed = true;
    else if (a === "--all") cfg.all = true;
    else if (a === "--format") cfg.format = argv[++i];
    else if (a === "--queries") cfg.queries = argv[++i];
    else if (a === "--output") cfg.output = argv[++i];
    else throw new Error(`Unknown option: ${a}`);
  }
  if (pos.length > 0) cfg.file = pos[0];
  return cfg;
}

function loadGraph(file, directed) {
  const graph = new Map();
  const addEdge = (u, v, w) => {
    if (!graph.has(u)) graph.set(u, []);
    graph.get(u).push({ to: v, w });
  };

  if (file.toLowerCase().endsWith(".json")) {
    const obj = JSON.parse(fs.readFileSync(file, "utf8"));
    for (const [u, nbrs] of Object.entries(obj)) {
      for (const [v, w] of Object.entries(nbrs)) {
        const wt = Number(w);
        addEdge(u, v, wt);
        if (!directed) addEdge(v, u, wt);
      }
    }
  } else {
    const lines = fs.readFileSync(file, "utf8").trim().split(/\r?\n/);
    for (let i = 1; i < lines.length; i += 1) {
      const [u, v, wStr] = lines[i].split(",").map((x) => x.trim());
      const w = Number(wStr);
      addEdge(u, v, w);
      if (!directed) addEdge(v, u, w);
    }
  }

  return graph;
}

function graphStats(graph, directed) {
  const nodes = [...graph.keys()];
  let edges = 0;
  let degreeSum = 0;
  let negatives = 0;
  for (const [u, nbrs] of graph.entries()) {
    edges += nbrs.length;
    degreeSum += nbrs.length;
    negatives += nbrs.filter((e) => e.w < 0).length;
    for (const e of nbrs) if (!graph.has(e.to)) graph.set(e.to, []);
  }
  if (!directed) edges /= 2;

  const visited = new Set();
  let comps = 0;
  for (const n of graph.keys()) {
    if (visited.has(n)) continue;
    comps += 1;
    const stack = [n];
    visited.add(n);
    while (stack.length) {
      const cur = stack.pop();
      for (const e of graph.get(cur) || []) {
        if (!visited.has(e.to)) {
          visited.add(e.to);
          stack.push(e.to);
        }
      }
    }
  }

  const N = graph.size;
  const density = N > 1 ? (directed ? edges / (N * (N - 1)) : (2 * edges) / (N * (N - 1))) : 0;

  return {
    totalNodes: N,
    totalEdges: edges,
    averageDegree: N ? degreeSum / N : 0,
    connectedComponents: comps,
    density,
    negativeEdges: negatives
  };
}

function dijkstra(graph, src) {
  const dist = new Map();
  const prev = new Map();
  for (const n of graph.keys()) dist.set(n, Infinity);
  dist.set(src, 0);

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

  while (pq.size) {
    const { node, dist: d } = pq.pop();
    if (d !== dist.get(node)) continue;
    for (const e of graph.get(node) || []) {
      const nd = d + e.w;
      if (nd < dist.get(e.to)) {
        dist.set(e.to, nd);
        prev.set(e.to, node);
        pq.push({ node: e.to, dist: nd });
      }
    }
  }
  return { dist, prev };
}

function buildPath(prev, src, dst) {
  if (src === dst) return [src];
  const path = [];
  let cur = dst;
  while (cur !== undefined && cur !== src) {
    path.push(cur);
    cur = prev.get(cur);
  }
  if (cur !== src) return null;
  path.push(src);
  return path.reverse();
}

function queryOne(graph, src, dst) {
  const { dist, prev } = dijkstra(graph, src);
  const d = dist.get(dst);
  if (!Number.isFinite(d)) return { source: src, destination: dst, exists: false, message: "No path" };
  const path = buildPath(prev, src, dst);
  return {
    source: src,
    destination: dst,
    exists: true,
    totalDistance: d,
    nodeSequence: path,
    edges: Math.max(0, path.length - 1)
  };
}

function formatOutput(result, format) {
  if (format === "json") return JSON.stringify(result, null, 2);
  if (format === "dot") {
    const lines = ["digraph G {"];
    if (result.nodeSequence) {
      for (let i = 0; i < result.nodeSequence.length - 1; i += 1) {
        lines.push(`  \"${result.nodeSequence[i]}\" -> \"${result.nodeSequence[i + 1]}\";`);
      }
    }
    lines.push("}");
    return lines.join("\n");
  }
  if (!result.exists) return `No path from ${result.source} to ${result.destination}`;
  return `Distance: ${result.totalDistance}\nPath: ${result.nodeSequence.join(" -> ")}\nEdges: ${result.edges}`;
}

function parseQueries(file) {
  return fs.readFileSync(file, "utf8").split(/\r?\n/).map((l) => l.trim()).filter(Boolean).map((l) => {
    const [s, d] = l.split(",").map((x) => x.trim());
    return { source: s, destination: d };
  });
}

function makeSample(file) {
  const nodes = Array.from({ length: 15 }, (_, i) => `N${i + 1}`);
  const edges = [];
  const add = (u, v, w) => edges.push(`${u},${v},${w}`);
  for (let i = 0; i < 14; i += 1) add(nodes[i], nodes[i + 1], 1 + (i % 5));
  add("N1", "N5", 4); add("N2", "N8", 3); add("N3", "N10", 6); add("N4", "N12", 2);
  add("N6", "N11", 5); add("N7", "N13", 2); add("N8", "N14", 7); add("N9", "N15", 1);
  add("N5", "N9", 3); add("N10", "N14", 2); add("N11", "N15", 4);
  const csv = `source,destination,weight\n${edges.join("\n")}\n`;
  fs.writeFileSync(file, csv, "utf8");
}

function main() {
  try {
    const cfg = parseArgs(process.argv.slice(2));
    if (!cfg.file) {
      cfg.file = path.resolve("sample_graph.csv");
      makeSample(cfg.file);
      cfg.source = "N1";
      cfg.destination = "N15";
    }

    const graph = loadGraph(cfg.file, cfg.directed);
    const stats = graphStats(graph, cfg.directed);
    if (stats.negativeEdges > 0) process.stderr.write("Warning: negative edges detected; Dijkstra may be invalid. Use Bellman-Ford.\n");

    const results = [];
    if (cfg.queries) {
      const pairs = parseQueries(cfg.queries);
      for (const q of pairs) results.push(queryOne(graph, q.source, q.destination));
    } else if (cfg.all && cfg.source) {
      const { dist, prev } = dijkstra(graph, cfg.source);
      for (const n of graph.keys()) {
        const d = dist.get(n);
        const p = Number.isFinite(d) ? buildPath(prev, cfg.source, n) : null;
        results.push({ source: cfg.source, destination: n, exists: Number.isFinite(d), totalDistance: d, nodeSequence: p, edges: p ? p.length - 1 : 0 });
      }
    } else {
      if (!cfg.source || !cfg.destination) throw new Error("--source and --destination are required unless --all or --queries is used");
      results.push(queryOne(graph, cfg.source, cfg.destination));
    }

    for (const r of results) {
      console.log(formatOutput(r, cfg.format));
      if (cfg.format !== "json") console.log("");
    }

    const report = { config: cfg, graphStats: stats, results };
    fs.writeFileSync(cfg.output, JSON.stringify(report, null, 2), "utf8");
  } catch (err) {
    console.error(`Error: ${err.message}`);
    process.exit(1);
  }
}

main();