ダイクストラの評価について

Question

実現したいこと

最小ホップ経路を用いた固定経路で、呼損率による評価を行う。

前提

通信の発生
ランダムに送受信ノードを決定する.

通信の確立
与えられた送受信ノード間の経路を決定し，その経路上のリンクの空き容量を 1Mbps だけ減少させる.ただし，経路上に空き容量のないリンクが存在する場合，この通信は確立しなかったものとして，何も行わない.

通信の終了
n 回前に発生した通信の経路上の空き容量を 1Mbps だけ増加させる.ただし，その通信が確立 していなかった場合には何も行わない.

呼損率の評価
10,000 回の通信を発生させ，そのうちで確立できなかった通信の割合(呼損率)を求める.

試行の繰り返し
パラメタ n を変化させながら，上記の試行を繰り返し行う.パラメタ n を変化させたときのグラフ・表を作成する。

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

,
,
,
「上記も続いている」
,
,
src=7, dest=4
src=5, dest=7
src=3, dest=5
src=0, dest=6
src=3, dest=7
src=0, dest=0
送受信ノードが一致している
src=2, dest=3
src=0, dest=0
送受信ノードが一致している
src=1, dest=9
src=4, dest=0
src=4, dest=3
src=9, dest=7
src=0, dest=7
src=4, dest=3
src=7, dest=5
何回前の通信の経路上の空き容量を増加させますか？: 3
3回前の情報はありません。

average = 0.141000

該当のソースコード

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

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

#define FLAG 1 /* 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++){
       link[i][j]= link[i][j];
      }
    }



    while(miss == 0){ /* 呼損が発生するまで繰り返す*/
       /* 評価の場合、送受信ノードをランダムに決定 */
      if (FLAG == 1){
        /* ランダムに送受信ノードを決定 */
        src = rand()%10;
        dest =  rand()%10;
        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] = graph[src][i];
         path[i] = src;
       }
     }



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

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


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

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




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

     dist[tmp_node] =MAX;
     for(i=0;i<NODE_NUM;i++){
        if(chk[i]==0 && dist[i]<dist[tmp_node]){
          dist[tmp_node] = dist[i];
          tmp_node = i;
        }
      }
      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で決定した経路を評価するためのプログラムを記述する */
      /**********************************************************************/

/*      2-(a) その経路上の全てのリンクに空き容量がある場合、それらを1Mbpsだけ
      減少させ、「確立できた通信回数」を1増やす
*/
     for(i=dest; i!=src; i=path[i]){
      if(bandwidth[i][path[i]] != 0){
        bandwidth[i][path[i]] -= 1;
        success += 1;
      }
    }



/*
      2-(b) その経路上に空き容量のないリンクが存在する場合、呼損とし、
      その時点までの「確立できた通信回数」をsum_successに足して、while文をbreakする
*/
    int lost =0;
    for(i=dest; i!=src; i=path[i]){
      if(bandwidth[i][path[i]] == 0){
      lost = 1;
      break;
     }
   }
    if(lost){
      sum_success += success;
      break;
    }


  }/* while(1) */
}/* 1～3の手続きを1000回行うためのfor文 */


int history[NODE_NUM] = {0};
int n;

printf("何回前の通信の経路上の空き容量を増加させますか？: ");
scanf("%d", &n);

if (n <= 0) {
    printf("通信が確立していません。\n");
    return 0;
}

if (n > NODE_NUM) {
    printf("%d回前の情報は記録されていません。\n", n);
    return 0;
}

// n回前の情報がある場合、容量を増加させる
if (history[n-1] > 0) {
  history[n-1] += 1;
  for (i = dest; i != src; i = path[i]) {
    if (bandwidth[i][path[i]] > 0) {
        bandwidth[i][path[i]] += 1;
    }
  }
    printf("%d回前の通信の経路上の空き容量を1Mbpsだけ増加させました。現在の容量は%dMbpsです。\n", n, bandwidth[i][path[i]]);
} else {
    printf("%d回前の情報はありません。\n", n);
}


/*
シミュレーション評価の結果出力
*/
    printf("\naverage = %f\n", sum_success / 1000.0);
/* 初めて呼損が起こるまでに確立できた通信回数の平均を表示 */
     return 0;
}

試したこと

何回前の通信の経路上の空き容量を増加させますか？の質問にどんな値を入れても、n回前の情報はありませんと表示されるのですが、評価ができているのか。
また、試行を繰り返してパラメタ n を変化させたときのグラフ・表を作成する方法がわからない。修正点があれば教えてください。

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

distance.txtの内容は
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

Comments

[jbpb0]

https://teratail.com/questions/0no3l7h4ij4pgf
とコードがよく似てますが、その質問をしたmidoriyaさんと質問者さん(programmingさん)は同一人物でしょうか？

[programming]

同一人物です。前のアカウントがログインできなくなってしまいました。

[actorbug]

正直、問題を解決するための手順を検討する前にコードを書いているように見えてしまいます。

int history[NODE_NUM] = {0};

上記コードを実行してから「history」に何も代入せずに

if (history[n-1] > 0) {

のような判定をしたら、「n回前の情報はありません。」と表示されるのは当たり前ではないでしょうか。

それ以外にも、以下のようにlinkにlinkを代入するという明らかに意味のないコードを書いていることも、最初の疑いを深める原因となっています。

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

[jimbe]

>評価ができているのか。

それを先ずはご自身で確認してください。
評価している箇所でその値を表示してみるとか出来ると思います。
それと、機能毎に関数化し、インデントを適切にしてください。
分かり易い読み易いコードは、バグが入り難く確認し易く修正し易いです、

[jbpb0]

> 同一人物です。

https://teratail.com/legal
の「第7条（禁止事項）」に書かれてるように、「複数のユーザーIDを1人で保有する行為」は禁止されてます

> 前のアカウントがログインできなくなってしまいました。

https://teratail.com/users/towawato
https://teratail.com/users/towa-wato
を見たら、アカウントを作成したのは同じ「2022/07/15」なので、
「ログインできなくなったから別のアカウントを作った」
のではないですよね