数学特別演習（第4回）

今日の授業では、ダイクストラのアルゴリズムの計算量の見積りを中心にやりました。一般のn個のノードを考えた場合というのは、なかなかピンとこないようですが、数個の具体例を考えて計算すると、納得できたという人が多いようでした。

あとは、グラフの辺の重みがノード間の距離に対応するような場合は、直観的な距離の探索が役に立つ・・・というのは、すでに始点と終点を結ぶ経路を1つ知っていた場合、最短経路は、始点と終点を焦点とし、すでに知っている経路の距離を長軸にもつ楕円の内部に存在する、という話も出ましたが、この話は、多くの人達にとって新鮮だったようです。

次回は、前処理の話と、グラフの「最小全域木（スパニングツリー）」の話になると思います。私も予習を頑張りたいと思います。