第一回 グラフ王 決定戦

dijkstra_shortest_paths での比較

Stanford GraphBase と boost::adjacency_list, boost::vector_as_graph を利用した std::vector によるグラフで boost::dijkstra_shortest_paths の実行時間を 適当に 比較してみました. boost::adjacency_list は節点と枝を保持するデータ構造に選択肢が複数あるので, vecS と listS の4通りの組み合わせで計測しました．

以下が計測結果です. 単位はナノ秒, 試行回数は100,000回です. 最適化オプションはO3です. また，計測に使用したグラフは Stanford GraphBase のページ にある knight3.gb を使用しました．

Average:
  SGB:              5209.81
  v=vecS,e=vecS:    3698.48
  v=vecS,e=listS:   4141.79
  v=listS,e=vecS::  6560.22
  v=listS,e=listS:  6675.47
  vector:           3560.44
Max:
  SGB:              64000
  v=vecS,e=vecS:    76000
  v=vecS,e=listS:   115000
  v=listS,e=vecS::  40000
  v=listS,e=listS:  20000
  vector:           18000
Min:
  SGB:              4000
  v=vecS,e=vecS:    3000
  v=vecS,e=listS:   3000
  v=listS,e=vecS::  6000
  v=listS,e=listS:  6000
  vector:           3000

平均値を見てみると, 節点に vecS を指定した boost::adjacency_list はなかなか良い結果を出しています.

また, std::vector<list<size_t>> で表される vector グラフも同等の良い結果が出ています. 専用のグラフクラスを定義しなくても std::vector で大抵は事足りると考えられます. ちなみに, vector グラフの枝の重みのプロパティマップには std::unorderd_map を使用しました.

C 言語実装である SGB(Stanford GraphBase) はこれらより少し遅い結果になりました.

そして最後に, 節点に listS を指定した boost::adjacency_list が最も遅いという結果に今回はなりました. dijkstra_shortest_paths は開始時に節点を総なめしているので, それをしない dijkstra_shortest_paths_no_color_map を使用すると結果は変わってくるかもしれません.

最大値に関しては測定するごとにかなりばらつきがあるので何とも言えません.

計測用のコード

#include <array>
#include <chrono>
#include <iostream>
#include <unordered_map>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/algorithm/max_element.hpp>
#include <boost/range/algorithm/min_element.hpp>
#include <boost/range/numeric.hpp>
#include <boost/graph/stanford_graph.hpp>
#undef ap
#undef upi
#undef abbr
#undef nickname
#undef conference
#undef HOME
#undef NEUTRAL
#undef AWAY
#undef venue
#undef date
#include <boost/functional/hash/hash.hpp>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

