c++ - dijkstra 的恒权最短路径算法

Question

如何应用 Dijkstra 算法找到仅考虑具有特定权重值的节点的最小路径？

typedef property < vertex_index1_t, int > VertexProperty; 
    typedef property < edge_weight_t, float > EdgeProperty; 

    typedef adjacency_list < listS, vecS, undirectedS,
        VertexProperty, EdgeProperty > graph_t;
    typedef graph_traits < graph_t >::vertex_descriptor vertex;
    typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
    typedef std::pair<int, int> Edge;

我考虑了具有起始和到达像素的图像

    // load image
    cv::Mat image = cv::imread("/Images/image_crop.tif", CV_LOAD_IMAGE_GRAYSCALE); 
    // start
    pos_x[0] = 26;
    pos_y[0] = 45;
    // finish
    pos_x[1] = 15;
    pos_y[1] = 60;

我输入感兴趣的参数

    float c = 0.5; // constant to move
    std::list<float> weights; // list of weights of an image
    std::list<Edge> edge_array; // list of edge of an image
    std::vector<float> vertici; // vector of vertex of an image 

我去插入顶点、权重并建立像素连接

    for(int x=0; x<width; x++)
        for(int y=0; y<height; y++)
            vertici.push_back( float(y*width+x) );

    for(int x=0; x<width; x++)
    {
        for(int y=0; y<height; y++)
        {
            for(int i=-1; i<2; i++)
            {
                for(int j=-1; j<2; j++)
                {
                    // color difference
                    weights.push_back(std::fabs(image.at<unsigned char>(y,x)/255.0f - image.at<unsigned char>(y+i, x+j)/255.0f) + c); 

                    // connections between adjacent pixels
                    edge_array.push_back( Edge( (y*width+x), ((y+i)*width+x+j)) ); 
                }
            }
        }
    }

我创建相关图

    graph_t g(edge_array.begin(), edge_array.end(), weights.begin(), num_nodes); // create the graph
    property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
    std::vector<vertex> p(num_vertices(g)); // to store parents
    std::vector<float> d(num_vertices(g)); // to store distance

Dijkstra 从这里开始

    dijkstra_shortest_paths(g, (pos_y[0]*width+pos_x[0]), 
    predecessor_map(&p[0]).distance_map(&d[0]).weight_map(get(edge_weight, g))); // I have to be able to consider only weights = 0.5

    typedef std::vector<graph_t::edge_descriptor> PathType;
    PathType percorso;
    vertex v = (pos_y[1]*width+pos_x[1]); // point of arrival

    for(vertex u = p[v]; u != v; v = u, u = p[v])
    {
        std::pair<graph_t::edge_descriptor, bool> edgePair = edge(u, v, g);
        graph_t::edge_descriptor edge = edgePair.first;
        percorso.push_back( edge );
    }

    std::cout << "Shortest path from starting position to arrival position:" << std::endl;
    for(PathType::reverse_iterator pathIterator = percorso.rbegin(); pathIterator != percorso.rend(); ++pathIterator)
    {
        std::cout << vertici[source(*pathIterator, g)] << " -> " << vertici[target(*pathIterator, g)]
        << " = " << get( edge_weight, g, *pathIterator ) << std::endl;      
    }

Answer 1

改为使用广度优先搜索。

如果您坚持，也可以使用常量权重图。

auto weight_map = boost::make_constant_property<EdgeDesc>(1.0);

参见 Boost graph: dijkstra_shortest_paths: cannot form a reference to 'void'