ShortestRouteBestFS.cpp

#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

struct RouteNode {
    string city;
    int heuristic;
    shared_ptr<RouteNode> parent;
};

struct CompareRouteNode {
    bool operator()(const shared_ptr<RouteNode>& a, const shared_ptr<RouteNode>& b) const {
        return a->heuristic > b->heuristic;
    }
};

map<string, vector<string>> graphRouteBest;
map<string, int> heuristicRouteBest;

void initializeGraphBest() {
    graphRouteBest["A"] = {"B", "C"};
    graphRouteBest["B"] = {"D", "E"};
    graphRouteBest["C"] = {"F"};
    graphRouteBest["D"] = {"G"};
    graphRouteBest["E"] = {"G"};
    graphRouteBest["F"] = {"G"};
    graphRouteBest["G"] = {};

    heuristicRouteBest["A"] = 6;
    heuristicRouteBest["B"] = 4;
    heuristicRouteBest["C"] = 3;
    heuristicRouteBest["D"] = 2;
    heuristicRouteBest["E"] = 2;
    heuristicRouteBest["F"] = 1;
    heuristicRouteBest["G"] = 0;
}

void printPathBest(shared_ptr<RouteNode> node) {
    vector<string> path;
    while (node) {
        path.push_back(node->city);
        node = node->parent;
    }
    reverse(path.begin(), path.end());
    cout << "Route:\n";
    for (size_t i = 0; i < path.size(); ++i) {
        cout << path[i];
        if (i + 1 < path.size()) cout << " -> ";
    }
    cout << '\n';
}

int main() {
    initializeGraphBest();
    cout << "Enter start city: ";
    string start;
    cin >> start;
    cout << "Enter destination city: ";
    string goal;
    cin >> goal;

    priority_queue<shared_ptr<RouteNode>, vector<shared_ptr<RouteNode>>, CompareRouteNode> open;
    set<string> closed;
    open.push(make_shared<RouteNode>(
        RouteNode{start, heuristicRouteBest.count(start) ? heuristicRouteBest[start] : INT_MAX, nullptr}
    ));

    while (!open.empty()) {
        auto node = open.top();
        open.pop();

        if (closed.count(node->city)) continue;
        closed.insert(node->city);

        if (node->city == goal) {
            printPathBest(node);
            return 0;
        }

        for (const auto& neighbor : graphRouteBest[node->city]) {
            if (!closed.count(neighbor)) {
                open.push(make_shared<RouteNode>(
                    RouteNode{neighbor, heuristicRouteBest.count(neighbor) ? heuristicRouteBest[neighbor] : INT_MAX, node}
                ));
            }
        }
    }

    cout << "No route found.\n";
    return 0;
}