Dijkstra Shortest Path Finder (java, written by Codex)

Codex wrote this java project from the task below. It does not run 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 Java project for a clean Ubuntu 22.04 machine with only JDK 17+ installed. Include:
- Source code
- pom.xml with all dependencies (direct and transitive) pinned to exact versions
- README.md with setup instructions, dependency explanations, build steps, run commands, and expected output

[]

<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
  <modelVersion>4.0.0</modelVersion>
  <groupId>org.tmlr</groupId>
  <artifactId>dijkstra-shortest-path-finder</artifactId>
  <version>1.0.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
  </properties>
  <build>
    <plugins>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-assembly-plugin</artifactId>
        <version>3.7.1</version>
        <configuration>
          <archive>
            <manifest>
              <mainClass>DijkstraShortestPathFinder</mainClass>
            </manifest>
          </archive>
          <descriptorRefs>
            <descriptorRef>jar-with-dependencies</descriptorRef>
          </descriptorRefs>
        </configuration>
      </plugin>
    </plugins>
  </build>
</project>

# Dijkstra Shortest Path Finder (Java)

## Requirements
- Ubuntu 22.04
- JDK 17+
- Maven 3.8+

## Build
```bash
mvn -q -DskipTests package assembly:single
```

## Run
```bash
java -cp target/dijkstra-shortest-path-finder-1.0.0-jar-with-dependencies.jar DijkstraShortestPathFinder graph.csv --source A --destination D
java -cp target/dijkstra-shortest-path-finder-1.0.0-jar-with-dependencies.jar DijkstraShortestPathFinder graph.json --source A --all --directed
java -cp target/dijkstra-shortest-path-finder-1.0.0-jar-with-dependencies.jar DijkstraShortestPathFinder 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 java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.*;
import java.time.Instant;
import java.util.*;

public class DijkstraShortestPathFinder {
    private static class Config {
        String file;
        String source;
        String destination;
        boolean directed;
        boolean all;
        String format = "text";
        String queries;
        String output = "shortest_path.json";
    }

    private record Edge(String to, double w) {}

    public static void main(String[] args) {
        try {
            Config cfg = parseArgs(args);
            if (cfg.file == null) {
                cfg.file = "sample_graph.csv";
                writeSample(Paths.get(cfg.file));
                cfg.source = cfg.source == null ? "N1" : cfg.source;
                cfg.destination = cfg.destination == null ? "N15" : cfg.destination;
            }

            Map<String, List<Edge>> g = loadGraph(Paths.get(cfg.file), cfg.directed);
            Map<String, Object> stats = graphStats(g, cfg.directed);
            if (((Number) stats.get("negativeEdges")).intValue() > 0) {
                System.err.println("Warning: negative edge weights found; Bellman-Ford is recommended.");
            }

            List<Map<String, Object>> results = new ArrayList<>();
            if (cfg.queries != null) {
                for (String[] q : parseQueries(Paths.get(cfg.queries))) results.add(queryOne(g, q[0], q[1]));
            } else if (cfg.all && cfg.source != null) {
                DijkstraResult dr = dijkstra(g, cfg.source);
                for (String n : g.keySet()) {
                    Double d = dr.dist.getOrDefault(n, Double.POSITIVE_INFINITY);
                    if (Double.isFinite(d)) {
                        List<String> path = buildPath(dr.prev, cfg.source, n);
                        results.add(Map.of("source", cfg.source, "destination", n, "exists", true, "totalDistance", d, "nodeSequence", path, "edges", Math.max(0, path.size() - 1)));
                    } else {
                        results.add(Map.of("source", cfg.source, "destination", n, "exists", false, "message", "No path"));
                    }
                }
            } else {
                if (cfg.source == null || cfg.destination == null) throw new IllegalArgumentException("--source and --destination are required unless --all or --queries is used");
                results.add(queryOne(g, cfg.source, cfg.destination));
            }

            for (Map<String, Object> r : results) {
                System.out.println(formatResult(r, cfg.format));
                if (!"json".equals(cfg.format)) System.out.println();
            }

            Map<String, Object> report = new LinkedHashMap<>();
            report.put("generatedAt", Instant.now().toString());
            report.put("config", Map.of(
                "file", cfg.file,
                "source", cfg.source,
                "destination", cfg.destination,
                "directed", cfg.directed,
                "all", cfg.all,
                "format", cfg.format,
                "queries", cfg.queries,
                "output", cfg.output
            ));
            report.put("graphStats", stats);
            report.put("results", results);

            Files.writeString(Paths.get(cfg.output), toJson(report), StandardCharsets.UTF_8);
        } catch (Exception ex) {
            System.err.println("Error: " + ex.getMessage());
            System.exit(1);
        }
    }

    private static Config parseArgs(String[] args) {
        Config cfg = new Config();
        List<String> pos = new ArrayList<>();
        for (int i = 0; i < args.length; i++) {
            String a = args[i];
            if (!a.startsWith("--")) { pos.add(a); continue; }
            switch (a) {
                case "--source" -> cfg.source = args[++i];
                case "--destination" -> cfg.destination = args[++i];
                case "--directed" -> cfg.directed = true;
                case "--all" -> cfg.all = true;
                case "--format" -> cfg.format = args[++i];
                case "--queries" -> cfg.queries = args[++i];
                case "--output" -> cfg.output = args[++i];
                default -> throw new IllegalArgumentException("Unknown option: " + a);
            }
        }
        if (!pos.isEmpty()) cfg.file = pos.get(0);
        return cfg;
    }

    private static Map<String, List<Edge>> loadGraph(Path p, boolean directed) throws IOException {
        Map<String, List<Edge>> g = new LinkedHashMap<>();
        var add = new Object() {
            void edge(String u, String v, double w) {
                g.computeIfAbsent(u, k -> new ArrayList<>()).add(new Edge(v, w));
            }
        };

        if (p.toString().toLowerCase().endsWith(".json")) {
            String txt = Files.readString(p, StandardCharsets.UTF_8).replaceAll("\\s+", "");
            // Minimal parser for adjacency JSON map
            if (!txt.startsWith("{") || !txt.endsWith("}")) throw new IllegalArgumentException("Invalid JSON graph");
            txt = txt.substring(1, txt.length() - 1);
            String[] nodes = txt.split("},");
            for (String node : nodes) {
                if (!node.endsWith("}")) node = node + "}";
                int c = node.indexOf(':');
                String u = unq(node.substring(0, c));
                String body = node.substring(c + 1).trim();
                if (body.startsWith("{")) body = body.substring(1, body.length() - 1);
                if (!body.isEmpty()) {
                    String[] parts = body.split(",");
                    for (String part : parts) {
                        String[] kv = part.split(":");
                        String v = unq(kv[0]);
                        double w = Double.parseDouble(kv[1]);
                        add.edge(u, v, w);
                        if (!directed) add.edge(v, u, w);
                    }
                }
            }
        } else {
            List<String> lines = Files.readAllLines(p, StandardCharsets.UTF_8);
            for (int i = 1; i < lines.size(); i++) {
                String[] parts = lines.get(i).split(",");
                if (parts.length < 3) continue;
                String u = parts[0].trim();
                String v = parts[1].trim();
                double w = Double.parseDouble(parts[2].trim());
                add.edge(u, v, w);
                if (!directed) add.edge(v, u, w);
            }
        }

        // ensure all nodes present
        List<String> addNodes = new ArrayList<>();
        for (var e : g.entrySet()) for (Edge x : e.getValue()) if (!g.containsKey(x.to)) addNodes.add(x.to);
        addNodes.forEach(n -> g.putIfAbsent(n, new ArrayList<>()));

        return g;
    }

    private static String unq(String s) {
        s = s.trim();
        if (s.startsWith("\"") && s.endsWith("\"")) return s.substring(1, s.length() - 1);
        return s;
    }

    private static Map<String, Object> graphStats(Map<String, List<Edge>> g, boolean directed) {
        int n = g.size();
        int e = 0;
        int neg = 0;
        int degree = 0;
        for (var v : g.values()) {
            e += v.size();
            degree += v.size();
            for (Edge x : v) if (x.w < 0) neg++;
        }
        if (!directed) e /= 2;

        Set<String> vis = new HashSet<>();
        int comps = 0;
        for (String s : g.keySet()) {
            if (vis.contains(s)) continue;
            comps++;
            Deque<String> st = new ArrayDeque<>();
            st.push(s);
            vis.add(s);
            while (!st.isEmpty()) {
                String u = st.pop();
                for (Edge x : g.getOrDefault(u, List.of())) {
                    if (!vis.contains(x.to)) {
                        vis.add(x.to);
                        st.push(x.to);
                    }
                }
            }
        }

        double density = n > 1 ? (directed ? (double) e / (n * (n - 1)) : (2.0 * e) / (n * (n - 1))) : 0.0;
        return Map.of("totalNodes", n, "totalEdges", e, "averageDegree", n == 0 ? 0.0 : (double) degree / n, "connectedComponents", comps, "density", density, "negativeEdges", neg);
    }

    private static class DijkstraResult {
        Map<String, Double> dist = new LinkedHashMap<>();
        Map<String, String> prev = new LinkedHashMap<>();
    }

    private static DijkstraResult dijkstra(Map<String, List<Edge>> g, String src) {
        DijkstraResult out = new DijkstraResult();
        for (String n : g.keySet()) out.dist.put(n, Double.POSITIVE_INFINITY);
        out.dist.put(src, 0.0);

        PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingDouble(out.dist::get));
        pq.add(src);

        while (!pq.isEmpty()) {
            String u = pq.poll();
            double du = out.dist.get(u);
            for (Edge e : g.getOrDefault(u, List.of())) {
                double nd = du + e.w;
                if (nd < out.dist.get(e.to)) {
                    out.dist.put(e.to, nd);
                    out.prev.put(e.to, u);
                    pq.remove(e.to);
                    pq.add(e.to);
                }
            }
        }
        return out;
    }

    private static List<String> buildPath(Map<String, String> prev, String src, String dst) {
        if (src.equals(dst)) return List.of(src);
        LinkedList<String> path = new LinkedList<>();
        String cur = dst;
        while (cur != null && !cur.equals(src)) {
            path.addFirst(cur);
            cur = prev.get(cur);
        }
        if (!src.equals(cur)) return null;
        path.addFirst(src);
        return path;
    }

    private static Map<String, Object> queryOne(Map<String, List<Edge>> g, String src, String dst) {
        DijkstraResult dr = dijkstra(g, src);
        double d = dr.dist.getOrDefault(dst, Double.POSITIVE_INFINITY);
        if (!Double.isFinite(d)) return Map.of("source", src, "destination", dst, "exists", false, "message", "No path");
        List<String> p = buildPath(dr.prev, src, dst);
        return Map.of("source", src, "destination", dst, "exists", true, "totalDistance", d, "nodeSequence", p, "edges", Math.max(0, p.size() - 1));
    }

    private static List<String[]> parseQueries(Path p) throws IOException {
        List<String[]> q = new ArrayList<>();
        for (String line : Files.readAllLines(p, StandardCharsets.UTF_8)) {
            line = line.trim();
            if (line.isEmpty()) continue;
            String[] s = line.split(",");
            q.add(new String[] { s[0].trim(), s[1].trim() });
        }
        return q;
    }

    private static String formatResult(Map<String, Object> r, String fmt) {
        if ("json".equals(fmt)) return toJson(r);
        if ("dot".equals(fmt)) {
            StringBuilder sb = new StringBuilder("digraph G {\n");
            @SuppressWarnings("unchecked") List<String> seq = (List<String>) r.get("nodeSequence");
            if (seq != null) for (int i = 0; i < seq.size() - 1; i++) sb.append("  \"").append(seq.get(i)).append("\" -> \"").append(seq.get(i + 1)).append("\";\n");
            sb.append("}");
            return sb.toString();
        }
        if (!(Boolean) r.getOrDefault("exists", false)) return "No path from " + r.get("source") + " to " + r.get("destination");
        @SuppressWarnings("unchecked") List<String> seq = (List<String>) r.get("nodeSequence");
        return "Distance: " + r.get("totalDistance") + "\nPath: " + String.join(" -> ", seq) + "\nEdges: " + r.get("edges");
    }

    private static void writeSample(Path p) throws IOException {
        List<String> lines = new ArrayList<>();
        lines.add("source,destination,weight");
        for (int i = 1; i <= 14; i++) lines.add("N" + i + ",N" + (i + 1) + "," + (1 + (i % 5)));
        lines.addAll(List.of(
            "N1,N5,4", "N2,N8,3", "N3,N10,6", "N4,N12,2", "N6,N11,5", "N7,N13,2", "N8,N14,7", "N9,N15,1", "N5,N9,3", "N10,N14,2", "N11,N15,4"
        ));
        Files.write(p, lines, StandardCharsets.UTF_8);
    }

    private static String toJson(Object obj) {
        if (obj == null) return "null";
        if (obj instanceof String s) return '"' + s.replace("\\", "\\\\").replace("\"", "\\\"") + '"';
        if (obj instanceof Number || obj instanceof Boolean) return obj.toString();
        if (obj instanceof Map<?, ?> m) {
            StringBuilder sb = new StringBuilder("{");
            boolean first = true;
            for (Map.Entry<?, ?> e : m.entrySet()) {
                if (!first) sb.append(',');
                first = false;
                sb.append(toJson(String.valueOf(e.getKey()))).append(':').append(toJson(e.getValue()));
            }
            sb.append('}');
            return sb.toString();
        }
        if (obj instanceof Iterable<?> it) {
            StringBuilder sb = new StringBuilder("[");
            boolean first = true;
            for (Object x : it) {
                if (!first) sb.append(',');
                first = false;
                sb.append(toJson(x));
            }
            sb.append(']');
            return sb.toString();
        }
        return toJson(String.valueOf(obj));
    }
}