注意: ライブラリにmin関数があるかもしれません。minを自作するとコンパイルの際にエラーが出る場合があります。適当な名前に変えて定義してください。下では、minから、lessに名前を変えておきました。gccを使う人は、minのままでもOK。deleteにエラーが出る場合も、関数名を変えてください。(エラーメッセージを読み、じたばたしよう!)
<問題>
p.135 からの解説、p136の疑似コードを読んで、作成してください。
事実上、適切なコメントをつけなさい、という課題
(「巻末のプログラムをコピーしてプログラムを提出しなさい」という課題ではありません。もちろん参考にしてもらってよいけれども、ダイクストラ法のプログラムとして自分なりのコメントがないもの、実行を確かめていないものは、コメントのしようがありません。積極的な加点はしません)
<実行結果 例>
vertex1
to 2: dist:4
to 5: dist:5
vertex2
to 3: dist:9
to 5: dist:6
to 6: dist:2
vertex3
to 6: dist:3
vertex4
to 1: dist:3
to 5: dist:2
vertex5
to 4: dist:2
to 6: dist:8
vertex6
to 3: dist:3
to 7: dist:5
vertex7
to 5: dist:7
to 6: dist:5 (ここまでは、STEP6.1の出力 )
1 -> 1 : 0
1 -> 2 : 4 (頂点1から2までの最短距離は4)
1 -> 5 : 5
1 -> 6 : 6
1 -> 4 : 7
1 -> 3 : 9
1 -> 7 : 11
List構造体は list1.hに定義 typedef struct list { struct list *next; int data; /* グラフの頂点 intにする */ int dist; /* 距離 グラフの重みにあたる。追加。関係する関数変更 */ } List; ネットワークを表現できるように、distメンバーを追加。(たとえばOut配列で表現されているグラフの情報で使用) 探索中の頂点リストにあたる変数nからのリストは、distメンバーを使用せず。
解答例 #include "list1.h" #define N 7 List *Out[N+1]; /* 配列の各要素はList 個数は0から始まらないのでN+1にする*/ int less(int a, int b); /* 元は、min */ int exist(List *n, int u); void Dijkstra(int v);