Dijkstra Shortest Path Finder (cpp, written by Codex)

Codex wrote this cpp 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 C++ project for a clean Ubuntu 22.04 machine with only G++ 12+ and CMake 3.22+ installed. Include:
- Source code
- CMakeLists.txt with all dependencies (direct and transitive) pinned to exact versions
- README.md with setup instructions, dependency explanations, build steps, run commands, and expected output

[]

cmake_minimum_required(VERSION 3.16)
project(dijkstra_shortest_path_finder LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

add_executable(dijkstra_shortest_path_finder src/main.cpp)

# Dijkstra Shortest Path Finder (C++)

## Requirements
- Ubuntu 22.04
- CMake 3.16+
- C++20 compiler

## Build
```bash
cmake -S . -B build
cmake --build build
```

## Run
```bash
./build/dijkstra_shortest_path_finder graph.csv --source A --destination D
./build/dijkstra_shortest_path_finder graph.json --source A --all --directed
./build/dijkstra_shortest_path_finder graph.csv --queries pairs.txt --format json --output shortest_path.json
```

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

#include <algorithm>
#include <filesystem>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace fs = std::filesystem;

struct Config {
    std::string file;
    std::string source;
    std::string destination;
    bool directed = false;
    bool all = false;
    std::string format = "text";
    std::string queries;
    std::string output = "shortest_path.json";
};

struct Edge { std::string to; double w; };
using Graph = std::map<std::string, std::vector<Edge>>;

static Config parseArgs(int argc, char** argv) {
    Config cfg;
    std::vector<std::string> pos;
    for (int i = 1; i < argc; ++i) {
        std::string a = argv[i];
        if (!a.starts_with("--")) { pos.push_back(a); continue; }
        if (a == "--source" && i + 1 < argc) cfg.source = argv[++i];
        else if (a == "--destination" && i + 1 < argc) cfg.destination = argv[++i];
        else if (a == "--directed") cfg.directed = true;
        else if (a == "--all") cfg.all = true;
        else if (a == "--format" && i + 1 < argc) cfg.format = argv[++i];
        else if (a == "--queries" && i + 1 < argc) cfg.queries = argv[++i];
        else if (a == "--output" && i + 1 < argc) cfg.output = argv[++i];
        else throw std::runtime_error("Unknown option: " + a);
    }
    if (!pos.empty()) cfg.file = pos[0];
    return cfg;
}

static void addEdge(Graph& g, const std::string& u, const std::string& v, double w, bool directed) {
    g[u].push_back({v, w});
    if (!directed) g[v].push_back({u, w});
    if (!g.count(v)) g[v] = {};
}

static Graph loadGraph(const fs::path& p, bool directed) {
    Graph g;
    if (p.extension() == ".json") {
        // Minimal JSON adjacency parser: {"A":{"B":1.2}}
        std::string txt;
        { std::ifstream in(p); std::ostringstream ss; ss << in.rdbuf(); txt = ss.str(); }
        txt.erase(std::remove_if(txt.begin(), txt.end(), [](unsigned char c){ return std::isspace(c); }), txt.end());
        if (txt.size() < 2 || txt.front() != '{' || txt.back() != '}') throw std::runtime_error("Invalid JSON graph");
        txt = txt.substr(1, txt.size() - 2);
        std::size_t i = 0;
        while (i < txt.size()) {
            std::size_t q1 = txt.find('"', i), q2 = txt.find('"', q1 + 1);
            std::string u = txt.substr(q1 + 1, q2 - q1 - 1);
            std::size_t b1 = txt.find('{', q2), b2 = txt.find('}', b1);
            std::string body = txt.substr(b1 + 1, b2 - b1 - 1);
            if (!body.empty()) {
                std::stringstream ss(body);
                std::string part;
                while (std::getline(ss, part, ',')) {
                    auto c = part.find(':');
                    std::string v = part.substr(1, c - 2);
                    double w = std::stod(part.substr(c + 1));
                    addEdge(g, u, v, w, directed);
                }
            }
            i = b2 + 1;
            if (i < txt.size() && txt[i] == ',') i++;
        }
    } else {
        std::ifstream in(p);
        std::string line;
        std::getline(in, line); // header
        while (std::getline(in, line)) {
            if (line.empty()) continue;
            std::stringstream ss(line);
            std::string u, v, ws;
            std::getline(ss, u, ',');
            std::getline(ss, v, ',');
            std::getline(ss, ws, ',');
            addEdge(g, u, v, std::stod(ws), directed);
        }
    }
    return g;
}

struct Stats {
    int nodes = 0;
    int edges = 0;
    double avgDegree = 0;
    int components = 0;
    double density = 0;
    int negative = 0;
};

static Stats graphStats(const Graph& g, bool directed) {
    Stats s;
    s.nodes = static_cast<int>(g.size());
    int degSum = 0;
    for (const auto& [u, es] : g) {
        degSum += static_cast<int>(es.size());
        s.edges += static_cast<int>(es.size());
        for (const auto& e : es) if (e.w < 0) s.negative++;
    }
    if (!directed) s.edges /= 2;
    s.avgDegree = s.nodes ? static_cast<double>(degSum) / s.nodes : 0;

    std::set<std::string> vis;
    for (const auto& [start, _] : g) {
        if (vis.count(start)) continue;
        s.components++;
        std::vector<std::string> st = {start};
        vis.insert(start);
        while (!st.empty()) {
            auto u = st.back(); st.pop_back();
            for (const auto& e : g.at(u)) {
                if (!vis.count(e.to)) {
                    vis.insert(e.to);
                    st.push_back(e.to);
                }
            }
        }
    }

    if (s.nodes > 1) s.density = directed ? (double)s.edges / (s.nodes * (s.nodes - 1)) : (2.0 * s.edges) / (s.nodes * (s.nodes - 1));
    return s;
}

struct Dij {
    std::map<std::string, double> dist;
    std::map<std::string, std::string> prev;
};

static Dij dijkstra(const Graph& g, const std::string& src) {
    Dij d;
    for (const auto& [n, _] : g) d.dist[n] = std::numeric_limits<double>::infinity();
    d.dist[src] = 0;

    using Q = std::pair<double, std::string>;
    std::priority_queue<Q, std::vector<Q>, std::greater<>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != d.dist[u]) continue;
        for (const auto& e : g.at(u)) {
            double nd = du + e.w;
            if (nd < d.dist[e.to]) {
                d.dist[e.to] = nd;
                d.prev[e.to] = u;
                pq.push({nd, e.to});
            }
        }
    }
    return d;
}

