<問題>
STEP6.3のプログラムを改良します。巻末のプログラムを参考に （ちょっと気になるところもあるプログラムですが、解説します）
gcc -c 0604.c
gcc -o 0604 0604.obj list1.obj
<実行結果 例>
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
1 -> 2 : 4
1 2
1 -> 5 : 5
1 5
1 -> 6 : 6
1 2 6
1 -> 4 : 7
1 5 4
1 -> 3 : 9
1 2 6 3
1 -> 7 : 11 （←距離)
1 2 6 7 (経路）
経路をプリントする関数 printlist1は、printlistを改造してください。
あるいは、STEP6.5の最後を参照
#include "list1.h"
#define N 7
List *Out[N+1]; /* 配列の各要素はList 個数は0から始まらないのでN+1にする*/
int less(int a, int b);
int exist(List *n, int u);
void Dijkstra(int v);
/* 小さい値を戻り値 */
int less(int a, int b){
if(a < b){
return(a);
} else {
return(b);
}
}
/* 探索リストn に含まれる頂点かどうかを判定 */
int exist(List *n, int u){
List *w;
for (w = n->next; w != NULL; w = w->next) {
if (u == w->data){
return(1);
}
}
return(0);
}
void Dijkstra(int v0){
int m, v, i, j, in[N+1]; /* in[N+1] 各頂点の1つ前(なのでin。出るものはout) */
int visit[N+1], dist[N+1]; /* 各配列頂点nについて、確定済情報、最短距離 */
List *n, *w, *u, *s, *route[N+1];
/* nは探索中リスト wは探索リスト操作用ポインター
uは隣接OUTリスト操作用ポインター routeは、各頂点への経路リスト */
for(i = 0 ; i < N+1; i++) {
visit[i] = 0; /* 最短距離確定情報リスト、全ての頂点を0に */
route[i] = create(); /* 経路情報。まずはヌル */
}
n=create();
insert(n, 1, v0, 0); /* n の先頭には、スタート頂点 */
dist[v0] = 0;
in[v0] = v0; /* スタートのみ、自分自身で初期化 */
while (!empty(n)) { /* 教科書ではempty_l 探索リストがなくなるまで */
m = 9999; /* 比較のため、ありえない値を暫定最小距離にする */
i = 1;
/* 現状のnについて、距離が最小の頂点を求める */
for (w = n->next; w != NULL; w = w->next) {
if (m > dist[w->data]) { /* 頂点までの距離がmより小さいなら */
m = dist[w->data]; /* 暫定最小値 mを更新 */
v = w->data; /* 暫定最短頂点vを更新 */
/* u = w; */ /* uに、暫定最短頂点へのアドレス しかし、要らない。作者のミスと思われる */
j=i; /* この情報のnリストの位置を記録 */
}
i++; /* リスト内の位置カウンター */
}
/* 確定した最小値について */
visit[v] = 1; /* visit配列に、確定を記録 */
delete(n,j); /* 探索リストnから、j番目の頂点をdelete */
printf("%d -> %d : %d\n", v0, v, dist[v]); /* 確定情報のプリント */
s = route[v]; /* 決定したvの経路リスト先頭アドレス */
/* 一つ前の頂点までの経路をコピー */
for (w = route[in[v]] -> next; w != NULL; w = w->next) {
insert(s, 1, w->data, 0); /* 経路なので、distメンバーは0に */
s = s->next; /* スタックでもよいが、ここではリスト(キュー)を使用 */
}
insert(s, 1, v, 0); /* 一番最後に自分自身 */
printlist1(route[v]); /* 経路の出力 printlist1は、list1.cで定義 */
/* 確定した頂点vから、ひとつ先の頂点の情報で、全体情報を更新 */
for (u = Out[v]->next; u != NULL; u = u->next) {
if (visit[u->data] == 0){ /* 未確定の頂点の場合 */
if (exist(n, u->data)) { /* 探索リストnにある頂点の場合 */
if (dist[v]+u->dist < dist[u->data]) /* vを経由した方が短い */
in[u->data] = v; /* 1つ前をvに更新 */
/* より短い距離で、更新 */
dist[u->data] = less(dist[u->data], dist[v]+u->dist);
} else {
/* 探索リストにない頂点の場合は、追加。
また、vまでの距離+隣接距離を登録 */
insert(n,1,u->data,0);
in[u->data] = v; /* 1つ前 */
dist[u->data] = dist[v]+u->dist;
} /* if else 文 */
} /* if 文 */
} /* for ループ end */
} /* while ループ end */
free(n); /* nリストをフリー */
}
int main(void){
int i;
/* 頂点のidを1からとするので、i=0は使用しない */
for(i=1;i<N+1;i++){
Out[i]=create();
}
/* 隣接リスト(重み；距離つき)を、リスト構造に格納 */
/* 図6.7と問6.3のデータ。教科書には距離つきの図がない */
insert(Out[1],1,2,4); insert(Out[1],2,5,5);
insert(Out[2],1,3,9); insert(Out[2],2,5,6); insert(Out[2],3,6,2);
insert(Out[3],1,6,3);
insert(Out[4],1,1,3); insert(Out[4],2,5,2);
insert(Out[5],1,4,2); insert(Out[5],2,6,8);
insert(Out[6],1,3,3); insert(Out[6],2,7,5);
insert(Out[7],1,5,7); insert(Out[7],2,6,5);
/* 各頂点について、隣接リストの表示 */
for(i=1; i<N+1; i++){
printf("vertex%d\n", i);
printlist(Out[i]);
}
/* ダイクストラ法で、頂点1から、最短距離を求めよ*/
Dijkstra(1);
/* Freeするなら */
for(i=1; i<N+1; i++){
FreeData(Out[i]);
}
return(0);
}