c++ - Boost Dijkstra 代码导致段内存损坏？

Question

我正在尝试使用 boost dijkstra 算法在图中找到最短路径。

std::pair<c_vertex_iterator_t, c_vertex_iterator_t> vi;
std::pair<c_vertex_iterator_t, c_vertex_iterator_t> vj;

boost::property_map<ConGraph,boost::edge_weight_t>::type weightmap = get(boost::edge_weight, cg);
std::vector<c_vertex_t> p(num_vertices(cg));
std::vector<int> d(num_vertices(cg));
for (vi = vertices(cg); vi.first != vi.second; ++vi.first)
{
    boost::dijkstra_shortest_paths(cg, *vi.first,
           predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, cg))).
           distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, cg))));
    for (vj = vertices(cg); vj.first != vj.second; ++vj.first)
    {
        distMat[*vi.first][*vj.first]= d[*vj.first];
    }
}

return boost::num_vertices(cg);

但是我在这段代码中遇到了问题；应用程序在此行停止运行:

distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, cg))));

visual c++ 检测到由该指令引起的损坏的内存段错误

retval = HeapFree(_crtheap, 0, pBlock);

我应该怎么做才能解决这个问题？

Answer 1

我支持 @1201ProgramAlarm:为 distMat 安全分配内存表明代码几乎没有真正的问题:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dag_shortest_paths.hpp>

using ConGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
      boost::no_property, boost::property<boost::edge_weight_t, int> >;

using c_vertex_iterator_t = ConGraph::vertex_iterator;
using c_vertex_t = ConGraph::vertex_descriptor;

template <typename Matrix>
int foo(ConGraph& cg, Matrix& distMat) {
    std::pair<c_vertex_iterator_t, c_vertex_iterator_t> vi;
    std::pair<c_vertex_iterator_t, c_vertex_iterator_t> vj;

    boost::property_map<ConGraph,boost::edge_weight_t>::type weightmap = get(boost::edge_weight, cg);

    std::vector<c_vertex_t> p(num_vertices(cg));
    std::vector<int> d(num_vertices(cg));

    for (vi = vertices(cg); vi.first != vi.second; ++vi.first)
    {
        boost::dijkstra_shortest_paths(cg, *vi.first,
                predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, cg))).
                distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, cg))).
                weight_map(weightmap)
            );

        for (vj = vertices(cg); vj.first != vj.second; ++vj.first) {
            distMat[*vi.first][*vj.first] = d[*vj.first];
        }
    }

    return boost::num_vertices(cg);
}

#include <boost/graph/graph_utility.hpp>
#include <boost/graph/random.hpp>
#include <iomanip>
#include <random>

int main() {
    ConGraph g;

    {
        std::mt19937 rng { std::random_device{}() };
        std::uniform_int_distribution<int> wdist(1,10);

        generate_random_graph(g, 20, 40, rng);

        auto weightmap = get(boost::edge_weight, g);
        for (auto ed : boost::make_iterator_range(edges(g)))
            put(weightmap, ed, wdist(rng));
    }

    print_graph(g);

    std::vector<std::vector<int> > mat(num_vertices(g), std::vector<int>(num_vertices(g)));

    std::cout << "foo(g, mat): " << foo(g, mat) << "\n";

    for (auto& row : mat) {
        for (auto i : row) {
            if (i == std::numeric_limits<int>::max())
                std::cout << "## ";
            else
                std::cout << std::setw(2) << i << " ";
        }
        std::cout << "\n";
    }
}

打印(例如，随机生成的图形):

0 --> 2 16 
1 --> 11 5 
2 --> 8 10 17 10 
3 --> 13 16 16 
4 --> 
5 --> 16 
6 --> 
7 --> 19 3 9 18 
8 --> 10 
9 --> 13 
10 --> 6 
11 --> 4 4 16 19 
12 --> 11 3 1 1 11 
13 --> 10 5 
14 --> 10 1 
15 --> 1 13 
16 --> 8 
17 --> 15 2 
18 --> 4 
19 --> 0 9 
foo(g, mat): 20
 0 23  9 ## 27 29 20 ## 12 35 17 26 ## 26 ## 19  2 15 ## 31 
13  0 22 ##  4  6 30 ## 21 12 27  3 ## 20 ## 32 11 28 ##  8 
27 14  0 ## 18 20 11 ## 10 26  8 17 ## 17 ## 10 25  6 ## 22 
## ## ##  0 ##  6 15 ## 16 ## 12 ## ##  2 ## ##  6 ## ## ## 
## ## ## ##  0 ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## 
## ## ## ## ##  0 24 ## 15 ## 21 ## ## ## ## ##  5 ## ## ## 
## ## ## ## ## ##  0 ## ## ## ## ## ## ## ## ## ## ## ## ## 
 8 31 17  8  5 14 23  0 20  2 20 34 ## 10 ## 27 10 23  1  3 
## ## ## ## ## ##  9 ##  0 ##  6 ## ## ## ## ## ## ## ## ## 
## ## ## ## ## 12 21 ## 27  0 18 ## ##  8 ## ## 17 ## ## ## 
## ## ## ## ## ##  3 ## ## ##  0 ## ## ## ## ## ## ## ## ## 
10 33 19 ##  1 21 28 ## 19  9 25  0 ## 17 ## 29  9 25 ##  5 
18  5 27  3  9  9 18 ## 19 17 15  8  0  5 ## 37  9 33 ## 13 
## ## ## ## ##  4 13 ## 19 ## 10 ## ##  0 ## ##  9 ## ## ## 
21  8 30 ## 12 14  7 ## 29 20  4 11 ## 28  0 40 19 36 ## 16 
17  4 26 ##  8 10 20 ## 25 16 17  7 ##  7 ##  0 15 32 ## 12 
## ## ## ## ## ## 19 ## 10 ## 16 ## ## ## ## ##  0 ## ## ## 
21  8  3 ## 12 14 14 ## 13 20 11 11 ## 11 ##  4 19  0 ## 16 
## ## ## ##  4 ## ## ## ## ## ## ## ## ## ## ## ## ##  0 ## 
 5 28 14 ## 32 16 25 ## 17  4 22 31 ## 12 ## 24  7 20 ##  0