授業で示した最長経路問題を解くアルゴリズムについて、与えられたグラフ中での最長経路の辺の重みの総和（コスト）と、その経路を示す頂点訪問順を示すプログラムを作成せよ。
頂点訪問順は、それが分かる形であれば出力形式は問わない。
提出するプログラムについては、与えるグラフはGRAPH_Cだけでよい。
・出力結果が読みやすくなるように、テキスト出力部分を工夫してあるほうがよい。
・頂点訪問順は、正順でも逆順でもよい（プログラム出力時にどちらか明記すること）。
| グラフ名 | GRAPH_B | GRAPH_C |
| 隣接行列 | #define N 8
int edge[N][N] = {
{0,4,0,0,2,0,0,0},
{0,0,0,0,0,0,1,0},
{0,0,0,3,0,0,3,0},
{0,0,0,0,0,0,0,5},
{0,0,0,0,0,2,0,0},
{0,0,0,0,0,0,2,0},
{0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0}
};
| #define N 8
int edge[N][N] = {
{0,4,0,0,2,0,0,0},
{0,0,0,0,0,0,1,0},
{0,0,0,3,0,0,3,0},
{0,0,0,0,0,0,0,5},
{0,0,0,0,0,2,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,4,0,1},
{0,0,0,0,0,0,0,0}
};
|
| 実行例 | Longest Path Value = 8 7 <- 3 <- 2 <- Go | Longest Path Value = 9 5 <- 6 <- 1 <- 0 <- Go |
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合 | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合 | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合 | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
授業で示した最長経路問題を解くアルゴリズムについて、各頂点が保持する「値」の性質を説明せよ。
授業で示した最長経路問題を解くアルゴリズムでは、ステップ(2)の終了後、ステップ(3)において、全ての頂点の値の中から最大値を求める処理を行っていた。
これは、(2)で最後に処理する頂点が最長経路の終点とは限らないからである。
このことが実際に発生するようなグラフとトポロジカルソートのの組み合わせの一例を示せ。
授業で示した最長経路問題を解くアルゴリズムの前提として、与えられた有向グラフ中に閉路（循環とも呼ばれる）があってはならない。
しかしながら、授業で示したアルゴリズムに従って実装する課題２Ａのプログラムでは、この前提の確認を行っていないため、閉路が存在するグラフが与えられたとしても誤って解を提示してしまうことになる。
そこで、課題２Ａのプログラムを改良して、閉路の検出を同時に行い、閉路検出時にはその閉路を示して（最長経路を示すことなく）終了するようにせよ。
なお、閉路検出はステップ(1)-(3)と別個に行うのではなく、その中の改良として実現すること。
| グラフ名 | GRAPH_D | GRAPH_E |
| 隣接行列 | #define N 8
int edge[N][N] = {
{0,4,0,0,2,0,0,0},
{0,0,0,0,0,0,1,0},
{0,0,0,3,0,0,3,0},
{0,0,0,0,0,0,0,5},
{0,0,0,0,0,2,0,0},
{0,0,0,0,0,0,2,0},
{0,0,0,0,0,0,0,1},
{0,0,0,0,4,0,0,0}
};
| #define N 8
int edge[N][N] = {
{0,4,0,0,2,0,0,0},
{0,0,0,0,0,0,1,0},
{0,0,0,3,0,0,3,0},
{0,0,2,0,0,0,0,5},
{0,0,0,0,0,2,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,4,0,1},
{0,0,0,0,0,0,0,0}
};
|