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

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

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

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

解決済

C言語によるダイクストラ法の実装

noukanokurashi
noukanokurashi

総合スコア3

C

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

1回答

0評価

0クリップ

1041閲覧

投稿2022/01/25 02:37

編集2022/01/26 12:25

前提・実現したいこと

ダイクストラ法のアルゴリズムの理解を深めるために、C言語でテキストファイル(隣接行列)を入力としたダイクストラ法のプログラムを実装したいです。
以下のある大学のサイト(pdf)を参考に作成したのですが、意図した結果になりません。
hama08_ho.pdf

どの箇所が誤っているのかご指摘いただければ幸いです。

なお、ソースファイル中に記述されている「看板」や「マジック」というのは、
以下のオペレーションズ・リサーチ学会のサイト(pdf)の4ページでダイクストラ法の理解を参考にしたためです。
or54-12_730.pdf

発生している問題

my_dijkstra.cの実行結果
図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言語の実行環境)

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

jimbe

2022/01/25 08:07

VisualStudio は単にそれを使用されているというだけで、 (VisualStudio を使っていなくてもこの問題は発生するという意味で ) ご質問自体には関係無いように思います。 タグは外されたほうが良いのではないでしょうか。
noukanokurashi

2022/01/26 03:08

了解いたしました。外しておきます。

まだ回答がついていません

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

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

同じタグがついた質問を見る

C

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。