如何在 boost dijkstra_shortest_paths 中指定打破平局的逻辑 (dijkstra)

Question

这个 SO question 中很好地解释了我的问题的背景 Is Dijkstra's algorithm deterministic?

具体来说，@Wyck 的回答说明了我想要解决的用例。图片由@Wyck提供

我的要求是，当被要求生成从 0 到 5 的路径时，boost 的 dijkstra_shortest_paths（基于提供的图表）始终生成：0->1->5，因为打破平局的逻辑应使用节点 ID 的最小总和。

Answer 1

因此，由于缺少代码，这里是使用 BGL 编码的示例：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>

struct VertexProps { };
struct EdgeProps { double weight = 1; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                    VertexProps, EdgeProps>;
using V = Graph::vertex_descriptor;
using E = Graph::edge_descriptor;

Graph make_graph();

int main() {
    auto g = make_graph();
    //write_graphviz(std::cout, g);

    std::vector<V> predecessors(num_vertices(g));
    boost::dijkstra_shortest_paths(g, 0,
                                   boost::weight_map(get(&EdgeProps::weight, g))
                                       .predecessor_map(predecessors.data()));

    std::cout << "Path: ";
    for (V v = 5; ; v = predecessors[v]) {
        std::cout << " " << v;
        if (v == predecessors[v])
            break;
    }
}

Graph make_graph() {
    // sample from 
    Graph g;
    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(0, 3, g);
    add_edge(0, 4, g);
    add_edge(1, 5, g);
    add_edge(2, 5, g);
    add_edge(3, 5, g);
    add_edge(4, 5, g);

    return g;
}

打印

Path:  5 1 0

但是如果我们颠倒添加边的顺序：

Graph make_graph() {
    Graph g;
    add_edge(4, 5, g);
    add_edge(3, 5, g);
    add_edge(2, 5, g);
    add_edge(1, 5, g);
    add_edge(0, 4, g);
    add_edge(0, 3, g);
    add_edge(0, 2, g);
    add_edge(0, 1, g);

    return g;
}

它现在打印 Live

Path:  5 1 0

看来图模型决定了考试顺序。让我们通过使用有序容器选择器（如 setS）来固定边缘存储：

using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS,
                                    VertexProps, EdgeProps>;

现在我们可以有一个随机的插入顺序：

#include <random>
#include <algorithm>
Graph make_graph() {
    // sample from 
    using namespace std;
    vector ee{pair{0, 1}, {0, 2}, {0, 3}, {0, 4},
              {1, 5},     {2, 5}, {3, 5}, {4, 5}};
    shuffle(ee.begin(), ee.end(), mt19937{random_device{}()});

    Graph g;
    for (auto [s, t] : ee)
        add_edge(s, t, g);

    return g;
}

并且仍然总是得到 (Live):

Path:  5 1 0

验证解决方案！

未经测试的代码已损坏。让我们开始工作吧：

Graph make_graph() {
    vector ee{
        tuple //
        {0, 1, 1.0},
        {0, 2, 1},
        {0, 3, 1},
        {0, 4, 1},
        {1, 5, 2.0},
        {2, 5, 1},
        {3, 5, 1},
        {4, 5, 1},
    };
    // shuffle(ee.begin(), ee.end(), mt19937{random_device{}()});

    Graph g;
    for (auto [s, t, w] : ee)
        add_edge(s, t, EdgeProps{w}, g);

    return g;
}

请注意我们是如何单独增加 1 -> 5 边的权重的。现在我们得到 Live

Path:  5 4 0

太棒了...我们预计这里是 5 2 0。我决定录制一个BFS搜索实际进度的动画：Code On Coliru:¹

现在很明显，中间队列有利于以后的发现。我们需要调整优先级比较。

自定义权重类型

让我们尝试使用自定义 Weight 类型而不是 double:

来破解它

struct Weight {
    double magnitude = 0;

    bool operator<(Weight const& rhs) const { return magnitude < rhs.magnitude; }
    bool operator==(Weight const& rhs) const { return magnitude == rhs.magnitude; }
    bool operator!=(Weight const& rhs) const { return magnitude != rhs.magnitude; }
    Weight operator+(Weight const& rhs) const {
        return {magnitude + rhs.magnitude};
    }
    friend std::ostream& operator<<(std::ostream& os, Weight const& w) {
        return os << w.magnitude;
    }
    static Weight Inf() { return {std::numeric_limits<double>::infinity()}; }
};

比照，这仍然有效：Live On Coliru.

当然，现在的挑战变成了将“累积节点 ID 总和”包含在等式中：

struct Weight {
    double magnitude = 0;
    size_t cumulative_node_id_sum = 0;

