最短経路問題をやります。最短経路を求めるアルゴリズムとして、ダイクストラ法を取り上げます。最後に問題を解きます。 最短経路問題 重み付きグラフが与えられているとします。最短経路問題とは、ある２点間をつなぐパスを構成する辺の重みの総和が最小と…

最小全域木の基本と、それに関連する知識を簡単にまとめておきます。最後に最小全域木に関する問題を解きます。 最小全域木 全域木 グラフGがあるとします。そして、その部分グラフG'を考えます。G' が G の全ての頂点を含み、かつ辺をできるだけ多く含む木…