プログラマ専用SNS ミクプラ

ダイクストラ法を用いて、最短経路を求めるプログラムを作成しています。
重みはすべて１で考えています。
経路がない頂点にたどり着いたら、他の頂点を探索してくれると思っていたのですが、そうはならずどのように直せばいいのかもよくわかりません。
どなたかアドバイスを頂けたら幸いです。

code
#include <stdio.h>
#define N 6 //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 = INF;
prv = INF;
used = FALSE;
}

cost[start] = FALSE;
next = start;

do{
i = next;
used = TRUE;
dmin = INF;
for(j=0;j<N;j++) {
if(j == i ) continue;
if(arg_edge[j]==INF) continue;
printf("used[%d] = %d\n",j ,used[j]);
if(used[j]==TRUE) continue;
test = cost + arg_edge[j];
if(test < cost[j]) {
cost[j] = test;
prv[j] = i;
if(test < dmin) {
dmin = test;
next = j;
}
}
}
hit = dmin < INF;
} 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[j] = INF;
}
}

edge[0][1] = 1;
edge[1][3] = 1;
edge[1][2] = 1;
edge[3][4] = 1;
edge[4][2] = 1;
edge[4][5] = 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;
}

/code

ダイクストラ法
・「今いる頂点から更新できる頂点が無かったら探索を終了する」と書かれているので、
　今いる頂点から更新できる頂点が無かったら探索を終了してしまいます。
・未使用の点からコストが最小の点を探す処理が抜けていると思います。

コード:

#include <stdio.h>
#define N 6   //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;
	  printf("used[%d] = %d\n",j ,used[j]);
	  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 = dmin < INF; */
	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][3] = 1;
  edge[1][2] = 1;
  edge[3][4] = 1; 
  edge[4][2] = 1; 
  edge[4][5] = 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;
}

ありがとうございます！！！
おかげさまで解決しました！！

プログラマ専用SNS ミクプラ

ダイクストラ法についてです

ダイクストラ法についてです

Re: ダイクストラ法についてです

Re: ダイクストラ法についてです