Q&A
VisualStudio は単にそれを使用されているというだけで、 (VisualStudio を使っていなくてもこの問題は発生するという意味で ) ご質問自体には関係無いように思います。
タグは外されたほうが良いのではないでしょうか。
前提・実現したいこと
ダイクストラ法のアルゴリズムの理解を深めるために、C言語でテキストファイル（隣接行列）を入力としたダイクストラ法のプログラムを実装したいです。
以下のある大学のサイト(pdf)を参考に作成したのですが、意図した結果になりません。
hama08_ho.pdf
どの箇所が誤っているのかご指摘いただければ幸いです。
なお、ソースファイル中に記述されている「看板」や「マジック」というのは、
以下のオペレーションズ・リサーチ学会のサイト(pdf)の4ページでダイクストラ法の理解を参考にしたためです。
or54-12_730.pdf
発生している問題
図1 my_dijkstra.cの実行結果
図2 答え
図3 adjacency_matrix.txtのグラフ
追記1（Cプログラム更新）
whileループ文が抜けていたため、挿入したのですが、ループから抜け出せなくなってしまいました。原因を究明中です。
テキストファイルadjacency_matrix.txtを読み込むと、図2のような結果になるはずですが自作したプログラムは無限ループから抜け出せなくなってしまいました。
該当のソースコード
txt
16 20 2 10 999 999 999 32 0 2 7 8 999 410 2 0 4 5 999 5999 7 4 0 999 3 6999 8 5 999 0 1 7999 999 999 3 1 0
C
1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4 5#define NMAX 100 /*ノード数の上限*/ 6#define START 0 /*始点ノード*/ 7#define FALSE 0 8#define TRUE 1 9#define INT_MAX 999 /*無限大*/ 10 11int n; /*グラフのノード数*/ 12int weight[NMAX][NMAX]; /*辺の重み*/ 13 14 15/// <summary> 16/// 入力グラフの隣接行列を取り込む 17/// </summary> 18void ReadWeight() 19{ 20 FILE* fp; 21 int i, j; 22 fp = fopen("adjacency_matrix.txt", "r"); 23 if (fp == NULL) 24 { 25 printf("file does not open\n"); 26 exit(1); 27 } 28 29 fscanf(fp, "%d", &n); 30 for (i = 0; i < n; i++) 31 { 32 for (j = 0; j < n; j++) 33 { 34 fscanf(fp, "%d", &weight[i][j]); 35 } 36 } 37 fclose(fp); 38} 39 40 41int main() 42{ 43 char U[NMAX]; /*各ノードの距離が未確定かどうかを表す配列(0のとき確定、1のとき未確定)*/ 44 int distance[NMAX]; /*各ノードへの距離を表す配列*/ 45 int prev[NMAX]; /*各ノードの前のノードを表す配列*/ 46 int min; /*最小のノード*/ 47 int min_value; /*最小のノードまでの距離*/ 48 int tmp_flag = 0; 49 int flag = 0; /*未確定ノードが残っているかどうかのフラグ*/ 50 51 /* 重みの読み込み & 配列の初期化 */ 52 ReadWeight(); 53 for (int i = 0; i < n; i++) 54 { 55 U[i] = TRUE; 56 distance[i] = INT_MAX; 57 prev[i] = FALSE; 58 } 59 distance[START] = 0; //始点から始点までの距離は0 60 min = START; 61 62 /*ダイクストラ法*/ 63 while (flag == 0) 64 { 65 // U[i]==1(各ノードの距離が未確定)であるノードの中でdistance[i]が最小となるノードを見つけ、そのノードをminとする。 66 min_value = INT_MAX; 67 for (int i = 0; i < n; i++) 68 { 69 if ((U[i] == 1) && (distance[i] < min_value)) 70 { 71 min = i; 72 min_value = distance[i]; 73 } 74 } 75 76 // U[min]==0とする。->距離が最小となるノードを確定する。（看板にマジック書きをする） 77 U[min] == FALSE; 78 79 // ノードminからつながっているすべてのノードについて以下を行う。 80 // distance[i] > distance[min] + weight[min][i] かつ U[i]==1ならば、 81 // distance[i] = distance[min] + weight[min][i], prev[i]=minとする。 82 for (int i = 0; i < n; i++) 83 { 84 if ((U[i] == 1) && (distance[i] > (distance[min] + weight[min][i]))) //（鉛筆書きの看板に書かれた数の方が大きければ、看板の数値を書き換える） 85 { 86 distance[i] = distance[min] + weight[min][i]; 87 prev[i] = min; 88 } 89 } 90 91 //Uがすべて0なら終了する(0以外つまり1が見つかったらダイクストラ法をつづける) 92 for (int i = 0; i < n; i++) 93 { 94 if (U[i] != FALSE) 95 { 96 tmp_flag = 1; 97 break; 98 } 99 } 100 if (tmp_flag == 0) 101 { 102 flag = 1; 103 } 104 } 105 106 //表示 107 printf("点 直前の点 最短距離\n"); 108 for (int i = 0; i < n; i++) 109 { 110 if (i != START) 111 { 112 printf("%2d %10d %10d\n", i, prev[i], distance[i]); 113 } 114 } 115 116 return 0; 117}
試したこと
ソースファイル中のダイクストラ法を実際に行っている箇所にループ処理に問題があると考え、flagの設定を見直しましたがだめでした。
補足情報（FW/ツールのバージョンなど）
Visual Studio 2019 (C言語の実行環境)
回答1件
0
ベストアンサー
アルゴリズムは分かりませんが、
c
1// U[min]==0とする。->距離が最小となるノードを確定する。（看板にマジック書きをする） 2U[min] == FALSE;
U[min] を FALSE にするというのであれば "==" では無く "=" ではないでしょうか。
また、 tmp_flag は一度 1 になると二度と 0 にはならないと思います。
tmp_flag と flag は 0/1 が逆なだけで同じ意味のようですので、それも含めて直されては如何でしょうか。
データを直接持って直してみました。
c
1#include <stdio.h> 2 3#define NMAX 100 /*ノード数の上限*/ 4#define START 0 /*始点ノード*/ 5#define INT_MAX 999 /*無限大*/ 6 7int n = 6; /*グラフのノード数*/ 8int weight[6][6] = { /*辺の重み*/ 9 { 0, 2, 10,999,999,999}, 10 { 2, 0, 2, 7, 8,999}, 11 { 10, 2, 0, 4, 5,999}, 12 {999, 7, 4, 0,999, 3}, 13 {999, 8, 5,999, 0, 1}, 14 {999,999,999, 3, 1, 0}, 15}; 16 17typedef struct { 18 int confirmed; //距離が確定かどうか 19 int distance; //距離 20 int prev; //前のノード 21} Node; 22 23void initNodes(Node node[], int n) { 24 for(int i=0; i<n; i++) { 25 node[i].confirmed = 0; 26 node[i].distance = INT_MAX; 27 node[i].prev = 0; 28 } 29} 30 31/*全て確定(TRUE)なら TRUE, それ以外は FALSE */ 32int allConfirmed(Node node[], int n) { 33 for(int i=0; i<n; i++) { 34 if(!node[i].confirmed) return 0; 35 } 36 return !0; 37} 38 39/* 距離が未確定であるノードの中で距離が最小となるノードを見つけ、そのindexを返す */ 40int findShortestDistance(Node node[], int n) { 41 int index = 0; 42 for(int i=0, distance=INT_MAX; i<n; i++) { 43 if(!node[i].confirmed && node[i].distance < distance) { 44 index = i; 45 distance = node[i].distance; 46 } 47 } 48 return index; 49} 50 51// ノードminからつながっているすべてのノードについて以下を行う。 52// distance[i] > distance[min] + weight[min][i] かつ未確定ならば、 53// distance[i] = distance[min] + weight[min][i], prev[i]=minとする。 54void setDistanceFromMin(Node node[], int n, int min) { 55 for(int i=0; i<n; i++) { 56 int distance = node[min].distance + weight[min][i]; 57 if(!node[i].confirmed && node[i].distance > distance) { 58 //（鉛筆書きの看板に書かれた数の方が大きければ、看板の数値を書き換える） 59 node[i].distance = distance; 60 node[i].prev = min; 61 } 62 } 63} 64 65//表示 66void print(Node node[], int n, int start) { 67 printf("点 直前の点 最短距離\n"); 68 for(int i=0; i<n; i++) { 69 if(i != START) { 70 printf("%2d %10d %10d\n", i, node[i].prev, node[i].distance); 71 } 72 } 73} 74 75int main() { 76 Node node[NMAX]; 77 78 /* 配列の初期化 */ 79 initNodes(node, n); 80 81 int min = START; 82 node[START].confirmed = !0; 83 node[START].distance = 0; //始点から始点までの距離は0 84 85 /*ダイクストラ法*/ 86 do { 87 // ノードminからつながっているすべてのノードについて距離を設定する 88 setDistanceFromMin(node, n, min); 89 90 // 距離が未確定であるノードの中でdistanceが最小となるノードを見つけ、そのノードをminとする 91 min = findShortestDistance(node, n); 92 93 //距離が最小となるノードを確定する。（看板にマジック書きをする） 94 node[min].confirmed = !0; 95 96 } while(!allConfirmed(node, n)); 97 98 //表示 99 print(node, n, START); 100 101 return 0; 102}
投稿2022/01/25 03:45
編集2022/01/25 10:21総合スコア13170
ご回答いただき、ありがとうございます。
ご指摘の通り、U[min] = 0 の箇所とtmp_flagが0に戻っていない箇所を修正したところ意図した結果がでました。今後はこのようなミスも自力であぶり出せるようになっていきたいです。
また、構造体や関数を用いて改良されたプログラムもありがとうございます。参考にさせていただきます。（まだまだ私はmain関数にべた書きしてしまいますので・・・）
あなたの回答
tips
プレビュー
