最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita

基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。 始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニ

[yarumato]

“競技プログラミングで超頻出の最短経路問題についてアルゴリズムを総特集しました。グラフ問題だけでなく、様々な最適化問題がグラフの最短経路問題に帰着可能です。では、たのしい競プロライフを！”

[dlive1]

競技プログラミングで超頻出の最短経路問題について特集

[mohno]

「基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました」

[emergent]

苦手なのでありがたい

[pascal256]

後で読む

[ImpureSilver11]

すき

[miler_yoshio]

経路探索したくなった時に参照したい！こういうまとめは、なかなか見ないのよねえ。