Алгоритм Дейкстры

vector<int>BuildPath(map<int, int>  Parent, int s, int e) {
    vector<int> result;
    int i;
    i = e;
    result.push_back(e);
    while (i != s) {
        result.push_back(Parent[i]);
        i = Parent[i];
       
    }
    result.push_back(s);
    for (int i = 0; i < result.size() / 2; i++) {
        int k;
        k = result[i];
        result[i] = result[result.size() - 1 - i];
        k = result[result.size() - 1 - i];
    }
    return result;
}
 
vector<int> shortest_path(const Graph& graph, int start_vertex, int end_vertex) {
    set<int> Vertices; //мн-во вершин
    map<int, double> Distance;
    map<int, int>  Parent;
    vector<int>Q, V;
    int u;
    for (int v = 0; v < graph.get_vertices().size(); v++) {
        Distance[v] = INFINITY;
 
    }
    Distance[start_vertex] = 0;
    Q = graph.get_vertices();
    vector <int>::iterator it, it_min;
    while (!Q.empty()) {
        int i;
        double min = Distance[Q[0]];
        it_min = Q.begin();
        for (it = Q.begin() + 1; it != Q.end(); it++) {
            if (Distance[*it] < min) {
                min = Distance[*it];
                it_min = it;
            }
        }
        u = *it_min;
        Q.erase(it_min);
        if (u == end_vertex)
            return BuildPath(Parent, start_vertex, end_vertex);
        V = graph.get_adjacent_vertices(u);
        for (int i = 0; i < V.size(); i++) {
            if (Distance[V[i]] > min + graph.edge_weight(u, V[i])) {
                Distance[V[i]] = min + graph.edge_weight(u, V[i]);
                Parent[V[i]] = u;
            }
        }
 
    }
    return vector<int> {};
}

    static void graph2file(const std::vector<Node>& g, id_t id)
    {
        const auto& WEY = g[id].mem;
 
        std::string STYLE_NODE_WEYS =
            "   node [\n"
            "       shape = circle\n"
            "       width = 0.8\n"
            "       color=\"#00000088\"\n"
            "       style = filled\n"
            "       fontname=\"Helvetica,Arial,sans-serif\"\n"
            "   ]\n\n";
 
        for(const auto& i : WEY)
        {
            STYLE_NODE_WEYS += "    "
                            + std::to_string(i)
                            + "[fillcolor = red fontcolor = white];\n";
        }
 
 
        std::ofstream f("g_way.txt");
                      f << "// sid for rand: "
                        << std::to_string(rrand.sid)
                        << "\n\ndigraph  {\n"
                        << "    rankdir=LR;\n\n"
                        << STYLE_NODE_WEYS << '\n';
 
        std::set<std::string> hash =  g[id].get_hash();
 
        auto is_exist = [&](auto a, auto b) ->bool
        {   auto aa  = std::to_string(a) ;
            auto bb  = std::to_string(b);
                 aa += "-" + bb;
            return hash.find(aa) != hash.end();
        };
 
        for(auto& e : g)
        {
            const std::string ID = std::to_string(e.id);
 
            for(auto& to : e.to)
            {
                std::string W = "\"" + toString(to.weight) + "\"";
 
                f << "    "
                  << std::setw(2) << ID << " -> "
                  << std::setw(2) << std::to_string(to.id)
                  << "[label="  << std::setw(7) << W
                  << ",weight=" << std::setw(7) << W << "]"
                  << (is_exist(e.id, to.id) ? "[color = red]" : "")
                  << ";\n";
            }
        }
        f   << "\n    c [label=\"© 2022 XLAT\" fontsize=12 shape=plain "
            << "style=\"\" fontcolor=green]\n";
        f   << "}\n";
    }