授業で示した最短経路問題を解くダイクストラのプログラムについて、指定された始点から全頂点への経路値と経路を標準出力表示する機能を追加せよ。
・到達不能である場合は、到達不能である旨の表示をすること。
・経路表示は始点⇒終点でも終点⇒始点のどちらの順でもよいが、そのどちらであるかを標準出力表示中で明示すること。
・出力結果が読みやすくなるように、テキスト出力部分を工夫してあるほうがよい。
・出力は日本語で表現しないこと（採点時のトラブルを避けるため）。
| グラフ名 | GRAPH_D | GRAPH_E | |||
| 隣接行列 |
#define NC 9999
#define N 6
int edge[N][N] = {
{ 0, NC, NC, 8, 15, NC},
{ 10, 0, 24, NC, 8, NC},
{ NC, NC, 0, NC, NC, 6},
{ NC, NC, NC, 0, 5, NC},
{ NC, NC, 12, NC, 0, 7},
{ NC, NC, 3, NC, NC, 0}
};
|
#define NC 9999
#define NC 12
int edge[N][N] = {
{ 0, 4,NC,NC, 3,NC,NC,NC,NC,NC,NC,NC},
{ 4, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC,NC},
{NC, 1, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC},
{NC,NC, 1, 0,NC,NC,NC,NC,NC,NC,NC,NC},
{ 3,NC,NC,NC, 0, 1,NC,NC, 1,NC,NC,NC},
{NC,NC,NC,NC, 1, 0, 2,NC,NC, 2, 3,NC},
{NC, 2,NC,NC,NC, 2, 0,NC,NC,NC, 3,NC},
{NC,NC, 2,NC,NC,NC,NC, 0,NC,NC,NC,NC},
{NC,NC,NC,NC, 1,NC,NC,NC, 0,NC,NC,NC},
{NC,NC,NC,NC,NC, 2,NC,NC,NC, 0,NC,NC},
{NC,NC,NC,NC,NC, 3, 3,NC,NC,NC, 0, 1},
{NC,NC,NC,NC,NC,NC,NC,NC,NC,NC, 1, 0}
};
|
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合 | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合 | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合 | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
授業で示した最短経路問題を解くダイクストラのプログラムにおけるコスト評価部分について、"&&"を外してif文を２段化したプログラムに書き直せ。
また、それぞれのif文で判断される内容を、１文ずつわかりやすい日本語で説明せよ。
| 元プログラム |
for (u = 0; u < numU - 1; u++) {
if (edge[min_node][setU[u]] > 0 && cost[min_node] + edge[min_node][setU[u]] < cost[setU[u]]) {
cost[setU[u]] = cost[min_node] + edge[min_node][setU[u]];
from[setU[u]] = min_node;
}
}
|
| 書き直し |
int detourvalue;
for (u = 0; u < numU - 1; u++) { //説明
if ( ... ) { //説明
detourvalue = ... ; //説明
if ( ... ) { //説明
cost[setU[u]] = ... ; //説明
from[setU[u]] = min_node;
}
}
|
授業で示したdijkstra, floyd のアルゴリズムの時間計算量を、プログラム上で根拠となる部分を示しながら述べよ。
ビッグＯオーダー表現でよい。
この２つの時間計算量の関係をもとにして、N対Nの（全ペアの）最短経路問題をdijkstraのアルゴリズムで解いた場合の利点欠点を述べよ。
授業で示したfloydのアルゴリズムについて、全頂点対の最短経路値とその経路を標準出力で表示する機能を追加せよ。
出力の可読性については、課題３Ａに準拠すること。
この機能は新規関数を用意して実装すること。