Dijkstraのアルゴリズム解法を実現するプログラムを作成し、コンパイルして実行せよ。
このとき、グラフ中の指定頂点に対して、全ての頂点への最短経路コストと最短経路を標準出力に表示すること。
経路の表示方法は、それが読める形であれば形式は問わない。
|
【注意】 | |
| 誰かに教えてもらった場合： | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |
授業で提示したFloydのアルゴリズムについて、
・時間計算量
・空間計算量(読み出しのみのメモリと書き込みが必要なメモリの総和について)
・空間計算量(書き込みが必要なメモリのみについて)
の見積もりを示し、その根拠を説明しなさい。
説明時にはビッグオー表現も使うこと。
ヒント：隣接行列は読み出して使うだけなので、この見積もりには入りません。
Floydのアルゴリズム解法を実現するプログラムを作成し、コンパイルして実行せよ。
このとき、グラフ中の全ての頂点対について、最短経路コストと最短経路を標準出力に表示すること。
経路の表示方法は、それが読める形であれば形式は問わない。