Dijkstra法について

Question

実現したいこと

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

前提

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

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

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

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

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NODE_NUM 10 /* 総ノード数 */
#define MAX 9999 /* 無限大に相当する数 */

#define FLAG 0 /* Dijkstraのテストの場合は0に、シミュレーション評価を行う場合は1にする */

int main()
{
/* Dijkstraのアルゴリズム部分で必要な変数 */
  int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */
  int path[NODE_NUM]; /* 前ノード表 */
  int dist[NODE_NUM]; /* 距離を格納 */
  int chk[NODE_NUM]; /* 最短距離確定のフラグ */
  int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */
  int src, dest; /* 始点・終点ノード */
  int a, b, c, d, i, j;
  int fin; /* 未確定ノードが残っているかどうかのフラグ */
  FILE *fp; /* 距離の入ったファイルを示すポインタ */

  /* シミュレーション評価の部分で必要な変数 */
  int link[NODE_NUM][NODE_NUM]; /* リンク容量 */
  int bandwidth[NODE_NUM][NODE_NUM]; /* リンクの空き容量 */
  int miss; /* 呼損を表すフラグ */
  int success; /* 確立できた通信回数 */
  int sum_success; /* 確立できた通信回数の合計 */
  int sim_time; /* 評価の回数をカウント */



/*
距離行列の作成
*/
  for(i=0; i<NODE_NUM; i++){
    for(j=0; j<NODE_NUM; j++){
      graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */
      link[i][j] = -1; /* 接続されていないノード間のリンク容量を-1にする */
      if(i==j){graph[i][j] = 0; link[i][j] = -1;}/* そのノード自身への距離は0とし、リンク容量は-1とする */
    }
  }
  fp=fopen("./distance.txt", "r");
  while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */
    {
      graph[a][b]=c; /* 接続されているノード間の距離を設定 */
      graph[b][a]=c; /* 逆方向も等距離と仮定 */
      link[a][b]=d; /* 接続されているノード間のリンクを設定 */
      link[b][a]=d; /* 逆方向も同じ容量と仮定 */
    }
  fclose(fp);

/*
始点・終点ノードを標準入力から得る (評価の場合は、実行しない)
*/
  if (FLAG == 0){
    printf("Source Node?(0-%d)", NODE_NUM-1);
    fscanf(stdin, "%d", &src);
    printf("Destination Node?(0-%d)", NODE_NUM-1);
    fscanf(stdin, "%d", &dest);
  }

  if (FLAG == 1) srand((unsigned)time(NULL)); /* 乱数の初期化, これ以降、rand()で乱数を得ることができる */



/****************************/
/* シミュレーション評価開始 */
/****************************/

  success = 0; sum_success = 0; /* 評価指標を初期化 */
  for (sim_time=0; sim_time<1000; sim_time++){
    miss = 0; /* 空きリンクが存在しない場合のフラグをOFFにする */
    success = 0; /* 確立できた通信回数を初期化する */

    for (i=0; i<NODE_NUM; i++){ /* 全リンクの空き容量を初期状態に戻す */
      for (j=0; j<NODE_NUM; j++){

      }
    }



    while(miss == 0){ /* 呼損が発生するまで繰り返す*/
       /* 評価の場合、送受信ノードをランダムに決定 */
      if (FLAG == 1){
        /* ランダムに送受信ノードを決定 */


        printf("src=%d, dest=%d\n", src, dest); /* 送受信ノードを表示 */
        if (src==dest) printf("送受信ノードが一致している\n");
      }



      /****************************************/
      /* ここからdijkstraのアルゴリズムを記述 */
      /* 最初はこの部分を記述し、作成すること */
      /****************************************/

      /*
      初期化
      */
      for(i=0; i<NODE_NUM; i++){ /* 何も確定していない状態にする */
        dist[i] = MAX;
        chk[i] = 0;
        path[i] = NODE_NUM;
      }
      path[src] = src; /* 始点ノードへの経路上の前ノードはそれ自身とする */
      dist[src] = 0; /* 始点ノード自身への距離は0である */
      chk[src] = 1; /* 始点ノードへの最短距離は確定 */
      tmp_node = src; /* 始点ノードから探索を始める */
      fin = 0;


      /*
      経路探索
      */

      /* 2. 送信ノードに接続されている全てのノードについて、接続リンクの長さを送信ノードからの長さとする */
     for(i=0; i<NODE_NUM; i++){
       if(graph[src][i]==1){
         dist[i] =1;
         path[i] =src;
       }
     }



      /* 3. 送信ノードに接続されている全てのノードうち、最短の距離をもつノードを確定とする */

      for(i=0; i<NODE_NUM; i++){
       tmp_dist = MAX;
        if(graph[src][i]==1 && dist[i]<tmp_dist){
          tmp_dist = dist[i];
          tmp_node = i;
          chk[tmp_node] = 1;
        }
      }




      while(fin==0){ /* finフラグが立つまで繰り返す */
        /* 4.*/
        /* 確定したノードに接続している全てのノードについて */
        /* srcからtmp_nodeまでの距離とtmp_nodeから現在考えているノードiまでの距離を計算 */
        /* これまでの距離より短ければ */
        /* distとpathを更新する */

      for(j=0;j<NODE_NUM;j++){
         if(graph[src][tmp_node]+graph[tmp_node][j] < dist[j]){
           dist[j] = graph[src][tmp_node]+graph[tmp_node][j];
           path[j] = tmp_node;
         }
      }




        /* 5. まだ確定していないノードのうち、送信ノードからの距離が最短のノードを確定とする*/
    for(i=0;i<NODE_NUM;i++){
     for(j=0;j<NODE_NUM;j++){
       tmp_dist =MAX;
        if(chk[j]==0 && dist[j]<tmp_dist){
          dist[j] < dist[i];
          tmp_dist = dist[j];
          tmp_node = j;
          chk[tmp_node] = 1;
        }

       }
     }








        if(chk[dest] == 1) fin = 1; /* 終点ノードへの最短距離が確定したら終了 */
      }

      /*
      結果出力(Dijkstra作成時のみ実行する)
      */
      if(FLAG == 0){
        if(dist[dest]>=MAX){
          printf("No path from node%d to node%d.\n",src,dest);
        }else{
          printf("Shortest path from node%d to node%d is as follows.\n",src,dest);
          printf("%d <- ",dest);
          i=dest;
          for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */
            printf("%d <- ",i);
          }
          printf("%d\n",src);
          printf("Shortest distance is %d.\n", dist[dest]);
        }
        return 0; /* Dijkstraの作成時は結果を出力したらプログラムを終了する */
      }

      /************************************/
      /* ここまでがdijkstraのアルゴリズム */
      /************************************/

      /**********************************************************************/
      /* この下にdijkstraで決定した経路を評価するためのプログラムを記述する */
      /**********************************************************************/





    } /* while(1) */
}
}

