前提・実現したいこと
ダイクストラ法のアルゴリズムの理解を深めるために、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
6 0 2 10 999 999 999 2 0 2 7 8 999 10 2 0 4 5 999 999 7 4 0 999 3 999 8 5 999 0 1 999 999 999 3 1 0
C
#include <stdio.h> #include <stdlib.h> #include <string.h> #define NMAX 100 /*ノード数の上限*/ #define START 0 /*始点ノード*/ #define FALSE 0 #define TRUE 1 #define INT_MAX 999 /*無限大*/ int n; /*グラフのノード数*/ int weight[NMAX][NMAX]; /*辺の重み*/ /// <summary> /// 入力グラフの隣接行列を取り込む /// </summary> void ReadWeight() { FILE* fp; int i, j; fp = fopen("adjacency_matrix.txt", "r"); if (fp == NULL) { printf("file does not open\n"); exit(1); } fscanf(fp, "%d", &n); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { fscanf(fp, "%d", &weight[i][j]); } } fclose(fp); } int main() { char U[NMAX]; /*各ノードの距離が未確定かどうかを表す配列(0のとき確定、1のとき未確定)*/ int distance[NMAX]; /*各ノードへの距離を表す配列*/ int prev[NMAX]; /*各ノードの前のノードを表す配列*/ int min; /*最小のノード*/ int min_value; /*最小のノードまでの距離*/ int tmp_flag = 0; int flag = 0; /*未確定ノードが残っているかどうかのフラグ*/ /* 重みの読み込み & 配列の初期化 */ ReadWeight(); for (int i = 0; i < n; i++) { U[i] = TRUE; distance[i] = INT_MAX; prev[i] = FALSE; } distance[START] = 0; //始点から始点までの距離は0 min = START; /*ダイクストラ法*/ while (flag == 0) { // U[i]==1(各ノードの距離が未確定)であるノードの中でdistance[i]が最小となるノードを見つけ、そのノードをminとする。 min_value = INT_MAX; for (int i = 0; i < n; i++) { if ((U[i] == 1) && (distance[i] < min_value)) { min = i; min_value = distance[i]; } } // U[min]==0とする。->距離が最小となるノードを確定する。(看板にマジック書きをする) U[min] == FALSE; // ノードminからつながっているすべてのノードについて以下を行う。 // distance[i] > distance[min] + weight[min][i] かつ U[i]==1ならば、 // distance[i] = distance[min] + weight[min][i], prev[i]=minとする。 for (int i = 0; i < n; i++) { if ((U[i] == 1) && (distance[i] > (distance[min] + weight[min][i]))) //(鉛筆書きの看板に書かれた数の方が大きければ、看板の数値を書き換える) { distance[i] = distance[min] + weight[min][i]; prev[i] = min; } } //Uがすべて0なら終了する(0以外つまり1が見つかったらダイクストラ法をつづける) for (int i = 0; i < n; i++) { if (U[i] != FALSE) { tmp_flag = 1; break; } } if (tmp_flag == 0) { flag = 1; } } //表示 printf("点 直前の点 最短距離\n"); for (int i = 0; i < n; i++) { if (i != START) { printf("%2d %10d %10d\n", i, prev[i], distance[i]); } } return 0; }
試したこと
ソースファイル中のダイクストラ法を実際に行っている箇所にループ処理に問題があると考え、flagの設定を見直しましたがだめでした。
補足情報(FW/ツールのバージョンなど)
Visual Studio 2019 (C言語の実行環境)
まだ回答がついていません
会員登録して回答してみよう