src/library.cpp - master - forthang/path_delivery-forthang

src/library.cpp
73 строки2 KB
forthang
upd library.cpp
23 мар 2025, 23:15
23 мар 2025, 23:151dd961b
#include "graph.hpp"
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
#include <algorithm>
#include <stdexcept>

class Graph {
private:
    std::unordered_map<std::string, std::unordered_map<std::string, int>> graph;

public:
    void add_edge(const std::string& from, const std::string& to, int cost) {
        graph[from][to] = cost;
        graph[to][from] = cost;
    }

    std::vector<std::string> find_shortest_path(const std::string& start, const std::string& end) {
        if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
            throw std::invalid_argument("Start or end city not present in the graph");
        }

        const int INF = std::numeric_limits<int>::max();
        std::unordered_map<std::string, int> distances;
        std::unordered_map<std::string, std::string> previous;
        
        for (const auto& node : graph) {
            distances[node.first] = INF;
        }
        distances[start] = 0;

        using QueueElement = std::pair<int, std::string>;
        std::priority_queue<QueueElement, 
                          std::vector<QueueElement>, 
                          std::greater<QueueElement>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            auto [current_dist, current] = pq.top();
            pq.pop();

            if (current_dist > distances[current]) continue;
            if (current == end) break;

            for (const auto& [neighbor, cost] : graph[current]) {
                int new_dist = current_dist + cost;
                if (new_dist < distances[neighbor]) {
                    distances[neighbor] = new_dist;
                    previous[neighbor] = current;
                    pq.push({new_dist, neighbor});
                }
            }
        }

        if (distances[end] == INF) return {};

        std::vector<std::string> path;
        std::string current = end;
        
        while (current != start) {
            path.push_back(current);
            if (!previous.count(current)) return {};
            current = previous[current];
        }
        
        path.push_back(start);
        std::reverse(path.begin(), path.end());
        
        return path;
    }
};