試したこと

/* 2. 送信ノードに接続されている全てのノードについて、接続リンクの長さを送信ノードからの長さとする */

/* 3. 送信ノードに接続されている全てのノードうち、最短の距離をもつノードを確定とする */

/* 4./
/ 確定したノードに接続している全てのノードについて /
/ srcからtmp_nodeまでの距離とtmp_nodeから現在考えているノードiまでの距離を計算 /
/ これまでの距離より短ければ /
/ distとpathを更新する */

/* 5. まだ確定していないノードのうち、送信ノードからの距離が最短のノードを確定とする*/

それぞれこの後の部分のプログラムを作成するのですが、うまく実行することができません。
プログラムに不備の点などがありましたら教えていただきたいです。

補足情報（FW/ツールのバージョンなど）

Comments

[ozwk]

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

実行しているコードと見ているコードは同一ですか?

[jbpb0]

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

現状の質問のコードから、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]

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]

> これが、distance.txtなのですが

「distance.txt」の内容は、質問を編集して追記してください

> どのように活用すれば良いのでしょうか

コードをコンパイルしてから実行する際に、カレントディレクトリにあれば、読み込まれます
そのような意図でコードを書いたのではないのですか？
質問のコードは、質問者さんが書いたのですよね？

[jbpb0]

質問のコードをそのまま、当方の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では、一応エラーは出ず実行されました

Answer 1

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

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

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