質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

1回答

1120閲覧

Dijkstra法について

towawato

総合スコア1

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2023/04/25 15:43

編集2023/04/26 16:00

実現したいこと

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

前提

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

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

エラーメッセージが表示されることなく、ダイクストラの計算も実行されずにプログラムが終了してしまう。 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/ツールのバージョンなど)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

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」とは、どのような内容のファイルでしょうか?
towawato

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では、一応エラーは出ず実行されました
guest

回答1

0

アルゴリズムうんぬんでは無く、コンパイルエラーです。エラーメッセージをしっかり理解して、コードを修正してください。

ブロックコメントの開始 /* と終了 */ の対応がちゃんと取れていない所があるため次のコメントブロックの開始 /* がコメントブロック内に現れる形になってしまっています。
コメントブロック内に /* は書けません。

また、main 関数の範囲を示す 11 行目の { に対応する } がありません。

投稿2023/04/25 16:08

編集2023/04/25 16:19
jimbe

総合スコア12870

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問