ダイクストラ法のテンプレ~経路復元可(C++)

アルゴリズム

機能

  • 最短経路を求める(答えを配列で受け取ったり、ある頂点への距離だけ受け取ったりできます)
  • 最短経路の復元(配列で返します)
namespace template_algorithm {
    /// @brief ダイクストラ法(クラス)
    /// @attention 求められるものは「startからの」最短経路。 求める際は0-indexedにすること。
    template<typename T>
    class dijkstra{
        public:
        /// @brief 辺クラス
        class edge{
            public:
            int to;
            T cost;
        };

        /// @brief コンストラクタ
        /// @param n_ 頂点数
        /// @param start_ スタート地点(source)(0-indexed)
        dijkstra(int n_, int start_) {
            n = n_;
            INF = numeric_limits<T>::max();
            adj_list.assign(n, vector<edge>());
            set_start(start_);
        }

        /// @brief ソース(始点)、配列の初期化
        void set_start(int start_) {
            start = start_;
            shortest_path.assign(n, INF);
            prev_node.assign(n, -1);
        }

        /// @brief fromからtoに重みcostの辺を追加
        void add_edge(int from, int to, T cost){
            adj_list[from].push_back({to, cost});
        }

        /// @brief このクラス内の隣接リストを使った最短経路計算
        vector<T> search_shortest_path() {
            return culc_shortest_path(adj_list);
        }

        /// @brief このクラス外から与えられた隣接リストを使った最短経路計算
        vector<T> search_shortest_path(const vector<vector<edge> > &arg_adj) {
            return culc_shortest_path(arg_adj);
        }

        /// @brief 頂点startからのtoまでの最短距離を返します
        T get_shortest_path(int to) {
            return shortest_path[to];
        }

        /// @brief toまでの具体的な経路を返します
        vector<int> get_concrete_path(int to) {
            vector<int> concrete_path;
            for (int i = to; i != -1; i = prev_node[i]) {
                concrete_path.push_back(i);
            }
            reverse(concrete_path.begin(), concrete_path.end());
            return concrete_path;
        }

        private:
        int n;
        int start;
        T INF;
        vector<vector<edge> > adj_list;
        vector<T> shortest_path;
        vector<int> prev_node;

        /// @brief 最短経路の計算
        vector<T> culc_shortest_path(const vector<vector<edge> > &arg_adj) {
            //tuple   <0> := コスト <1>:= 頂点番号 <2>:= どの頂点から来たか
            priority_queue<tuple<T, int, int>, vector<tuple<T, int, int> >, greater<tuple<T, int, int> > > pq;
            pq.push({0, start, -1});

            while (!pq.empty()) {
                tuple<T, int, int> t = pq.top();
                pq.pop();

                //現在のノードまでのコスト
                T cost;
                //現在の頂点
                int now_v;
                //ひとつ前の頂点
                int prev_v;
                tie(cost, now_v, prev_v) = t;

                //すでに確定している
                if (shortest_path[now_v] != INF) continue;

                //最短距離を確定
                shortest_path[now_v] = cost;

                //ひとつ前の頂点を記録
                prev_node[now_v] = prev_v;

                //確定した頂点から出ている辺すべてについて、調べる候補に追加
                for (auto &e : arg_adj[now_v]) {
                    //よりコストが増える場合は飛ばしてよい
                    if (shortest_path[e.to] < cost + e.cost) continue;
                    pq.push({cost + e.cost, e.to, now_v});
                }
            }
            return shortest_path;
        }
    };
}

より詳しい使い方

最短経路を求める

1.ダイクストラクラスを作成する

2.辺を追加する(2パターンあります)
2-1.「ダイクストラクラス内」の隣接リストに辺を追加する(add_edge())パターン
提出 #52710738 – 競プロ典型 90 問 (atcoder.jp)

それぞれのダイクストラクラスごとにadd_edgeをしないといけないです。
グラフが与えられて、そのグラフから辺を削除してから再度求める場合などには使えません。(追加はできるけど削除不可)
これに対応したものがパターン2↓です

2-2.「外から」引数として隣接リストを与えるパターン
提出 #52710496 – 競プロ典型 90 問 (atcoder.jp)

引数で与えるための隣接リストの宣言が少しややこしいですが、辺を削除する事もできます

3.search_shortest_path()を呼びます。
 辺の追加がパターン1なら引数なし。
 パターン2なら引数として隣接リストを渡してください。

 返り値として、最短距離の配列を返します。
 ここで返り値を受け取らなくても始点を変えない限りはダイクストラクラスが最短距離を持ってます

経路復元

get_concrete_path(to)を呼びます。

1.必ずsearch_shortest_path()(引数の有無はどちらでもよい)を呼んだ後に、このメソッドを使用してください。(そうでないと求めれません)

2.こちらは返り値として受け取らなかった場合、保持されないので必ず返り値を何らかの変数に代入してください。

最後に

余談ですが、筆者はこれを書く際にassign()のところをresize()と書いてうまくいかず、
久しぶりにassign()とresize()の違いを思い出しました。
assign() ←全部埋める
resize() ←「足りないところ」を全部埋める

もし、「このコード使ったよ」(←励みになります)や「正しく動かないよ」ということがありましたら
筆者のX(旧Twitter)まで連絡いただけると助かります。

最後までお読みいただきありがとうございましたっ
ヾ(•ω•`)o

コメント

タイトルとURLをコピーしました