トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

ダイクストラ法

[アルゴリズム,グラフアルゴリズム]

練習のための問題は 競技プログラミングの履歴

グラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

TODO: 重みの合計値が一定以内に収まる経路の探索ってどうやって求める?

ダイクストラ法

  詳しい解説

疑似コード

+ 疑似コード

  AOJの関連する問題

  計算量 O(V^2)

オリジナルのアルゴリズムは隣接行列をしようするため計算量がV^2

ALDS1_12_B

解答

+ サンプルコード

  計算量 O((E+V) log V)

ALDS1_12_C

解答


お名前: コメント: