有向グラフに関するプログラムについて

[ＲＯＹ]

有向グラフに関するプログラムを作成中です。
このプログラムを改良して、入力のstartを0からfor文で回して、start及びendの双方向にルートを持つ(その判定はmsc関数で判定)グラフを格納し、随時新たに双方向にルートを持つグラフを探すプログラムしにたいと考えています。startとendを固定してルートを一つ見つけるところまではできたのですが、新たに次のルートを探すという段階でつまずいております。
どなたかアドバイスをくれたら、と思います。分かりにくい説明ですみませんがどなたかお願いします。

コード:

#include <stdio.h>
#define N 9   //node
#define INF 10000 //infinity
#define TRUE 1
#define FALSE 0

int dijkstra(int start,int end,int arg_edge[N][N])
{
  int i,j; 
  int used[N]; //Committed node
  int cost[N];  //shortest distance to node
  int prv[N];  //next node
  int next; //next nodes
  int dmin; //shortest distanc
  int test; //test
  int hit;  //new shortest distanc

  for(i=0;i<N;i++) {
	cost[i] = INF;
	prv[i] = INF;
	used[i] = FALSE;
  }

  cost[start] = FALSE; 
  next = start;
  
  do{
	i = next;
	for(j=0,dmin=INF;j<N;j++) {
      if(!used[j] && cost[j] < dmin) {
        dmin = cost[j];
        i = j;
      }
    }
    if(dmin==INF) break;
    used[i] = TRUE;
    dmin = INF;
    for(j=0;j<N;j++) {
      if(j == i ) continue;
      if(arg_edge[i][j]==INF) continue;
      if(used[j]==TRUE) continue;
      test = cost[i] + arg_edge[i][j];
      if(test < cost[j]) {
        cost[j] = test;
        prv[j] = i;
        if(test < dmin) {
          dmin = test;
          next = j;
        }
      }
    }
    hit = 1;
  } while(hit);

  return cost[end];
}

int msc(int start, int end, int arg_edge[][N]){
  int r = 0;
  if(dijkstra(start,end,arg_edge)<INF && dijkstra(end,start,arg_edge)<INF){
  r = 1;
  }
  return r;
  }

int main(){ 
  int i,j,r;
  int dmin;    //shortest distance
  int start,end;     //start,goal
  int edge[N][N]; //path

  for(i=0; i<N; i++){
	for(j=0; j<N; j++){
	  edge[i][j] = INF;
	}
  }

  edge[0][1] = 1;
  edge[1][2] = 1;
  edge[2][4] = 1;
  edge[2][8] = 1;
  edge[3][4] = 1;
  edge[4][6] = 1; 
  edge[5][7] = 1;
  edge[6][7] = 1;
  edge[7][0] = 1;
  edge[8][4] = 1;

  printf("        "); 
  scanf("%d",&start);
  printf("        "); 
  scanf("%d",&end);

  dmin = dijkstra(start,end,edge);
  printf("dmin=%d\n",dmin);

  r =  msc(start,end,edge);
  printf("%d\n", r);

  return  0;
}

[sleep]

質問内容がよく分からないですね（汗）
いえ、私も読解力が無いのです。申し訳ないです。

以下のサイトの図を例にして説明できますか？
http://i.wikiwiki.jp/kut-pg/?plugin=ref ... Graph2.png
例えば、この図だと 0 がスタート、4 がゴールです。
それを 4 がスタート、1 をゴールとした場合、最短ルートは 4 → 2 → 1 です。
しかし、1 ⇔ 2 間のコストを 1 → 2 は 4 のまま、2 → 1 は 6 とした場合
最短ルートは 4 → 2 → 3 → 0 → 1 となります。
その状態のまま、逆に 1 がスタート、4 をゴールとした場合は
1 → 2 間のコストは 4 のままなので、最短ルートは 1 → 2 → 4 となります。

「双方向にルートを持つグラフを探すプログラム」というのは
この 1 ⇔ 2 間のように進む方向によってコストが変わる状態を含んでのルート検索のことでしょうか？


仮にもし、そうだとすると
Googleで dijkstra c などの検索ワードで検索するとトップ近辺に出てくると思いますが
http://www.algolist.com/code/c/Dijkstra%27s_algorithm
辺りが参考になるかと思います。
このコードなら、少し変更を加えるだけで上記の条件を満たすコードにできます。
任意のスタート地点から検索できるようにするには、shortpath関数にスタート地点を与えてあげれる様に変更し、current変数の初期値としてそのスタート地点を設定すれば良いです。
（distance[0]=0;はdistance[current]=0;とし、current=0;は消してしまってもかまいません）
あと、最短ルートについてはpreced配列の初期化を変更してあげるだけで、逆方向ではありますがゴールからスタートへと一方向リストの様に最短ルートを辿れる配列にできます。

ROYさんのコードの場合、修正を加えるにはもう少し整理してからの方が良いかもしれないですね。
dijkstra法のコードではcontinueはまず出てこないはずですね。
恐らく、その分余計な処理をしてしまっていて把握が難しいコードになっているのではないかと思います。

[ROY]

説明不足で申し訳ありません。

私が考えてる有向グラフの場合、矢印でつながれていればコスト１としてコストは均一で１となっています。
この掲示板のお力添えもあり、有向グラフに対してstartとendを入力して最短経路を求めるプログラムまでは完成しました。
次の段階として、startとendでとり得る組み合わせをすべて試し、その各々がstartとendを逆にしてもルートはあるか？(このときコストは変わってしまっても大丈夫です、)
また逆ルートがあるならばそれstartをi、endをjと、その逆ルートをn_mscとして格納してきたいと考えています。

そこでソースコードの68～88行目の構造体のプログラムがうまく組めず、困っています。
説明が下手で分かりにくいところがあるかもしれませんが、アドバイスお願いします。

コード:

#include <stdio.h>
#define N 9   //頂点数
#define INF 10000
#define TRUE 1
#define FALSE 0

int dijkstra(int start,int end,int arg_edge[N][N])  //最短経路の確定
{
  int i,j; 
  int used[N]; //使用済頂点
  int cost[N];  //頂点へのコスト
  int prv[N];  //次の頂点
  int next; //次の頂点候補
  int dmin; //最短経路コスト
  int test;
  int hit;

  for(i=0; i<N; i++) {
	cost[i] = INF;
	prv[i] = INF;
	used[i] = FALSE;
  }

  cost[start] = FALSE; 
  next = start;
  
  do{
	i = next;
	for(j=0,dmin=INF;j<N;j++) {
      if(!used[j] && cost[j] < dmin) {
        dmin = cost[j];
        i = j;
      }
    }
    if(dmin == INF) break;
    used[i] = TRUE;
    dmin = INF;
    for(j=0; j<N; j++) {
      if(j == i ) continue;
      if(arg_edge[i][j] == INF) continue;
      if(used[j] == TRUE) continue;
      test = cost[i] + arg_edge[i][j];
      if(test < cost[j]) {
        cost[j] = test;
        prv[j] = i;
        if(test < dmin) {
          dmin = test;
          next = j;
        }
      }
    }
    hit = 1;
  } while(hit);

  return cost[end];
}

int check_msc(int start, int end, int arg_edge[][N])  //mscかの確認
{
  int r = 0;
  if(dijkstra(start,end,arg_edge)<INF && dijkstra(end,start,arg_edge)<INF){
	r = TRUE;
  }
  return r;
}


struct msc  //構造体の型宣言
{
  int start;
  int end;
}n_msc[N*(N-1)/2];


int stack_msc
{
  n_msc = 0;
  for(i=0; i<N; i++){
	for(j=i+1; j<N; j++){
	  if(check_msc[i][j] == TRUE){
		msc[n_msc].start = i;
		msc[n_msc].end = j;
		n_msc++;
	  }	
	}
  }
  return n_msc;
}


int main()
{ 
  int i,j,r;
  int dmin;    //最短距離コスト
  int start,end;     //出発と到着
  int edge[N][N]; //グラフ情報
  int n_msc; //mscの格納ナンバー

  for(i=0; i<N; i++){    //グラフのパス情報
	for(j=0; j<N; j++){
	  edge[i][j] = INF;
	}
  }

  edge[0][1] = 1;
  edge[1][2] = 1;
  edge[2][4] = 1;
  edge[2][8] = 1;
  edge[3][4] = 1;
  edge[4][6] = 1; 
  edge[5][7] = 1;
  edge[6][7] = 1;
  edge[7][0] = 1;
  edge[8][4] = 1;

  for(start=0; start<N; start++){
	for(end=start+1; end<N; end++) {
	  printf("strat=%d end=%d\n",start,end);
	  
	  dmin = dijkstra(start,end,edge);
	  printf("dmin = %d\n",dmin);
	  
	  r =  check_msc(start,end,edge);
	  printf("r = %d\n", r);
	}

	n_msc = stack_msc;
	printf("n_msc = %d\n",n_msc);
  }


  return  0;
}

[sleep]

追加の説明ありがとうございます。
お手数をお掛けします。

次の段階として、startとendでとり得る組み合わせをすべて試し、その各々がstartとendを逆にしてもルートはあるか？(このときコストは変わってしまっても大丈夫です、)

そこが一番よく分からない部分でして、
コストが変わってしまっても良い、ということは、片道で通った最短ルートをそのまま真逆に辿れる必要は無いわけですね？
つまり、ある１つの決まったスタート地点からある１つの決まったゴール地点に対して複数ルートを探す必要はないということですね？

言葉のニュアンスから色々な捉え方ができてしまうので、まずは想定している結果を教えてください。


プログラム中にある以下の配列から
edge[0][1] = 1;
edge[1][2] = 1;
edge[2][4] = 1;
edge[2][8] = 1;
edge[3][4] = 1;
edge[4][6] = 1;
edge[5][7] = 1;
edge[6][7] = 1;
edge[7][0] = 1;
edge[8][4] = 1;

想定している結果は以下ですか？
start: 0 end: 1
start: 0 end: 2
start: 0 end: 4
start: 0 end: 6
start: 0 end: 7
start: 0 end: 8
start: 1 end: 2
start: 1 end: 4
start: 1 end: 6
start: 1 end: 7
start: 1 end: 8
start: 2 end: 4
start: 2 end: 6
start: 2 end: 7
start: 2 end: 8
start: 4 end: 6
start: 4 end: 7
start: 4 end: 8
start: 6 end: 7
start: 6 end: 8
start: 7 end: 8

[sleep]

今回掲示いただいたコードを見て思ったのは、恐らくROYさんがハマっているのはC言語の書き方です。
こればかりは自身で言語の勉強をしていただくしかないので

悩んだのですが・・・、なるべく手を加えず修正した例を先に載せておくことにします。
これを見ながら前回私が示した結果が自身が求めていた結果であるかどうか確認してください。
もし、異なる結果を求めていた場合は自身の求めている結果を添えて再度教えてください。

コード:

#include <stdio.h>
#define N 9   //頂点数
#define INF 10000
#define TRUE 1
#define FALSE 0

int dijkstra(int start, int end, int arg_edge[N][N])  //最短経路の確定
{
	...
}

int check_msc(int start, int end, int arg_edge[][N])  //mscかの確認
{
	...
}


struct msc  //構造体の型宣言
{
	int start;
	int end;
};

void stack_msc(msc* n_msc, int arg_edge[][N])
{
	int n = 0;
	for (int i = 0; i<N; i++){
		for (int j = i + 1; j<N; j++){
			if (check_msc(i, j, arg_edge) == TRUE){
				n_msc[n].start = i;
				n_msc[n].end = j;
				n++;
			}
		}
	}
}


int main()
{
	int i, j, r;
	int dmin;    //最短距離コスト
	int start, end;     //出発と到着
	int edge[N][N]; //グラフ情報
	msc n_msc[N*(N - 1) / 2] = { 0 };

	for (i = 0; i<N; i++){    //グラフのパス情報
		for (j = 0; j<N; j++){
			edge[i][j] = INF;
		}
	}

	edge[0][1] = 1;
	edge[1][2] = 1;
	edge[2][4] = 1;
	edge[2][8] = 1;
	edge[3][4] = 1;
	edge[4][6] = 1;
	edge[5][7] = 1;
	edge[6][7] = 1;
	edge[7][0] = 1;
	edge[8][4] = 1;

	stack_msc(n_msc, edge);
	for (start = 0; start<sizeof(n_msc); start++){
		if (n_msc[start].end == 0) break;
		printf("strat=%d end=%d\n", n_msc[start].start, n_msc[start].end);
	}

	return  0;
}

[sleep]

65行目は以下に修正してください。（sizeofでループ回数を決めていました）

コード:

	for (start = 0; start<N*(N - 1) / 2); start++){