0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

【自分用】最短経路問題メモ

0
Last updated at Posted at 2020-03-29

最短経路問題で使用するアルゴリズム

  • BFS
    • 計算量:O(N)
    • 使用用途:辺のコストが全て1のとき
  • ダイクストラ
    • 計算量:O(MlongM)
    • 使用用途:辺のコストが違うとき
  • ワーシャルフロイド
    • 計算量:O(N**2)
    • 使用用途:密なグラフ(点が少なく辺が多い)で全点間の距離を求めるとき
    • 特徴:点間の総コストが計算できる、実装が軽い
  • ベルマンフォード
    • 計算量:O(NM)
    • 使用用途:負のコストの辺があるとき

※基本的にはBFSもしくはダイクストラでOK

問題一覧

回答

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?