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

Claude Code 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.22)
project(dijkstra_path_finder VERSION 1.0.0 LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

# ---------------------------------------------------------------------------
# Dependencies
# ---------------------------------------------------------------------------
# Boost.Graph 1.84.0 — Graph data structures and algorithms
# nlohmann/json 3.11.3 — Header-only JSON library
# ---------------------------------------------------------------------------

find_package(Boost 1.84.0 REQUIRED COMPONENTS graph)

include(FetchContent)

FetchContent_Declare(
    nlohmann_json
    GIT_REPOSITORY https://github.com/nlohmann/json.git
    GIT_TAG        v3.11.3
    GIT_SHALLOW    TRUE
)

set(JSON_BuildTests OFF CACHE BOOL "" FORCE)
set(JSON_Install OFF CACHE BOOL "" FORCE)

FetchContent_MakeAvailable(nlohmann_json)

# ---------------------------------------------------------------------------
# Executable
# ---------------------------------------------------------------------------

add_executable(dijkstra_path_finder main.cpp)

target_link_libraries(dijkstra_path_finder PRIVATE
    Boost::graph
    nlohmann_json::nlohmann_json
)

if(CMAKE_CXX_COMPILER_ID MATCHES "GNU|Clang")
    target_compile_options(dijkstra_path_finder PRIVATE -Wall -Wextra -Wpedantic)
endif()

/**
 * Dijkstra Shortest Path Finder - Trial 1 (Boost.Graph 1.84.0 + nlohmann/json 3.11.3)
 *
 * Finds shortest paths in weighted graphs using Dijkstra's algorithm with
 * priority queue optimization. Supports batch queries.
 */

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

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>

#include <nlohmann/json.hpp>

using json = nlohmann::json;

// ---------------------------------------------------------------------------
// Graph type definitions
// ---------------------------------------------------------------------------
struct EdgeWeight {
    double weight;
};

using Graph = boost::adjacency_list<
    boost::vecS, boost::vecS, boost::directedS,
    boost::no_property, EdgeWeight>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using Edge = boost::graph_traits<Graph>::edge_descriptor;

// ---------------------------------------------------------------------------
// DijkstraPathFinder
// ---------------------------------------------------------------------------
class DijkstraPathFinder {
public:
    DijkstraPathFinder() = default;

    void addEdge(const std::string& source, const std::string& target, double weight) {
        if (weight < 0) {
            throw std::invalid_argument("Edge weight must be non-negative, got " + std::to_string(weight));
        }
        Vertex u = getOrCreateVertex(source);
        Vertex v = getOrCreateVertex(target);
        boost::add_edge(u, v, EdgeWeight{weight}, graph_);
    }

    void addUndirectedEdge(const std::string& nodeA, const std::string& nodeB, double weight) {
        addEdge(nodeA, nodeB, weight);
        addEdge(nodeB, nodeA, weight);
    }

    void loadFromJson(const json& data) {
        bool directed = data.value("directed", true);

        if (data.contains("nodes")) {
            for (const auto& node : data["nodes"]) {
                std::string id = node.is_object() ? node["id"].get<std::string>() : node.get<std::string>();
                getOrCreateVertex(id);
            }
        }

        if (data.contains("edges")) {
            for (const auto& edge : data["edges"]) {
                std::string src = edge["source"].get<std::string>();
                std::string tgt = edge["target"].get<std::string>();
                double wt = edge["weight"].get<double>();
                if (directed) {
                    addEdge(src, tgt, wt);
                } else {
                    addUndirectedEdge(src, tgt, wt);
                }
            }
        }
    }

    void loadFromFile(const std::string& filepath) {
        std::ifstream in(filepath);
        if (!in) throw std::runtime_error("Cannot open file: " + filepath);
        json data;
        in >> data;
        loadFromJson(data);
    }

    struct DijkstraResult {
        std::map<std::string, double> distances;
        std::map<std::string, std::string> predecessors;
        double target_distance = std::numeric_limits<double>::infinity();
        std::vector<std::string> target_path;
        bool target_reachable = false;
    };

    DijkstraResult dijkstra(const std::string& source, const std::string& target = "") {
        if (name_to_vertex_.find(source) == name_to_vertex_.end()) {
            throw std::invalid_argument("Source node '" + source + "' not found in graph");
        }

        Vertex src = name_to_vertex_[source];
        int num_vertices = boost::num_vertices(graph_);

        std::vector<double> dist(num_vertices, std::numeric_limits<double>::infinity());
        std::vector<Vertex> pred(num_vertices);
        for (int i = 0; i < num_vertices; ++i) pred[i] = i;

        auto weight_map = boost::get(&EdgeWeight::weight, graph_);

        boost::dijkstra_shortest_paths(graph_, src,
            boost::distance_map(boost::make_iterator_property_map(dist.begin(),
                boost::get(boost::vertex_index, graph_)))
            .predecessor_map(boost::make_iterator_property_map(pred.begin(),
                boost::get(boost::vertex_index, graph_)))
            .weight_map(weight_map));

        DijkstraResult result;

        for (const auto& [name, vertex] : name_to_vertex_) {
            result.distances[name] = dist[vertex];
            if (pred[vertex] != vertex) {
                result.predecessors[name] = vertex_to_name_[pred[vertex]];
            } else if (name != source) {
                result.predecessors[name] = "";
            }
        }

        if (!target.empty() && name_to_vertex_.find(target) != name_to_vertex_.end()) {
            Vertex tgt = name_to_vertex_[target];
            result.target_distance = dist[tgt];
            result.target_path = reconstructPath(pred, src, tgt);
            result.target_reachable = (dist[tgt] < std::numeric_limits<double>::infinity());
        }

        return result;
    }

    struct BatchResult {
        std::string source;
        std::string target;
        double distance;
        std::vector<std::string> path;
        bool reachable;
    };

    std::vector<BatchResult> batchShortestPaths(
        const std::vector<std::pair<std::string, std::string>>& queries) {

        std::vector<BatchResult> results;
        std::map<std::string, DijkstraResult> cache;

        for (const auto& [source, target] : queries) {
            if (cache.find(source) == cache.end()) {
                cache[source] = dijkstra(source);
            }

            const auto& dr = cache[source];
            BatchResult br;
            br.source = source;
            br.target = target;
            auto it = dr.distances.find(target);
            br.distance = (it != dr.distances.end()) ? it->second : std::numeric_limits<double>::infinity();
            br.reachable = br.distance < std::numeric_limits<double>::infinity();

            if (br.reachable && name_to_vertex_.find(source) != name_to_vertex_.end()
                && name_to_vertex_.find(target) != name_to_vertex_.end()) {
                // Reconstruct path from dijkstra
                int num_vertices = boost::num_vertices(graph_);
                std::vector<double> dist(num_vertices, std::numeric_limits<double>::infinity());
                std::vector<Vertex> pred(num_vertices);
                for (int i = 0; i < num_vertices; ++i) pred[i] = i;

                auto weight_map = boost::get(&EdgeWeight::weight, graph_);
                Vertex src = name_to_vertex_[source];
                boost::dijkstra_shortest_paths(graph_, src,
                    boost::distance_map(boost::make_iterator_property_map(dist.begin(),
                        boost::get(boost::vertex_index, graph_)))
                    .predecessor_map(boost::make_iterator_property_map(pred.begin(),
                        boost::get(boost::vertex_index, graph_)))
                    .weight_map(weight_map));

                br.path = reconstructPath(pred, src, name_to_vertex_[target]);
            }

            results.push_back(br);
        }

        return results;
    }

    json getGraphStats() const {
        json stats;
        stats["num_nodes"] = boost::num_vertices(graph_);
        stats["num_edges"] = boost::num_edges(graph_);
        stats["is_directed"] = true;

        std::vector<std::string> nodeNames;
        for (const auto& [name, _] : name_to_vertex_) {
            nodeNames.push_back(name);
        }
        std::sort(nodeNames.begin(), nodeNames.end());
        stats["nodes"] = nodeNames;

        int v = boost::num_vertices(graph_);
        int e = boost::num_edges(graph_);
        double maxEdges = static_cast<double>(v) * (v - 1);
        double density = maxEdges > 0 ? e / maxEdges : 0.0;
        stats["density"] = std::round(density * 10000.0) / 10000.0;

        return stats;
    }

private:
    Graph graph_;
    std::map<std::string, Vertex> name_to_vertex_;
    std::map<Vertex, std::string> vertex_to_name_;

    Vertex getOrCreateVertex(const std::string& name) {
        auto it = name_to_vertex_.find(name);
        if (it != name_to_vertex_.end()) return it->second;
        Vertex v = boost::add_vertex(graph_);
        name_to_vertex_[name] = v;
        vertex_to_name_[v] = name;
        return v;
    }

    std::vector<std::string> reconstructPath(const std::vector<Vertex>& pred,
                                              Vertex source, Vertex target) {
        if (pred[target] == target && target != source) {
            return {};
        }

        std::vector<std::string> path;
        Vertex current = target;
        while (current != source) {
            path.push_back(vertex_to_name_[current]);
            if (pred[current] == current) return {};
            current = pred[current];
        }
        path.push_back(vertex_to_name_[source]);
        std::reverse(path.begin(), path.end());
        return path;
    }
};

// ---------------------------------------------------------------------------
// Sample graph
// ---------------------------------------------------------------------------
static json createSampleGraph() {
    return json{
        {"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
// ---------------------------------------------------------------------------
int main() {
    std::cout << std::string(60, '=') << "\n";
    std::cout << "  Dijkstra Shortest Path Finder (Boost.Graph + nlohmann/json)\n";
    std::cout << std::string(60, '=') << "\n";

    DijkstraPathFinder finder;
    finder.loadFromJson(createSampleGraph());

    // Graph stats
    json stats = finder.getGraphStats();
    std::cout << "\nGraph Statistics:\n";
    std::cout << "  Nodes: " << stats["num_nodes"] << "\n";
    std::cout << "  Edges: " << stats["num_edges"] << "\n";
    std::cout << "  Directed: " << std::boolalpha << stats["is_directed"].get<bool>() << "\n";
    std::cout << "  Density: " << stats["density"] << "\n";
    std::cout << "  Vertices: ";
    for (size_t i = 0; i < stats["nodes"].size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << stats["nodes"][i].get<std::string>();
    }
    std::cout << "\n";

    std::string sep(60, '-');

    // Single query
    std::cout << "\n" << sep << "\n";
    std::cout << "Single Query: A -> G\n";
    std::cout << sep << "\n";

    auto result = finder.dijkstra("A", "G");
    std::cout << "  Shortest distance: " << result.target_distance << "\n";
    if (!result.target_path.empty()) {
        std::cout << "  Path: ";
        for (size_t i = 0; i < result.target_path.size(); ++i) {
            if (i > 0) std::cout << " -> ";
            std::cout << result.target_path[i];
        }
        std::cout << "\n";
    } else {
        std::cout << "  Path: No path found\n";
    }

    // All distances from A
    std::cout << "\n" << sep << "\n";
    std::cout << "All Distances from A:\n";
    std::cout << sep << "\n";

    auto allResult = finder.dijkstra("A");
    for (const auto& [node, dist] : allResult.distances) {
        auto pathResult = finder.dijkstra("A", node);
        std::string pathStr;
        if (!pathResult.target_path.empty()) {
            for (size_t i = 0; i < pathResult.target_path.size(); ++i) {
                if (i > 0) pathStr += " -> ";
                pathStr += pathResult.target_path[i];
            }
        } else {
            pathStr = "N/A";
        }
        std::cout << "  A -> " << node << ": distance = " << std::setw(5) << std::fixed
                  << std::setprecision(0) << dist << ", path = " << pathStr << "\n";
    }

    // Batch queries
    std::cout << "\n" << sep << "\n";
    std::cout << "Batch Queries:\n";
    std::cout << sep << "\n";

    std::vector<std::pair<std::string, std::string>> queries = {
        {"A", "G"}, {"A", "F"}, {"B", "G"}, {"C", "F"}, {"D", "A"}, {"G", "A"}
    };

    auto batchResults = finder.batchShortestPaths(queries);
    for (const auto& r : batchResults) {
        std::string pathStr;
        if (!r.path.empty()) {
            for (size_t i = 0; i < r.path.size(); ++i) {
                if (i > 0) pathStr += " -> ";
                pathStr += r.path[i];
            }
        } else {
            pathStr = "No path";
        }
        std::string distStr = r.reachable ? std::to_string(static_cast<int>(r.distance)) : "unreachable";
        std::cout << "  " << r.source << " -> " << r.target << ": "
                  << std::setw(12) << distStr << "  |  " << pathStr << "\n";
    }

    // JSON output
    std::cout << "\n" << sep << "\n";
    std::cout << "JSON Output:\n";
    json output;
    output["graph_stats"] = stats;
    json batchArray = json::array();
    for (const auto& r : batchResults) {
        json obj;
        obj["source"] = r.source;
        obj["target"] = r.target;
        obj["distance"] = r.distance;
        obj["path"] = r.path;
        batchArray.push_back(obj);
    }
    output["batch_results"] = batchArray;
    std::cout << output.dump(2) << "\n";

    std::cout << "\nDone!\n";
    return 0;
}