int main()
{
    using namespace boost;
    sgb_graph_ptr sgb_graph = restore_graph(const_cast<char*>("knight3.gb"));

    using result_type = std::array<uint64_t, 100000>;
    {
        dijkstra_shortest_paths(sgb_graph, *vertices(sgb_graph).first
                , weight_map(get(edge_length_t{}, sgb_graph))
                . distance_inf(std::numeric_limits<long>::max()));
    }
    auto sgb_result = result_type{};
    for (auto& result : sgb_result)
    {
        auto const start = std::chrono::system_clock::now();
        dijkstra_shortest_paths(sgb_graph, *vertices(sgb_graph).first
                , weight_map(get(edge_length_t{}, sgb_graph))
                . distance_inf(std::numeric_limits<long>::max()));
        auto const end = std::chrono::system_clock::now();
        result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    }

    auto vecSvecS_result = result_type{};
    {
        using BoostGraph = adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : vecSvecS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto vecSlistS_result = result_type{};
    {
        using BoostGraph = adjacency_list<listS, vecS, directedS, no_property, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : vecSlistS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto listSvecS_result = result_type{};
    {
        using BoostGraph = adjacency_list<vecS, listS, directedS, property<vertex_index_t, size_t>, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                    put(vertex_index, boost_graph, boost_v, get(get(vertex_index, sgb_graph), sgb_v));
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : listSvecS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto listSlistS_result = result_type{};
    {
        using BoostGraph = adjacency_list<listS, listS, directedS, property<vertex_index_t, size_t>, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                    put(vertex_index, boost_graph, boost_v, get(get(vertex_index, sgb_graph), sgb_v));
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : listSlistS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto vector_result = result_type{};
    {
        using VectorGraph = std::vector<std::list<size_t>>;
        auto vector_graph = VectorGraph{};
        using edge_descriptor = graph_traits<VectorGraph>::edge_descriptor;
        auto wmap = std::unordered_map<edge_descriptor, long, boost::hash<edge_descriptor>>{};
        copy_graph(sgb_graph, vector_graph
                , vertex_copy([&](auto, auto){
                })
                . edge_copy([&](auto sgb_e, auto& vector_e){
                    wmap[vector_e] = get(edge_length_t{}, sgb_graph, sgb_e);
                }));
        {
            dijkstra_shortest_paths(vector_graph, *vertices(vector_graph).first
                    , weight_map(make_assoc_property_map(wmap))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : vector_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(vector_graph, *vertices(vector_graph).first
                    , weight_map(make_assoc_property_map(wmap))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }


    std::cout << "Average:" << std::endl;
    std::cout << "  SGB:              " << accumulate(sgb_result, 0.0) / sgb_result.size() << std::endl;
    std::cout << "  v=vecS,e=vecS:    " << accumulate(vecSvecS_result, 0.0) / vecSvecS_result.size() << std::endl;
    std::cout << "  v=vecS,e=listS:   " << accumulate(vecSlistS_result, 0.0) / vecSlistS_result.size() << std::endl;
    std::cout << "  v=listS,e=vecS::  " << accumulate(listSvecS_result, 0.0) / listSvecS_result.size() << std::endl;
    std::cout << "  v=listS,e=listS:  " << accumulate(listSlistS_result, 0.0) / listSlistS_result.size() << std::endl;
    std::cout << "  vector:           " << accumulate(vector_result, 0.0) / vector_result.size() << std::endl;
    std::cout << "Max:" << std::endl;
    std::cout << "  SGB:              " << *max_element(sgb_result) << std::endl;
    std::cout << "  v=vecS,e=vecS:    " << *max_element(vecSvecS_result) << std::endl;
    std::cout << "  v=vecS,e=listS:   " << *max_element(vecSlistS_result) << std::endl;
    std::cout << "  v=listS,e=vecS::  " << *max_element(listSvecS_result) << std::endl;
    std::cout << "  v=listS,e=listS:  " << *max_element(listSlistS_result) << std::endl;
    std::cout << "  vector:           " << *max_element(vector_result) << std::endl;
    std::cout << "Min:" << std::endl;
    std::cout << "  SGB:              " << *min_element(sgb_result) << std::endl;
    std::cout << "  v=vecS,e=vecS:    " << *min_element(vecSvecS_result) << std::endl;
    std::cout << "  v=vecS,e=listS:   " << *min_element(vecSlistS_result) << std::endl;
    std::cout << "  v=listS,e=vecS::  " << *min_element(listSvecS_result) << std::endl;
    std::cout << "  v=listS,e=listS:  " << *min_element(listSlistS_result) << std::endl;
    std::cout << "  vector:           " << *min_element(vector_result) << std::endl;
}

Boost.Graph property to Boost.Fusion

Boost.Graph のグラフ構造体で使用される property を fusion::for_each で使用できるようにしてみました. ソースは こちら にあげています.

property に bundle (ユーザが定義した構造体)が含まれる場合, bundle は fusion::for_each 上には現れないので注意です.

以下は使用例で, グラフを graphviz の dot 言語に書き出す際に node attributes を fusion::for_each で出力しています(attribute の名前は面倒なので typeinfo::name に使用しています).

使用例:

#include <iostream>
#include <boost/fusion/algorithm/iteration/for_each.hpp>
#include <boost/fusion/container/map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include "canard/property_sequence.hpp"

// 長い property のリスト
using vertex_property
    = boost::property<
        boost::vertex_index_t, std::size_t
    , boost::property<
        boost::vertex_color_t, std::string
    , boost::property<
        boost::vertex_name_t, std::string
    , boost::property<
        boost::vertex_rank_t, std::size_t
    >>>>;
using graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, vertex_property>;

struct print_property
{
    explicit print_property(std::ostream& out)
        : out{out}
    {
    }

    template <class Tag, class T, class Base>
    void operator()(boost::property<Tag, T, Base>& p) const
    {
        (is_first ? out : (out << ", ")) << typeid(Tag).name() << "=" << p.m_value;
        is_first = false;
    }

    std::ostream& out;
    mutable bool is_first = true;
};

struct vertex_property_writer
{
    using all_property_map = boost::property_map<graph, boost::vertex_all_t>::type;

    template <class Vertex>
    void operator()(std::ostream& out, Vertex const v) const
    {
        // node attirbutes を出力
        out << "[";
        boost::fusion::for_each(get(all_map, v), print_property{out});
        out << "]";
    }

    all_property_map all_map;
};

int main()
{
    auto g = graph{};
    add_vertex(vertex_property{0, {"blue", {"tokyo", {2}}}}, g);
    add_vertex(vertex_property{1, {"red", {"sapporo", {1}}}}, g);
    boost::write_graphviz(std::cout, g, vertex_property_writer{get(boost::vertex_all, g)});
}

実行結果:

digraph G {
0[N5boost14vertex_index_tE=0, N5boost14vertex_color_tE=blue, N5boost13vertex_name_tE=tokyo, N5boost13vertex_rank_tE=2];
1[N5boost14vertex_index_tE=1, N5boost14vertex_color_tE=red, N5boost13vertex_name_tE=sapporo, N5boost13vertex_rank_tE=1];
}

Boost.Program_optionsで名前を持たないオプションの扱い方

Boost.Program_optionsについて調べてみたので，備忘録として．

名前を持たないオプションの対応

以下が名前を持たないオプション値の例です．オプション値hogeはoptionという名前に関連づけされていますが，huga.txtには関連づけされた名前がありません．

$ command --option=hoge huga.txt

以下のような一般的なProgram_optionsの使用方法ではhuga.txtが手に入りません．

#include <iostream>
#include <boost/program_options.hpp>

using namespace boost::program_options;

int main(int argc, char* argv[])
{
    auto desc = options_description{"options"};
    desc.add_options()
        ("option", value<std::string>(), "some option");
    auto vm = variables_map{};
    store(parse_command_line(argc, argv, desc), vm);
    notify(vm);

    if (vm.count("option")) {
        std::cout << vm["option"].as<std::string>() << std::endl;
    }
}

positional_options_descriptionを使用する方法

この場合，huga.txtを扱うには二通り方法があります． 一つ目がpositional_options_descriptionを使用する方法です．これはドキュメントにも載っている方法なので例だけ示します．

auto desc = options_description{"options"};
desc.add_options()
    ("option", value<std::string>(), "some option")
    // 名前をつけないオプションにも名前をつける
    ("unnamed-option", value<std::string>(), "unnamed option")
    ;

auto vm = variables_map{};
store(command_line_parser{argc, argv}
        .options(desc)
        .positional(
            positional_options_description{}
                // 名前の付いていないオプション一つをunnamed-optionで名前づけする
                .add("unnamed-option", 1))
        .run()
    , vm);
notify(vm);

if (vm.count("option")) {
    std::cout << vm["option"].as<std::string>() << std::endl;
}

if (vm.count("unnamed-option")) {
    std::cout << vm["unnamed-option"].as<std::string>() << std::endl;
}

ちなみにpositional_options_description::addの第二引数の整数値は，第一引数に指定した名前を持つオプション値の個数を表します． 位置を指定している訳ではありませんので注意してください．-1を指定すると個数は無制限になります．

positional_options_description{}
    .add("unnamed1", 2)
    .add("unnamed2", 1)
    .add("unnamed3", -1)
    .add("unnamed4", 2);

上記のような場合，コマンドライン上に表れる名前を持たないオプション値のうち，左から二つはunnamed1に関連づけられ，その次の一つ，さらにその次の二つはそれぞれunnamed2，unnamed4に関連づけられます．残りのオプション値はunnamed3に関連づけられることになります．

さらに.add("unnamed5", -1)と書くとunnamed3にはオプション値は一つも関連づけられず，代わりにunnamed5に関連づけられます．

collect_unrecognizedを使用する方法

positional_options_description使用する方法の欠点は，名前を必要としないオプション値に対しても名前付けする必要があることです．

名前が不要のオプションに対して名前を付けてしまうと，helpオプション等の出力にoptions_descriptionインスタンスを用いた場合，不要なオプションが見えてしまいます．Program_optionsのtutorialでは，options_descriptionの複数のインスタンスを用いることでこの問題を解決していましたが，出力と実際のparsingで使用するインスタンスが異なるのはあまりよいとは思えません．

ここでは関数collect_unrecognizedを使用して，options_descriptionインスタンスに変更を加えずに名前を持たないオプションを取得します．

collect_unrecognizedは指定したoptions_descriptorインスタンスが知らないオプションを取得する関数です（デフォルトではparserは，'-'で始まるオプションが知らないものだった場合，例外を投げるため，これを許容するようにする必要があります）．

collect_unrecognizedの第一引数はstd::vector<basic_option>であり，これはparsing結果から取得できます．

第二引数はcollect_unrecognized_mode型の値であり，include_positionalとexclude_optionalの二つの値が存在します．前者を指定すると'-'から始まらないオプションも取得することができます．

以下が例です．

auto desc = options_description{"options"};
desc.add_options()
    ("option", value<std::string>(), "some option");
auto vm = variables_map{};
// parsingの結果を保持
auto const parsing_result = parse_command_line(argc, argv, desc);
store(parsing_result, vm);
notify(vm);

if (vm.count("option")) {
    std::cout << vm["option"].as<std::string>() << std::endl;
}

std::cout << "unnamed options:" << std::endl;
// parsingの結果からoptions_descriptionに関係しないものを取得
for (auto const& str : collect_unrecognized(parsing_result.options, include_positional)) {
    std::cout << "    " << str << std::endl;
}

先読みiteratorアダプタ作ってみた

指定した値分だけiteratorが進んで見える(つまりstd::advance(it, n))ようなiteratorアダプタを作ってみました.

Boost.Rangeのslicedでも同じようなことができるのですが, このアダプタはbase()では元の場所を指したiteratorを返します. 式で書くと*it == *(it.base() + n)になります.

gist8730956

findやlower_boundなどiteratorを返すアルゴリズムで目的の値の一つ手前の要素が欲しいときに使うことを想定しました.

#include "slide_view_iterator.hpp"
#include <algorithm>
#include <boost/range/irange.hpp>
#include <iostream>

int main()
{
    auto numbers = boost::irange(0, 10);
    {
        auto it = std::lower_bound(
                canard::make_slide_view_iterator(numbers.begin(), 1)
              , canard::make_slide_view_iterator(numbers.end())
              , 9);
        std::cout << *it.base() << " is one step short of " << *it << std::endl;
    }
    {
        auto it = std::find(
                canard::make_slide_view_iterator(numbers.begin(), 2)
              , canard::make_slide_view_iterator(numbers.end())
              , 8);
        std::cout << *it.base() << " is two step short of " << *it << std::endl;
    }
}

iterator_category等のチェックは未実装です.

std::pair<Iterator, Iterator>をrange based forで使用する

C++11にはrange based forが加わり，rangeに対する走査処理を書くのが楽になりました．しかしながら，このstd::pair<Iterator, Iterator>で表されるIterator対はこのrangeには含まれません*1． そのため以下のようなコードはコンパイルエラーになります．

#include <iostream>
#include <map>

int main() {
    auto const map = std::multimap<int, int>{{2, 3}, {2, 4}, {2, 5}};
    for (auto const& entry : map.equal_range(2)) { // equal_rangeはIterator対を返す!!
        std::cout << "key: " << entry.first << " value: " << entry.second << std::endl;
    }
}

こういった場合は，Boost.Rangeのfor_eachとlambda式を組み合わせることで解決できます．

#include <iostream>
#include <map>
#include <boost/range/algorithm/for_each.hpp>

int main() {
    auto const map = std::multimap<int, int>{{2, 3}, {2, 4}, {2, 5}};
    boost::for_each(map.equal_range(2), [](std::pair<int, int> const& entry) {
        std::cout << "key: " << entry.first << " value: " << entry.second << std::endl;
    });
}

しかしながら，lambda式の引数の型名が長くなってくると，このやり方は少々面倒なことになります．特にBoost.Graphではそれが顕著になります．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/range/algorithm/for_each.hpp>

int main() {
    boost::adjacency_list<> graph;
    // lambda式の引数の型名が長い
    boost::for_each(vertices(graph), [&](boost::graph_traits<decltype(graph)>::vertex_descriptor const v) {
        std::cout << "v index: " << get(boost::vertex_index, graph, v) << std::endl;
    });
}

こうなってくると，range based forを通した型推論を使って型名を書くのを避けたくなります．しかしながら，既に述べた通りstd::pairによるIterator対を使うとコンパイルエラーになってしまうため，そのままでは使用できません．自分でstd::pairに対するwrapperを書いてもいいですが，Boost.Rangeにiterator_rangeがあるのでこれを使用します．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/range/algorithm/for_each.hpp>

int main() {
    boost::adjacency_list<> graph;
    // autoでOK!!
    for (auto v : boost::make_iterator_range(vertices(graph))) {
        std::cout << "v index: " << get(boost::vertex_index, graph, v) << std::endl;
    };
}

make_iterator_rangeはfiltered等のadaptorとは異なり(adaptorもiterator_rangeを使ってました)，Iteratorをコピーするので元のIterator対の寿命を気にする必要がありません(上記ではvertices(graph)が返すIterator対の寿命)*2．

まとめ

Generic lambdaサイコー!!

*1:http://stackoverflow.com/questions/6167598/why-was-pair-range-access-removed-from-c11?rq=1

*2:std::vector等のテンポラリオブジェクトを渡すのはダメです

Boost1.55でMultiple Source Dijkstra

この記事はC++ (fork) Advent Calendar 2013の22日目の記事になります．
今回も軽めの記事です．ご了承ください．

Boost1.55ではBoost.Graphの関数boost::dijkstra_shortes_pathsがマルチソースに対応しましたので，本記事ではこれを紹介します．

dijkstra_shortest_paths

関数dijkstra_shortest_pathsはその名前からも分かる通り，ダイクストラ法を用いた最短経路木を探索するためのアルゴリズムです．通常，ダイクストラ法ではスタート地点となる節点を一つ選択し，この節点から他の節点までの最短経路を求めます．

マルチソースの場合はスタート地点(ルート)となる節点が複数になります．実際に図で見てみるとこのようになります(見た目上枝の長さは違いますが，論理的にはすべて同じにしてます)．
二重線で囲まれている節点(ラベルが0, 20, 40, 60, 80の節点)がルートになります．
マルチソースダイクストラでは，ルート以外の節点vと，各ルート間のすべての最短経路が計算されるのではなく，経路距離が最小となるルートとの経路のみが計算されます．そのため図中ではルート以外の節点は経路距離が最小となるようなルートと同じ色で塗り分けしています．
この図はグラフのボロノイ分割と呼ばれ，勢力図等を作成するのに役立ちます．例えば，ルートを消防署と考えれば，ある節点で火事が起きた際にどこの消防署から消防車を出せばよいかの指標になります．

マルチソース版の実装で，シングルソース版との違いは探索開始時に優先度付きキューの中身に複数のルートがあるという点だけですので，容易に実装できます(私も昔作りました)．

上記のような図をboost::dijkstra_shortes_pathsを用いて作成するコードは以下になります．

A example of multiple source dijkstra.

ルート節点の指定

注目すべき箇所は関数multisource_dijkstra内のboost::dijkstra_shortest_pathsの呼び出しです．
第一引数はシングルソースの場合と同じで探索対象のグラフですが，第二，第三引数がルートとなる節点の集合を示すイテレータペアになっています(Rangeで渡したいですね!!)．シングルソースの場合は，第二引数にルートとなる節点一つを指定していた場合とは異なります．それ以外の引数はシングルソースの場合と同じです．

各節点から最短のルートの記録

ここではparent_recorderという名前のEventVisitorを新たに作成しています(root_recorderという名前にすればよかった)．これは新たに探索された節点がどのルートから探索されたかを記憶します．親(predecessorであってparentではない)のルートを自節点のルートに設定するだけです．あらかじめルートとなる節点のルートをその節点に設定しておく必要はありますが，そこは我慢します．

void operator()(Edge const e, Graph const& g) const {
    auto value = get(parent_map_, source(e, g));
    put(parent_map_, target(e, g), value);
}

getとputを合わせて一行にせずにわざわざgetで取得した値をコピーしているのは，put時にparent_map_の内部で保持するvectorのresize()が呼ばれてgetで取得した値が破棄されるのを防ぐためです(というか一行で書いて嵌りました)．

引数の数

上記のdijkstra_shortes_pathsの呼び出しでは12個の引数を指定していますが，これらを省略することはできません．
通常Boost.Graphの関数はdjikstra_shortest_pathsも含め，Named Parameter Idiomを用いた名前付き引数によってデフォルト引数を持つパラメータに対して引数を指定する必要はありません．しかしながら，マルチソースの場合名前付き引数を持つオーバロードが一つもないので，すべての引数を指定する必要があります(さらにVertexColorMapを指定するオーバロードならありました．これで引数の数は13個!!)．
使い勝手はかなり悪いので，名前付き引数版をオーバロード可能かどうか調査して追加するか独自にラッパを作成する必要がありそうです．

グラフの視覚化

出力されたファイルはgraphvizを使えばいい感じにレイアウトしてくれます.

fdp -Nstyle=filled -Nshape=circle -Nperipheries=peripheries -Tpng -O graph.dot

まとめ

マルチソースダイクストラは現状undocumentedですが，シングルソース版の使い方が分かっていれば使用方法が分からないことはないと思います．また，Boost1.55ではダイクストラだけではなく，幅優先探索もマルチソースに対応しているので利用してみるといいかもしれません(今回の例では枝の長さがすべて等しいので本当はこっちを使うべきでした)．

アルゴリズムとか意味がなかった

https://paiza.jp/poh/ec-campaign に挑戦してみましたので，そのコードを載せておきます．

#include <iostream>
#include <vector>
#include <algorithm>

template <class Iterator>
inline int calc(Iterator const first, Iterator const last, int const value)
{
    if (*(last - 1) + *(last - 2) <= value) {
        return *(last - 1) + *(last - 2);
    }
    Iterator upper = std::lower_bound(first + 1, last, value / 2);
    if (upper + 1 != last && *upper + *(upper + 1) == value) {
        return value;
    }
    int best_price = 0;
    for (Iterator lower = std::upper_bound(first, upper, value - *upper);
         lower != first && upper != last;
         lower = std::upper_bound(first, lower - 1, value - *upper)) {
        upper = std::upper_bound(upper + 1, last, value - *(lower - 1));
        best_price = std::max(best_price, *(upper - 1) + *(lower - 1));
        if (best_price == value) {
            break;
        }
    }
    return best_price;
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int N, D;
    std::cin >> N >> D;
    std::vector<int> prices;
    prices.reserve(N);
    for (int i = 0; i < N; ++i) {
        int p;
        std::cin >> p;
        prices.push_back(p);
    }
    std::sort(prices.begin(), prices.end());
    for (int i = 0; i < D; ++i) {
        int m;
        std::cin >> m;
        std::cout << calc(prices.begin(), prices.end(), m) << '\n';
    }
}

結果は http://paiza.jp/poh/ec-campaign/result/16051cf4bd6d13df012bc008d1fdad13 です．case3は0.13secでした．