単一始点最短経路(Single Shortest Path)の解法と勉強方法と例題まとめ

このページは、私が単一始点最短経路(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
重みに負の要素があり、ダイクストラ法を使うことができないので、
ベルマンフォードを使う必要があります。