このページは、私が単一始点最短経路(Single Shortest Path)を理解する際参考にしたものをまとめたものです。
単一始点最短経路(Single Shortest Path)の概念について
MITのOpen soft ware courseに単一始点最短経路の概念説明のvideoがあるので、
それを参考にするといいかと思います。
遷移先に資料のpdfなども上がっています。
補講動画(細かいネタが載っているので、余裕があれば)
単一始点最短経路(Single Shortest Path)の解法アルゴリズム
解法として主にダイクストラ法とベルマン–フォード法があります。 この2つが基本になるっぽい。
ダイクストラ法とは
単一始点最短経路(Single Shortest Path)を解くための代表的なアルゴリズムです。
ただし、重みが-になる場合は適応できません。
MITのopen course videoにてダイクストラ法についての解説があるので、
参考にするといいと思います。
こちらは、ダイクストラを高速化方法について、解説しています。
ベルマンフォード法とは
グラフの-の重みにも対応した解法アルゴリズムで、
その分ダイクストラよりも複雑になります。
mitのopen courseにベルマンフォード法について解説した動画があるので、
参考にすると良いです。
単一始点最短経路(Single Shortest Path)の例題まとめ
単一始点最短経路を扱った例題をまとめます。
例題1
ALDS1_12_B
頂点の数が少ないので、隣接行列を使って解くことができます。
問題の解法ををこちらにまとめました。
例題2
ALDS1_12_C
問題は同じですが、頂点数が多いため解法を工夫する必要があります。
優先度付きqueを使った解法をこちらでまとめています。
例題3
GRL_1_A
例題2と内容は同じですが、与えられる入力が異なります。
例題4
GRL_1_B
重みに負の要素があり、ダイクストラ法を使うことができないので、
ベルマンフォードを使う必要があります。
