実現したいこと
ダイクストラ法の実装プログラムの作成
前提
自分でダイクストラ法のプログラムを作成してみたのですが、うまく実行できません。
発生している問題・エラーメッセージ
エラーメッセージが表示されることなく、ダイクストラの計算も実行されずにプログラムが終了してしまう。 gcc Dijkstra1.c ^[[ADijkstra1.c:166:19: warning: relational comparison result unused [-Wunused-comparison] dist[j] < dist[i]; ~~~~~~~~^~~~~~~~~ 1 warning generated. % ./a.out zsh: segmentation fault ./a.out
該当のソースコード
C言語
1#include <stdio.h> 2#include <stdlib.h> 3#include <time.h> 4 5#define NODE_NUM 10 /* 総ノード数 */ 6#define MAX 9999 /* 無限大に相当する数 */ 7 8#define FLAG 0 /* Dijkstraのテストの場合は0に、シミュレーション評価を行う場合は1にする */ 9 10int main() 11{ 12/* Dijkstraのアルゴリズム部分で必要な変数 */ 13 int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */ 14 int path[NODE_NUM]; /* 前ノード表 */ 15 int dist[NODE_NUM]; /* 距離を格納 */ 16 int chk[NODE_NUM]; /* 最短距離確定のフラグ */ 17 int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */ 18 int src, dest; /* 始点・終点ノード */ 19 int a, b, c, d, i, j; 20 int fin; /* 未確定ノードが残っているかどうかのフラグ */ 21 FILE *fp; /* 距離の入ったファイルを示すポインタ */ 22 23 /* シミュレーション評価の部分で必要な変数 */ 24 int link[NODE_NUM][NODE_NUM]; /* リンク容量 */ 25 int bandwidth[NODE_NUM][NODE_NUM]; /* リンクの空き容量 */ 26 int miss; /* 呼損を表すフラグ */ 27 int success; /* 確立できた通信回数 */ 28 int sum_success; /* 確立できた通信回数の合計 */ 29 int sim_time; /* 評価の回数をカウント */ 30 31 32 33/* 34距離行列の作成 35*/ 36 for(i=0; i<NODE_NUM; i++){ 37 for(j=0; j<NODE_NUM; j++){ 38 graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */ 39 link[i][j] = -1; /* 接続されていないノード間のリンク容量を-1にする */ 40 if(i==j){graph[i][j] = 0; link[i][j] = -1;}/* そのノード自身への距離は0とし、リンク容量は-1とする */ 41 } 42 } 43 fp=fopen("./distance.txt", "r"); 44 while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */ 45 { 46 graph[a][b]=c; /* 接続されているノード間の距離を設定 */ 47 graph[b][a]=c; /* 逆方向も等距離と仮定 */ 48 link[a][b]=d; /* 接続されているノード間のリンクを設定 */ 49 link[b][a]=d; /* 逆方向も同じ容量と仮定 */ 50 } 51 fclose(fp); 52 53/* 54始点・終点ノードを標準入力から得る (評価の場合は、実行しない) 55*/ 56 if (FLAG == 0){ 57 printf("Source Node?(0-%d)", NODE_NUM-1); 58 fscanf(stdin, "%d", &src); 59 printf("Destination Node?(0-%d)", NODE_NUM-1); 60 fscanf(stdin, "%d", &dest); 61 } 62 63 if (FLAG == 1) srand((unsigned)time(NULL)); /* 乱数の初期化, これ以降、rand()で乱数を得ることができる */ 64 65 66 67/****************************/ 68/* シミュレーション評価開始 */ 69/****************************/ 70 71 success = 0; sum_success = 0; /* 評価指標を初期化 */ 72 for (sim_time=0; sim_time<1000; sim_time++){ 73 miss = 0; /* 空きリンクが存在しない場合のフラグをOFFにする */ 74 success = 0; /* 確立できた通信回数を初期化する */ 75 76 for (i=0; i<NODE_NUM; i++){ /* 全リンクの空き容量を初期状態に戻す */ 77 for (j=0; j<NODE_NUM; j++){ 78 79 } 80 } 81 82 83 84 while(miss == 0){ /* 呼損が発生するまで繰り返す*/ 85 /* 評価の場合、送受信ノードをランダムに決定 */ 86 if (FLAG == 1){ 87 /* ランダムに送受信ノードを決定 */ 88 89 90 printf("src=%d, dest=%d\n", src, dest); /* 送受信ノードを表示 */ 91 if (src==dest) printf("送受信ノードが一致している\n"); 92 } 93 94 95 96 /****************************************/ 97 /* ここからdijkstraのアルゴリズムを記述 */ 98 /* 最初はこの部分を記述し、作成すること */ 99 /****************************************/ 100 101 /* 102 初期化 103 */ 104 for(i=0; i<NODE_NUM; i++){ /* 何も確定していない状態にする */ 105 dist[i] = MAX; 106 chk[i] = 0; 107 path[i] = NODE_NUM; 108 } 109 path[src] = src; /* 始点ノードへの経路上の前ノードはそれ自身とする */ 110 dist[src] = 0; /* 始点ノード自身への距離は0である */ 111 chk[src] = 1; /* 始点ノードへの最短距離は確定 */ 112 tmp_node = src; /* 始点ノードから探索を始める */ 113 fin = 0; 114 115 116 /* 117 経路探索 118 */ 119 120 /* 2. 送信ノードに接続されている全てのノードについて、接続リンクの長さを送信ノードからの長さとする */ 121 for(i=0; i<NODE_NUM; i++){ 122 if(graph[src][i]==1){ 123 dist[i] =1; 124 path[i] =src; 125 } 126 } 127 128 129 130 /* 3. 送信ノードに接続されている全てのノードうち、最短の距離をもつノードを確定とする */ 131 132 for(i=0; i<NODE_NUM; i++){ 133 tmp_dist = MAX; 134 if(graph[src][i]==1 && dist[i]<tmp_dist){ 135 tmp_dist = dist[i]; 136 tmp_node = i; 137 chk[tmp_node] = 1; 138 } 139 } 140 141 142 143 144 while(fin==0){ /* finフラグが立つまで繰り返す */ 145 /* 4.*/ 146 /* 確定したノードに接続している全てのノードについて */ 147 /* srcからtmp_nodeまでの距離とtmp_nodeから現在考えているノードiまでの距離を計算 */ 148 /* これまでの距離より短ければ */ 149 /* distとpathを更新する */ 150 151 for(j=0;j<NODE_NUM;j++){ 152 if(graph[src][tmp_node]+graph[tmp_node][j] < dist[j]){ 153 dist[j] = graph[src][tmp_node]+graph[tmp_node][j]; 154 path[j] = tmp_node; 155 } 156 } 157 158 159 160 161 /* 5. まだ確定していないノードのうち、送信ノードからの距離が最短のノードを確定とする*/ 162 for(i=0;i<NODE_NUM;i++){ 163 for(j=0;j<NODE_NUM;j++){ 164 tmp_dist =MAX; 165 if(chk[j]==0 && dist[j]<tmp_dist){ 166 dist[j] < dist[i]; 167 tmp_dist = dist[j]; 168 tmp_node = j; 169 chk[tmp_node] = 1; 170 } 171 172 } 173 } 174 175 176 177 178 179 180 181 182 if(chk[dest] == 1) fin = 1; /* 終点ノードへの最短距離が確定したら終了 */ 183 } 184 185 /* 186 結果出力(Dijkstra作成時のみ実行する) 187 */ 188 if(FLAG == 0){ 189 if(dist[dest]>=MAX){ 190 printf("No path from node%d to node%d.\n",src,dest); 191 }else{ 192 printf("Shortest path from node%d to node%d is as follows.\n",src,dest); 193 printf("%d <- ",dest); 194 i=dest; 195 for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */ 196 printf("%d <- ",i); 197 } 198 printf("%d\n",src); 199 printf("Shortest distance is %d.\n", dist[dest]); 200 } 201 return 0; /* Dijkstraの作成時は結果を出力したらプログラムを終了する */ 202 } 203 204 /************************************/ 205 /* ここまでがdijkstraのアルゴリズム */ 206 /************************************/ 207 208 /**********************************************************************/ 209 /* この下にdijkstraで決定した経路を評価するためのプログラムを記述する */ 210 /**********************************************************************/ 211 212 213 214 215 216 } /* while(1) */ 217} 218}
試したこと
/* 2. 送信ノードに接続されている全てのノードについて、接続リンクの長さを送信ノードからの長さとする */
/* 3. 送信ノードに接続されている全てのノードうち、最短の距離をもつノードを確定とする */
/* 4./
/ 確定したノードに接続している全てのノードについて /
/ srcからtmp_nodeまでの距離とtmp_nodeから現在考えているノードiまでの距離を計算 /
/ これまでの距離より短ければ /
/ distとpathを更新する */
/* 5. まだ確定していないノードのうち、送信ノードからの距離が最短のノードを確定とする*/
それぞれこの後の部分のプログラムを作成するのですが、うまく実行することができません。
プログラムに不備の点などがありましたら教えていただきたいです。
補足情報(FW/ツールのバージョンなど)
