如何在boost的dijkstra_shortest_paths中指定路径平局判定逻辑

云原生阿岚

2026-9-30

Boost Dijkstra最短路径自定义平局规则实现方案

核心原理：默认dijkstra_shortest_paths仅以路径总权重作为优先级判定依据，同权重下的路径选择无确定性，我们需要将节点ID总和作为二次判定规则嵌入优先级比较逻辑，实现同权重下优先选择节点ID总和最小的路径。
具体实现步骤：

定义自定义距离结构体，同时存储路径总权重和对应节点ID总和，重载比较和加法运算符适配算法逻辑：

#include <boost/graph/dijkstra_shortest_paths.hpp>

// 自定义距离类型，集成权重和节点ID总和两个判定维度
struct PriorityWeight {
    double path_weight; // 原始路径总权重
    size_t node_sum;    // 路径包含的所有节点ID总和

    // 优先级比较规则：先比路径权重，权重相等时比节点ID总和
    bool operator<(const PriorityWeight& other) const {
        if (path_weight != other.path_weight) {
            return path_weight < other.path_weight;
        }
        return node_sum < other.node_sum;
    }

    // 扩展边时的距离计算规则
    PriorityWeight operator+(double edge_weight, size_t next_node_id) const {
        return {
            path_weight + edge_weight,
            node_sum + next_node_id
        };
    }
};

// 自定义距离比较器，适配Boost算法接口
struct PriorityWeightCompare {
    bool operator()(const PriorityWeight& a, const PriorityWeight& b) const {
        return b < a; // Boost优先级队列默认是大顶堆，反转比较实现小顶堆
    }
};