No Caffeine, No Life

プログラミング(主にPython)

ダイクストラ法とベルマンフォード法

ダイクストラ

  • 頂点集合に注目
  • 比較的早い
  • 負の重みに対応できない

ベルマンフォード法

  • 辺集合に注目
  • 比較的遅い
  • 負の重みに対応できる

参考:

最短経路問題(ベルマンフォード法・ワーシャルフロイド法) - アルゴリズム講習会

最短経路問題:ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法(6題) - 藤 遥のブログ