如何实现Boost图可视化并运行Dijkstra最短路径算法

问题说明 #

需要基于Dijkstra最短路径算法构建可调整顶点数量的网格图，通过循环批量创建边，遇到两个异常点：

• dot文件生成无响应：执行std::ofstream dot_file("grid.dot"); boost::write_graphviz(dot_file, g);代码后，没有生成对应文件，也没有报错输出
• Dijkstra函数调用报错：执行dijkstra_shortest_paths(g, vtx_distance, predecessor_map(&p[0]).distance_map(&d[0]));时报编译或运行错误

原始代码 #

#include <stdint.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace std;
using namespace boost;

int main() {
    struct Vertex {int index;};
    struct Edge {int weight;};
    typedef adjacency_list<vecS, vecS, bidirectionalS, Vertex, Edge> Graph;
    Graph g;
    typedef graph_traits < Graph >::vertex_descriptor vertex_t;
    typedef graph_traits < Graph >::edge_descriptor edge_t;
    typedef graph_traits <Graph> Traits;


    vector<int> vertices; 
    int size = 9;
    int size_x = 3;
    int size_y = 3;
    for (int i = 0; i < size; i++){
        vertices.push_back(i);
    }
    vector<vertex_t> vtx;
    for (int i = 0; i<vertices.size(); i++) {
        vertex_t tmp = add_vertex(g);
        g[tmp].index = vertices.at(i);
        vtx.push_back(tmp); 
    }

 //Add edge in horizontal
    for (int i = 0; i<vertices.size(); i++){
        if (vertices[i] % size_x !=2){
            add_edge(vtx[i], vtx[i + 1], g);
        }
    }
 //Add edge in vertical
    for (int i = 0; i<vertices.size(); i++){
    if (vertices[i] < size - size_y){
        add_edge(vtx[i], vtx[i + size_x], g);
    }
}
//Add edge in diagonal 1
for (int i = 0; i<vertices.size(); i++){
    if (vertices[i] % size_x != 2 && vertices[i] < size - size_y){
        add_edge(vtx[i], vtx[i + 1 + size_x], g);
    }
}
//Add edge in diagonal 2
for (int i = 0; i<vertices.size(); i++){
    if (vertices[i] % size_x != 0 && vertices[i] < size - size_y){
        add_edge(vtx[i], vtx[i - 1 + size_x], g);
    }
}

vector<int> d(num_vertices(g));
vector<vertex_t> p(num_vertices(g));
vertex_t vtx_distance = vertex(0, g);

dijkstra_shortest_paths(g, vtx_distance, predecessor_map(&p[0]).distance_map(&d[0]));

std::cout << "distances and parents:" << std::endl;

std::ofstream dot_file("grid.dot");
boost::write_graphviz(dot_file, g);
}

修复方案 #

问题原因 #

1. dot文件不生成：未判断文件流是否成功打开，且文件流生命周期结束前未显式关闭，部分环境下会导致缓冲区内容未写入磁盘；同时默认write_graphviz不会输出自定义的顶点index属性，生成的dot文件可读性差。
2. Dijkstra调用报错：自定义Edge结构体包含weight属性，Dijkstra算法运行必须显式指定权重映射参数，且创建边时未给weight属性赋值，导致算法无法读取边权。

修复后完整代码 #

#include <stdint.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace std;
using namespace boost;

int main() {
    struct Vertex {int index;};
    struct Edge {int weight;};
    typedef adjacency_list<vecS, vecS, bidirectionalS, Vertex, Edge> Graph;
    Graph g;
    typedef graph_traits < Graph >::vertex_descriptor vertex_t;
    typedef graph_traits < Graph >::edge_descriptor edge_t;
    typedef graph_traits <Graph> Traits;


    vector<int> vertices; 
    int size = 9;
    int size_x = 3;
    int size_y = 3;
    for (int i = 0; i < size; i++){
        vertices.push_back(i);
    }
    vector<vertex_t> vtx;
    for (int i = 0; i<vertices.size(); i++) {
        vertex_t tmp = add_vertex(g);
        g[tmp].index = vertices.at(i);
        vtx.push_back(tmp); 
    }

    // 横向边
    for (int i = 0; i<vertices.size(); i++){
        if (vertices[i] % size_x !=2){
            add_edge(vtx[i], vtx[i + 1], Edge{1}, g);
        }
    }
    // 纵向边
    for (int i = 0; i<vertices.size(); i++){
        if (vertices[i] < size - size_y){
            add_edge(vtx[i], vtx[i + size_x], Edge{1}, g);
        }
    }
    // 右下斜向边
    for (int i = 0; i<vertices.size(); i++){
        if (vertices[i] % size_x != 2 && vertices[i] < size - size_y){
            add_edge(vtx[i], vtx[i + 1 + size_x], Edge{1}, g);
        }
    }
    // 左下斜向边
    for (int i = 0; i<vertices.size(); i++){
        if (vertices[i] % size_x != 0 && vertices[i] < size - size_y){
            add_edge(vtx[i], vtx[i - 1 + size_x], Edge{1}, g);
        }
    }

    vector<int> d(num_vertices(g));
    vector<vertex_t> p(num_vertices(g));
    vertex_t vtx_distance = vertex(0, g);

    // 显式传入权重映射
    dijkstra_shortest_paths(g, vtx_distance,
        predecessor_map(&p[0])
        .distance_map(&d[0])
        .weight_map(get(&Edge::weight, g)));

    std::cout << "distances and parents:" << std::endl;
    for (int i = 0; i < num_vertices(g); i++) {
        std::cout << "顶点" << i << "距离起点距离：" << d[i] << "，前驱顶点：" << p[i] << std::endl;
    }

    std::ofstream dot_file("grid.dot");
    if (dot_file.is_open()) {
        // 输出顶点index作为标签
        boost::write_graphviz(dot_file, g, 
            [&](std::ostream& out, vertex_t v) { 
                out << "[label=\"" << g[v].index << "\"]"; 
            });
        dot_file.close();
        std::cout << "grid.dot文件生成成功" << std::endl;
    } else {
        std::cerr << "grid.dot文件打开失败，请检查当前目录写入权限" << std::endl;
    }
    return 0;
}

修复后生成的dot文件对应的图为3x3的8方向网格图，符合预期结构。

内容的提问来源于stack exchange，提问作者Sally Go