STEP 6.3 ダイクストラ法 (最短距離) 問6.3 (p.139)

注意: ライブラリに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



解答例
#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);