Dijkstra法について

実現したいこと

ダイクストラ法の実装プログラムの作成

前提

自分でダイクストラ法のプログラムを作成してみたのですが、うまく実行できません。

発生している問題・エラーメッセージ

エラーメッセージが表示されることなく、ダイクストラの計算も実行されずにプログラムが終了してしまう。

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/ツールのバージョンなど）

ozwk

2023/04/26 00:28

dist[j] < dist[i]; という行に警告が出ていますが、質問文のコードにそのような箇所は見当たりません。実行しているコードと見ているコードは同一ですか?

jbpb0

2023/04/26 00:53 編集

> エラーメッセージが表示されることなく、ダイクストラの計算も実行されずにプログラムが終了現状の質問のコードから、jimbeさんが回答で指摘してる > main 関数の範囲を示す 11 行目の { に対応する } がありません。を直して(コードの一番最後に「}」を追加)、他はそのままで、当方のmacのgcc (Apple clang version 14.0.0)でコンパイルしたら「a.out」ができたので、 ./a.out で実行したら、「Segmentation fault: 11」になりました【追記】「Segmentation fault: 11」になったのは、「distance.txt」が存在しない状態で実行したからのようです「distance.txt」とは、どのような内容のファイルでしょうか？

midoriya

2023/04/26 16:05

0 1 1 3 0 3 1 3 1 2 1 3 1 3 1 4 2 4 1 4 2 5 1 3 3 4 1 5 3 7 1 3 4 5 1 5 4 7 1 4 5 6 1 3 5 8 1 4 6 8 1 3 7 8 1 4 7 9 1 3 8 9 1 3 これが、distance.txtなのですが、どのように活用すれば良いのでしょうか

jbpb0

2023/04/27 11:40

> これが、distance.txtなのですが「distance.txt」の内容は、質問を編集して追記してください > どのように活用すれば良いのでしょうかコードをコンパイルしてから実行する際に、カレントディレクトリにあれば、読み込まれますそのような意図でコードを書いたのではないのですか？質問のコードは、質問者さんが書いたのですよね？

jbpb0

2023/04/27 23:42 編集

質問のコードをそのまま、当方のmacのgcc (Apple clang version 14.0.0)で gcc -O2 ソースコードのファイル名でコンパイルしたら、「a.out」ができました質問者さんのコメントの内容の「distance.txt」を作って、「a.out」がある場所(ディレクトリパス)に置きましたターミナルで、カレントディレクトリを「a.out」と「distance.txt」がある場所にしてから ./a.out で実行したら、 Source Node?(0-9) と表示されたので、「0」を入力(実際に入力したのは数字だけ)してリターンキーを入力したら、 Destination Node?(0-9) と表示されたので、「1」を入力(実際に入力したのは数字だけ)してリターンキーを入力したら、 Shortest path from node0 to node1 is as follows. 1 <- 0 Shortest distance is 1. と表示されました > エラーメッセージが表示されることなく、ダイクストラの計算も実行されずにプログラムが終了上記の結果が、ちゃんと「ダイクストラの計算」がされた結果なのかは分かりませんが、当方のmacでは、一応エラーは出ず実行されました