C言語プログラミング
最短経路問題解法プログラミング
最短経路問題(Shortest Path)を題材としたプログラミングを行います。
プログラミング言語はC/C++を使用し、Visual Studioを利用します。
- Visual Studio(コンパイラ)のインストールと使い方
- ファイル(テキストデータ)の読み書きと二次元配列
- 最短経路問題を解くアルゴリズム
- 実行時間を減らす工夫
- リスト構造
Visual Studioのインストール、使い方については
こちらも参照のこと。
課題および説明資料
- 入力グラフデータを読み込むプログラムを作成し、グラフの点数およびデータファイル中に記された最短経路長正解を表示しなさい。
- 入力グラフデータを読み込み、グラフの枝数を調べて表示しなさい。
- 枝を二次元配列で表現したBellman-Ford法のプログラムを作成しなさい。
- 二次元配列で表現した枝の参照を効率化する改善を行いなさい。
- 枝をリスト構造で表現したBellman-Ford法のプログラムを作成しなさい。
- Dijkstra法のプログラムを作成しなさい。
- sentinel手法を利用してプログラムを改善しなさい。
発展
- 最短経路長候補集合を利用するようにプログラムを改善しなさい。
入力グラフデータ
資料等は随時更新します。
令和6年11月5日(課題資料更新、発展追記)
令和6年9月24日(課題資料更新)
令和6年9月20日(課題資料更新)
令和5年11月13日(課題資料更新)
令和5年10月12日(課題資料更新)
令和5年10月11日(課題資料更新)
令和4年12月19日(課題資料更新)
令和4年12月4日(課題資料更新)
令和3年12月13日(課題資料更新)
令和3年9月30日(課題資料更新)
令和3年9月28日(課題資料更新)
令和2年10月26日(課題資料更新)
令和2年9月25日(課題資料更新)
令和2年4月2日(課題資料更新)
令和2年3月27日(課題資料更新)
令和元年11月13日(課題資料更新)
令和元年11月9日(課題資料更新)
令和元年11月6日(課題資料更新)
令和元年10月28日(課題資料更新)
令和元年10月9日(課題資料訂正)
令和元年10月8日(課題資料更新)
令和元年10月7日(課題資料更新)
伊藤和人