Ошибка "выход за пределы массива"

[Шляпадляменя]

Задача: Реализовать метод ветвей и границ.
В строке if (LowerBound(G, VNext) < Length(G, BestPath)) выдает ошибку выход за пределы массива, как ее исправить?

double LowerBound(const Graph& G, const vector<int>&Visited) {
    vector<int>Q = G.get_vertices();
    double min,min2;
    double rez = 0;
    for (int i = 0; i< Visited.size()-1; i++) {
        rez += G.edge_weight(Visited[i], Visited[i + 1]);
    }
    for (int j = 0; j < Q.size(); j++) {
        min = INFINITY;
        vector<std::pair<int, double>> smeg;
        smeg=G.get_adjacent_edges(Q[j]);
        for (int k = 0; k < smeg.size(); k++) {
            if (smeg[k].second < min)
                min = smeg[k].second;   
        }
        rez += min;
        min2 = INFINITY;
        for (int k = 0; k < smeg.size(); k++) {
            if (smeg[k].second != min && smeg[k].second<min2)
                min2 = smeg[k].second;
        }
        rez += min2;
    }
    return rez / 2;
}


double Length(const Graph& G, const vector<int>& Path) {
    double rez = 0;
    for (int i = 0; i < Path.size() - 1; i++) {
        rez += G.edge_weight(Path[i], Path[i + 1]);

    }
    if (Path.size() >= 2)
        rez += G.edge_weight(Path[Path.size() - 1], Path[0]);
    return rez;
}

vector<int>MinPath(const Graph& G, const vector<int>&P1, const vector<int>&P2) {
    if (Length(G, P1) < Length(G, P2))
        return P1;
    else
        return P2;
}
vector<int> BnB(const Graph& G, vector<int>Visited, vector<int>BestPath) {
    vector<int> Path, VNext; int i;
    vector<int>Q = G.get_vertices();
    if (Q.size() == Visited.size())
        return MinPath(G, BestPath, Visited);
    for (int v = 0; v < Q.size(); v++) {
        for (i = 0; i < Visited.size(); i++)
            if (Q[v] == Visited[i])
                break;
        if (i == Visited.size())
            VNext.push_back(Q[v]);
        if (LowerBound(G, VNext) < Length(G, BestPath)) {
            Path = BnB(G, VNext, BestPath);
            BestPath = MinPath(G, BestPath, Path);
        }
    }
    return BestPath;
}
vector<int>TSP_BnB(const Graph& G, int start) {
   vector<int> BestPath; 
   vector<int> Visited = { start }; 
        return BnB(G, Visited, BestPath);
}

[Шляпадляменя]

весь код
graph.h

#include <map>
#include <vector>
#include <tuple>
#include <initializer_list>

/**
 * Non-oriented weighted graph.
**/
class Graph {
public:
    Graph() {}
    Graph(std::initializer_list<std::tuple<int, int, double>> edges);

    /// Add single vertex to the graph.
    void add_vertex(int vertex);

    /// Add vertices (if necessary) and an edge between them to the graph.
    void add_edge(int start_vertex, int end_vertex, double weight = 1.0);

    /// Return all vertices of the graph.
    std::vector<int> get_vertices() const;

    /// Return all adjacent by edges vertices for the specified vertex.
    std::vector<int> get_adjacent_vertices(int src_vertex) const;

    /// Get adjacent edges for the vertex as vector of (end vertex, edge weight).
    std::vector<std::pair<int, double>> get_adjacent_edges(int src_vertex) const;

    /// Return true if the vertex exists in the graph, false otherwise.
    bool has_vertex(int vertex) const;

    /// Return true if vertices exist and have an edge between them, false otherwise.
    bool has_edge(int start_vertex, int end_vertex) const;

    /// Return weight of an edge between vertices (if there is any), throw an exception otherwise.
    double edge_weight(int start_vertex, int end_vertex) const;

    /// Remove the vertex and all its adjacent edges from the graph.
    void remove_vertex(int vertex);

