STEP 6.3　ダイクストラ法 (最短距離)

• 上の文字列str中、２番目の動物を表示する。

#include "list1.h" /* リスト構造体の定義など */
#define N 7
List *Out[N+1];  /* 各頂点からの隣接情報ネットワーク。リスト配列の各要素はList 個数は0から始まらないのでN+1にする */

int less(int a, int b); /* min関数をless関数という名前にしておきます */
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;
   int visit[N+1], dist[N+1]; /* 各配列頂点nについて、確定済情報、最短距離 */
   List *n, *w, *u; /* nは探索中リスト(重要）   wは探索リスト操作用ポインター    uは隣接OUT リスト操作用ポインター */

   for(i = 0 ; i < N+1; i++) { /* 最短距離確定情報、全ての頂点を0に */
      visit[i] = 0; /* 0は確定していないことを表す */
   }

   n=create();　/* 空リストを生成 */
   insert(n, 1, v0, 0); /* v0は、Dijksyra関数の引数。つまり、スタートの頂点。n の先頭には、スタート頂点。距離は使用しないので、0 */
   dist[v0] = 0; /* v0自身からの距離は、当然0 */

   while (!empty(n)) { /* 教科書ではempty_l 探索リストがなくなるまで */
      m = 9999; /* 比較のため、ありえない値を暫定最小距離にする */

      i = 1; /* nリストのカウンタ。何番目の要素か */
      /* 現状の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を更新 */
            j=i;                 /* 暫定一位になっている頂点のnリスト内の位置を記録 */
         }
         i++; /* リスト内の位置カウンターをインクリメント */
      }

     /* 確定した最小値について */
      visit[v] = 1; /* visit配列に、確定を記録 1は確定したことを表す。*/
      delete(n,j);  /* 探索リストnから、最小確定したj番目の頂点をdelete */
      printf("%d -> %d : %d\n", v0, v, dist[v]); /* ここで、確定情報を毎回プリント */

      /* 確定した頂点vから、ひとつ先の頂点の情報で、全体情報を更新 */
      for (u = Out[v]->next; u != NULL; u = u->next) {
         if (visit[u->data] == 0){ /* 未確定の頂点の場合 */
            if (exist(n, u->data)) { /* 探索リストnにある頂点の場合 */
               /* より短い距離で、更新 */
               dist[u->data] = less(dist[u->data], dist[v]+u->dist);
            } else {
               /* 探索リストにない頂点の場合は、追加。
                  また、vまでの距離+隣接距離を登録 */
               insert(n,1,u->data,0); /* 距離メンバーは使用しないので、0にしておく */
               dist[u->data] = dist[v]+u->dist;
            }
         }
      } /* 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);
}