static std::vector<std::string> buildPath(const std::map<std::string, std::string>& prev, const std::string& src, const std::string& dst) {
    if (src == dst) return {src};
    std::vector<std::string> rev;
    std::string cur = dst;
    while (cur != src) {
        rev.push_back(cur);
        auto it = prev.find(cur);
        if (it == prev.end()) return {};
        cur = it->second;
    }
    rev.push_back(src);
    std::reverse(rev.begin(), rev.end());
    return rev;
}

struct QueryResult {
    std::string source, destination;
    bool exists = false;
    double dist = 0;
    std::vector<std::string> path;
    int edges = 0;
    std::string message;
};

static QueryResult queryOne(const Graph& g, const std::string& src, const std::string& dst) {
    auto d = dijkstra(g, src);
    auto it = d.dist.find(dst);
    if (it == d.dist.end() || !std::isfinite(it->second)) return {src, dst, false, 0, {}, 0, "No path"};
    auto path = buildPath(d.prev, src, dst);
    return {src, dst, true, it->second, path, static_cast<int>(path.size()) - 1, ""};
}

static std::string toJson(const QueryResult& r) {
    std::ostringstream out;
    out << "{\"source\":\"" << r.source << "\",\"destination\":\"" << r.destination << "\",\"exists\":" << (r.exists?"true":"false");
    if (r.exists) {
        out << ",\"totalDistance\":" << r.dist << ",\"nodeSequence\":[";
        for (std::size_t i = 0; i < r.path.size(); ++i) { if (i) out << ","; out << "\"" << r.path[i] << "\""; }
        out << "],\"edges\":" << r.edges;
    } else {
        out << ",\"message\":\"" << r.message << "\"";
    }
    out << "}";
    return out.str();
}