    /// Remove the edge from the graph (but not the vertices).
    void remove_edge(int start_vertex, int end_vertex);

private:
    std::map<int, std::map<int, double>> vertices;
}

graph.cpp

#include "graph.h"

#include <stdexcept>

using namespace std;

Graph::Graph(initializer_list<tuple<int, int, double>> edges) {
    for (const auto& e : edges) {
        add_edge(get<0>(e), get<1>(e), get<2>(e));
    }
}

void Graph::add_vertex(int vertex) {
    if (!has_vertex(vertex)) {
        vertices[vertex] = std::map<int, double>();
    }
}

void Graph::add_edge(int start_vertex, int end_vertex, double weight) {
    add_vertex(start_vertex);
    add_vertex(end_vertex);
    vertices[start_vertex][end_vertex] = weight;
    vertices[end_vertex][start_vertex] = weight;
}

std::vector<int> Graph::get_vertices() const {
    std::vector<int> result;
    for (const auto& p : vertices) {
        result.push_back(p.first);
    }
    return result;
}

std::vector<int> Graph::get_adjacent_vertices(int src_vertex) const {
    const auto it = vertices.find(src_vertex);
    if (it == vertices.end()) {
        return std::vector<int> {};
    }
    vector<int> result;
    for (const auto& p : it->second) {
        result.push_back(p.first);
    }
    return result;
}

vector<pair<int, double>> Graph::get_adjacent_edges(int src_vertex) const {
    const auto it = vertices.find(src_vertex);
    if (it == vertices.end()) {
        return vector<pair<int, double>> {};
    }
    vector<pair<int, double>> result;
    for (const auto& p : it->second) {
        result.push_back(make_pair(p.first, p.second));
    }
    return result;
}

bool Graph::has_vertex(int vertex) const {
    return (vertices.find(vertex) != vertices.end());
}

bool Graph::has_edge(int start_vertex, int end_vertex) const {
    const auto it = vertices.find(start_vertex);
    if (it == vertices.end()) {
        return false;
    }
    return (it->second.find(end_vertex) != it->second.end());
}

double Graph::edge_weight(int start_vertex, int end_vertex) const {
    const auto it_s = vertices.find(start_vertex);
    if (it_s == vertices.end()) {
        throw invalid_argument("Edge doesn't exist");
    }
    const auto it_e = it_s->second.find(end_vertex);
    if (it_e == it_s->second.end()) {
        throw invalid_argument("Edge doesn't exist");
    }
    return it_e->second;
}

void Graph::remove_vertex(int vertex) {
    /// Remove adjacent edges.
    auto adjacent_vertices = get_adjacent_vertices(vertex);
    for (const auto& adj_v : adjacent_vertices) {
        remove_edge(adj_v, vertex);
    }
    /// Remove the vertex itself.
    vertices.erase(vertex);
}

void Graph::remove_edge(int start_vertex, int end_vertex) {
    auto it_s = vertices.find(start_vertex);
    if (it_s != vertices.end()) {
        it_s->second.erase(end_vertex);
    }
    auto it_e = vertices.find(end_vertex);
    if (it_e != vertices.end()) {
        it_e->second.erase(start_vertex);
    }
}

tsp.h

#include "graph.h"
#include <vector>
std::vector<int> TSP_BnB(const Graph& G, int start);

test.cpp

#include "catch.hpp"

#include "tsp.h"

using namespace std;

// For a circilar path get its reverse.
vector<int> reversed(const vector<int>& path) {
    if (path.empty()) {
        return vector<int> {};
    }
    vector<int> result = { path[0] }; // first item is a start vertex
    result.insert(result.end(), path.rbegin(), path.rend()); // add vertices in reverse order
    result.pop_back(); // remove duplicated start vertex
    return result;
}

// From two possible directions for a circlular path choose one with min second vertex.
vector<int> min_dir(const vector<int>& path) {
    if (path.size() <= 1) {
        return path;
    }
    const auto reversed_path = reversed(path);
    return (path[1] <= reversed_path[1] ? path : reversed_path);
}

