Spaghetti Source - k-最短路
説明 グラフ G と始点終点の対 (s,t) が与えられたとき，s-t パスの中で k 番目に短いものを求める問題を k-最短路問題という． この問題に対する最も基本的な解法は，優先度付きキューを用いてダイクストラ調にグラフを探索し，通常なら最短距離が確定した頂点を切り捨てるところを k 個の最短距離が確定した頂点を切り捨てるようにすることである（以下に実装を示した）．この方法で計算量 O(k E log V) が達成できる．多くの応用ではこれで十分だと考えられる． 理論的にはもっと頭の良い解法が提案されており，例えば Eppstein による deviation に基づくアルゴリズムは O(k + E + V log V) を達成する．しかし，このアルゴリズムはパスを管理するデータ構造を持たなければならず，シンプルに実装するのは難しい．そこで以下では Eppstein の方法を参考にした
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
