気に入った記事をブックマーク
- 気に入った記事を保存できます
保存した記事の一覧は、はてなブックマークで確認・編集ができます
- 記事を読んだ感想やメモを書き残せます
- 非公開でブックマークすることもできます
エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント1件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
いまの話題をアプリでチェック！
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Spaghetti Source - k-最短路
説明 グラフ G と始点終点の対 (s,t) が与えられたとき，s-t パスの中で k 番目に短いものを求める問題... 説明 グラフ G と始点終点の対 (s,t) が与えられたとき，s-t パスの中で k 番目に短いものを求める問題を k-最短路問題という． この問題に対する最も基本的な解法は，優先度付きキューを用いてダイクストラ調にグラフを探索し，通常なら最短距離が確定した頂点を切り捨てるところを k 個の最短距離が確定した頂点を切り捨てるようにすることである（以下に実装を示した）．この方法で計算量 O(k E log V) が達成できる．多くの応用ではこれで十分だと考えられる． 理論的にはもっと頭の良い解法が提案されており，例えば Eppstein による deviation に基づくアルゴリズムは O(k + E + V log V) を達成する．しかし，このアルゴリズムはパスを管理するデータ構造を持たなければならず，シンプルに実装するのは難しい．そこで以下では Eppstein の方法を参考にした
ブックマークしたユーザー
すべてのユーザーの
詳細を表示します
詳細を表示します
2017/07/28 リンク