TEST_CASE("[TSP] Empty graph", "[tsp]") {
    Graph g{};
    CHECK(TSP_BnB(g,0) == vector<int> {});
}

TEST_CASE("[TSP] One edge", "[tsp]") {
    Graph g{ {0, 1, 2.5} };
    CHECK(TSP_BnB(g,0) == vector<int> {0, 1});
}


TEST_CASE("[TSP] Single vertex", "[tsp]") {
    Graph g{};
    g.add_vertex(0);
    CHECK(TSP_BnB(g, 0) == vector<int> {});
}


TEST_CASE("[TSP] Three vertices, three edges", "[tsp]") {
    Graph g{ {0, 1, 2.5}, {0, 2, 0.5}, {1, 2, 1.0} };
    const auto result = TSP_BnB(g,0);
    const auto expected = vector<int>{ 0, 1, 2 };
    CHECK(min_dir(result) == expected);
}

TEST_CASE("[TSP] Several vertices", "[tsp]") {
    Graph g{ {0, 1, 6.0}, {0, 2, 4.0}, {0, 3, 1.0},
             {1, 2, 3.5}, {1, 3, 2.0},
             {2, 3, 5.0} };
    const auto result = TSP_BnB(g,0);
    const auto expected = vector<int>{ 0, 2, 1, 3 };
    CHECK(min_dir(result) == expected);
}

TEST_CASE("[TSP] Many vertices", "[tsp]") {
    Graph g{ {0, 1, 2.0}, {0, 2, 4.0}, {0, 3, 1.0}, {0, 4, 2.5},
             {1, 2, 3.6}, {1, 3, 6.0}, {1, 4, 3.0},
             {2, 3, 7.0}, {2, 4, 5.0},
             {3, 4, 9.0} };
    const auto result = TSP_BnB(g,0);
    const auto expected = vector<int>{ 0, 3, 2, 1, 4 };
    CHECK(min_dir(result) == expected);
}

TEST_CASE("[TSP] Unreachable vertex", "[tsp]") {
    Graph g{ {0, 1, 2.5}, {1, 2, 1.0}, {0, 2, 1.0}, {3, 4, 0.7} };
    CHECK(TSP_BnB(g,0) == vector<int> {});
    CHECK(TSP_BnB(g,0) == vector<int> {});
}

TEST_CASE("[TSP] No looped path", "[tsp]") {
    Graph g{ {0, 1, 2.5}, {0, 2, 1.0}, {2, 3, 7.0} };
    CHECK(TSP_BnB(g,0) == vector<int> {});
    CHECK(TSP_BnB(g,0) == vector<int> {});
}

main.cpp

#define CATCH_CONFIG_RUNNER

#include "catch.hpp"
#include <ctime>
#include <chrono>
#include <iostream>
using namespace std;

#include "tsp.h"

int main(int argc, char* argv[]) {
    int result = Catch::Session().run(argc, argv);
    return result;
}

[Пётр Седов]

Сообщение от Шляпадляменя

    for (int i = 0; i< Visited.size()-1; i++) {

Сообщение от Шляпадляменя

    for (int i = 0; i < Path.size() - 1; i++) {

Так лучше не писать, потому что тут получается беззнаковая арифметика (метод std::vector::size возвращает значение типа size_t, а это беззнаковый тип).

#include <assert.h>
#include <limits.h>
#include <vector>

using namespace std;

int main() {
  vector<int> v;
  assert(v.size() == 0);
  if (sizeof(size_t) * CHAR_BIT == 32) { // если 32-битная платформа
    assert(v.size() - 1 == 4294967295u); // потому что беззнаковая арифметика по модулю pow(2, 32)
  }
  return 0;
}

Это грабли C++, унаследованные от C. Может быть из-за этого выходим за рамки массива. Лучше приводить к типу int, чтобы была знаковая арифметика:

for (int i = 0; i < static_cast<int>(Visited.size()) - 1; i++) {

for (int i = 0; i < static_cast<int>(Path.size()) - 1; i++) {