static std::string formatResult(const QueryResult& r, const std::string& fmt) {
    if (fmt == "json") return toJson(r);
    if (fmt == "dot") {
        std::ostringstream out;
        out << "digraph G {\n";
        for (std::size_t i = 0; i + 1 < r.path.size(); ++i) out << "  \"" << r.path[i] << "\" -> \"" << r.path[i+1] << "\";\n";
        out << "}";
        return out.str();
    }
    if (!r.exists) return "No path from " + r.source + " to " + r.destination;
    std::ostringstream out;
    out << "Distance: " << r.dist << "\nPath: ";
    for (std::size_t i = 0; i < r.path.size(); ++i) { if (i) out << " -> "; out << r.path[i]; }
    out << "\nEdges: " << r.edges;
    return out.str();
}

static std::vector<std::pair<std::string,std::string>> parseQueries(const fs::path& p) {
    std::vector<std::pair<std::string,std::string>> q;
    std::ifstream in(p);
    std::string line;
    while (std::getline(in, line)) {
        if (line.empty()) continue;
        std::stringstream ss(line);
        std::string s, d;
        std::getline(ss, s, ',');
        std::getline(ss, d, ',');
        q.push_back({s, d});
    }
    return q;
}

static void writeSample(const fs::path& p) {
    std::ofstream out(p);
    out << "source,destination,weight\n";
    for (int i = 1; i <= 14; ++i) out << "N" << i << ",N" << (i + 1) << "," << (1 + (i % 5)) << "\n";
    out << "N1,N5,4\nN2,N8,3\nN3,N10,6\nN4,N12,2\nN6,N11,5\nN7,N13,2\nN8,N14,7\nN9,N15,1\nN5,N9,3\nN10,N14,2\nN11,N15,4\n";
}

int main(int argc, char** argv) {
    try {
        Config cfg = parseArgs(argc, argv);
        if (cfg.file.empty()) {
            cfg.file = "sample_graph.csv";
            writeSample(cfg.file);
            if (cfg.source.empty()) cfg.source = "N1";
            if (cfg.destination.empty()) cfg.destination = "N15";
        }

        Graph g = loadGraph(cfg.file, cfg.directed);
        Stats st = graphStats(g, cfg.directed);
        if (st.negative > 0) std::cerr << "Warning: negative edges found; Bellman-Ford recommended.\n";

        std::vector<QueryResult> results;
        if (!cfg.queries.empty()) {
            for (const auto& q : parseQueries(cfg.queries)) results.push_back(queryOne(g, q.first, q.second));
        } else if (cfg.all && !cfg.source.empty()) {
            auto d = dijkstra(g, cfg.source);
            for (const auto& [n, _] : g) {
                if (std::isfinite(d.dist[n])) {
                    auto p = buildPath(d.prev, cfg.source, n);
                    results.push_back({cfg.source, n, true, d.dist[n], p, static_cast<int>(p.size()) - 1, ""});
                } else {
                    results.push_back({cfg.source, n, false, 0, {}, 0, "No path"});
                }
            }
        } else {
            if (cfg.source.empty() || cfg.destination.empty()) throw std::runtime_error("--source and --destination are required unless --all or --queries is used");
            results.push_back(queryOne(g, cfg.source, cfg.destination));
        }

        for (const auto& r : results) {
            std::cout << formatResult(r, cfg.format) << "\n\n";
        }

        std::ofstream out(cfg.output);
        out << "{\n"
            << "  \"graphStats\": {\"totalNodes\": " << st.nodes << ", \"totalEdges\": " << st.edges << ", \"averageDegree\": " << st.avgDegree << ", \"connectedComponents\": " << st.components << ", \"density\": " << st.density << ", \"negativeEdges\": " << st.negative << "},\n"
            << "  \"results\": [\n";
        for (std::size_t i = 0; i < results.size(); ++i) {
            out << "    " << toJson(results[i]);
            if (i + 1 < results.size()) out << ",";
            out << "\n";
        }
        out << "  ]\n}\n";
    } catch (const std::exception& ex) {
        std::cerr << "Error: " << ex.what() << "\n";
        return 1;
    }
    return 0;
}