    auto both() const { return std::tie(magnitude, cumulative_node_id_sum); }

    bool operator<(Weight const& rhs) const { return both() < rhs.both(); }
    bool operator==(Weight const& rhs) const { return both() == rhs.both(); }
    bool operator!=(Weight const& rhs) const { return both() != rhs.both(); }
    Weight operator+(Weight const& rhs) const {
        return Weight{magnitude + rhs.magnitude,
                      cumulative_node_id_sum + rhs.cumulative_node_id_sum};
    }
    friend std::ostream& operator<<(std::ostream& os, Weight const& w) {
        return os << w.magnitude;
    }
    static Weight Inf() {
        return Weight{std::numeric_limits<double>::infinity(), 0};
    }
};

还是一样（直播）。为什么？因为没有初始权重实际上知道节点id：

让我们在 make_graph:

中初始化

for (auto e : boost::make_iterator_range(edges(g))) {
    g[e].weight.cumulative_node_id_sum = target(e, g);
}

这会将初始节点 ID 总和设置为每条边的目标的顶点 ID。有了它，一切都顺畅了：

确实路径回到了期望的路径：

Path:  5 2 0

Simplify/Cleanup

有了这些理解，我们可能可以对该诊断代码进行抽脂。我们施展了一点魔法，所以 default expression for distance_inf 起作用了：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
using namespace std::literals;

using Traits = boost::adjacency_list_traits<boost::setS, boost::vecS, boost::directedS>;
using V      = Traits::vertex_descriptor;
using E      = Traits::edge_descriptor;

struct Weight {
    double magnitude              = 0;
    size_t cumulative_node_id_sum = 0;

    Weight(double magnitude = 0, size_t cumulative_node_id_sum = 0)
        : magnitude(magnitude)
        , cumulative_node_id_sum(cumulative_node_id_sum)
    { }

  private:
    auto both() const { return std::tie(magnitude, cumulative_node_id_sum); }

  public:
    bool   operator<(Weight const& rhs) const { return both() < rhs.both(); }
    bool   operator==(Weight const& rhs) const { return both() == rhs.both(); }
    bool   operator!=(Weight const& rhs) const { return both() != rhs.both(); }
    Weight operator+(Weight const& rhs) const {
        return Weight{magnitude + rhs.magnitude,
                      cumulative_node_id_sum + rhs.cumulative_node_id_sum};
    }
};

namespace std {
    template <> struct numeric_limits<Weight> : numeric_limits<double> {
    };
} // namespace std

struct EdgeProps {
    Weight weight;
};

using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS,
                                    boost::no_property, EdgeProps>;

Graph make_graph();

int main()
{
    auto g = make_graph();

    std::vector<V> predecessors(num_vertices(g));
    boost::dijkstra_shortest_paths( //
        g, 0,
        boost::predecessor_map(predecessors.data())
            .weight_map(get(&EdgeProps::weight, g)));

    std::cout << "Path: ";
    for (V v = 5;; v = predecessors[v]) {
        std::cout << " " << v;
        if (v == predecessors[v])
            break;
    }
    std::cout << "\n";
}

#include <random>
#include <algorithm>
Graph make_graph()
{
    // sample from
    // 
    using namespace std;
    vector ee{
        tuple //
        {0, 1, 1.0},
        {0, 2, 1},
        {0, 3, 1},
        {0, 4, 1},
        {1, 5, 2.0},
        {2, 5, 1},
        {3, 5, 1},
        {4, 5, 1},
    };
    shuffle(ee.begin(), ee.end(), mt19937{random_device{}()});

    Graph g;
    for (auto [s, t, w] : ee)
        add_edge(s, t, EdgeProps{w}, g);

    for (auto e : boost::make_iterator_range(edges(g))) {
        g[e].weight.cumulative_node_id_sum = target(e, g);
    }

    return g;
}

打印信任

Path:  5 2 0

¹ 使用 gifsicle -l -O9 -k32 -d 100 frame{0..31}.gif > test.gif

组合的图像

如何在 boost dijkstra_shortest_paths 中指定打破平局的逻辑 (dijkstra)

How to specify tie-breaking logic in boost dijkstra_shortest_paths (dijkstra)

boost

验证解决方案！

自定义权重类型

Simplify/Cleanup