今日は有名なグラフ問題を４つ扱います。 その名の通り最短路を求める最短路問題をはじめ、 それぞれが何某かの最適化問題です。 今まで習ったアルゴリズムを応用して 高速なアルゴリズムで解けるものもあれば、 そうでないものもあります。

1. 重み付きグラフ
2. 最短路問題
3. 郵便配達員問題
4. 最小連結子問題
5. 巡回セールスマン問題
6. デモ動画、今日のまとめと宿題

配布プリント

• 最短路問題・郵便配達員問題・最小連結子問題・巡回セールスマン問題