出発時刻を入力し最短経路を求めるプログラムを下記の通り作成しました
逆に到着予定時刻を入力して経路を求めるプログラムを作成したいのですが…
現在は出発アークに条件付けをして入力に対して経路探索をしていますので
入力をtrain[0].e_time=60*hour+timeとして到着アークの条件を付け加えればいいのかな?とは考えているのですが
まったく考え付きません…どうか教えて頂けないでしょうか
#include <stdio.h>
#define N 22
int S[N]; // 最短距離がすでに計算されたノードを格納
int d[N]; // d[i]は、出発ノードからノードiまでの最短距離を格納するための配列
int p[N]; // 最短経路を格納
int c; //
struct node // 電車情報の構造体
{
int flag; // flagが0なら出発ノード、flagが1なら到着ノード
int T_name; // 電車の名番
char s_name[20]; // 出発駅の名前
char e_name[20]; // 到着駅の名前
int s; // 出発駅の名前に対応した番号
int e; // 到着駅の名前に対応した番号
int s_time; // 出発時刻
int e_time; // 到着時刻
};
void dijkstra(int a[N][N],int s);
int main(void)
{
// 構造体を初期化し配列作成
struct node train[N]={{0,999,"start station","NULL",999,999,999,999},//着発区分,"出発駅","到着駅",出発駅番号,到着駅番号,出発時刻,到着時刻
{0,1,"津田沼","錦糸町",1,2,18*60+1,18*60+20},
{1,1,"津田沼","錦糸町",1,2,18*60+1,18*60+20},
{0,2,"津田沼","錦糸町",1,2,18*60+16,18*60+35},
{1,2,"津田沼","錦糸町",1,2,18*60+16,18*60+35},
{0,3,"津田沼","錦糸町",1,2,17*60+59,18*60+26},
{1,3,"津田沼","錦糸町",1,2,17*60+59,18*60+26},
{0,4,"津田沼","錦糸町",1,2,18*60+10,18*60+37},
{1,4,"津田沼","錦糸町",1,2,18*60+10,18*60+37},
{0,3,"錦糸町","御茶ノ水",2,3,18*60+27,18*60+35},
{1,3,"錦糸町","御茶ノ水",2,3,18*60+27,18*60+35},
{0,4,"錦糸町","御茶ノ水",2,3,18*60+38,18*60+46},
{1,4,"錦糸町","御茶ノ水",2,3,18*60+38,18*60+46},
{0,3,"御茶ノ水","新宿",3,4,18*60+36,18*60+55},
{1,3,"御茶ノ水","新宿",3,4,18*60+36,18*60+55},
{0,4,"御茶ノ水","新宿",3,4,18*60+47,19*60+6},
{1,4,"御茶ノ水","新宿",3,4,18*60+47,19*60+6},
{0,5,"御茶ノ水","新宿",3,4,18*60+36,18*60+46},
{1,5,"御茶ノ水","新宿",3,4,18*60+36,18*60+46},
{0,6,"御茶ノ水","新宿",3,4,18*60+47,18*60+57},
{1,6,"御茶ノ水","新宿",3,4,18*60+47,18*60+57},
{999,999,"NULL","end",999,999,999,999}};
int S,E,i,j,k,time,hour;
int A[N][N];
S=0;
E=N-1;
for(i=0;i<N;i++)
{
for(k=0;k<N;k++)
{
A[i][k]=9999;
}
}
printf("1:津田沼\n2:錦糸町\n3:御茶ノ水\n4:新宿\n");
printf("出発駅番号を指定せよ\n"); scanf("%d",&train[0].s);
printf("到着駅番号を指定せよ\n"); scanf("%d",&train[N].e);
printf("出発時間を入力(18時以降)\n");
printf("時:"); scanf("%d",&hour);
printf("分:"); scanf("%d",&time);
train[0].s_time=60*hour+time;
for(i=1;i<N-1;i++)
{
for(j=1;j<N-1;j++)
{
// 走行アーク
if(train[i].T_name==train[j].T_name && train[i].flag==0 && train[j].flag==1 && train[i].s_time==train[j].s_time)
{
A[i][j]=train[j].e_time-train[i].s_time;
}
// 停車アーク
if(train[i].T_name==train[j].T_name && train[i].flag==1 && train[j].flag==0 && train[i].e==train[j].s)
{
A[i][j]=train[j].s_time-train[i].e_time;
}
// 乗り換えアーク
if(train[i].T_name!=train[j].T_name && train[i].flag==1 && train[j].flag==0 && train[i].e==train[j].s && train[i].e_time<train[j].s_time)
{
A[i][j]=train[j].s_time-train[i].e_time;
}
}
}
for(i=1;i<N-1;i++)
{
// 出発アーク
if(train[0].s==train[i].s && train[i].flag==0)
{
if(train[0].s_time<=train[i].s_time)
{
A[0][i]=train[i].s_time-train[0].s_time;
}
else
{
A[0][i]=(train[i].s_time+24*60)-train[0].s_time;
}
}
}
for(i=1;i<N-1;i++)
{
// 到着アーク
if(train[N].e==train[i].e && train[i].flag==1)
A[i][N-1]=0;
}
dijkstra(A,S);
i=E;
while(p[i]!=0)
{
if(train[p[i]].flag==0)
{
printf("%s:%d時%d分発",train[p[i]].s_name,train[p[i]].s_time/60,train[p[i]].s_time%60);
}else
{
printf("%s:%d時%d分着",train[p[i]].e_name,train[p[i]].e_time/60,train[p[i]].e_time%60);
}
if(p[i]!=0)
printf("\n\n");
i=p[i];
}
return 0;
}
void dijkstra(int a[N][N],int s)
{
int i,j,k,v,w,min;
for(i=1;i<N;i++)
d[i]=9999;
for(i=0;i<N;i++)
S[i]=0;
d[s]=0;
c=0;
while(1)
{
c=0;
min=9999;
for(k=0;k<N;k++)
{
if(S[k]==0 && d[k]<min) // 最短距離が計算されていないノードかつ今現在最小の値よりも小さい
{
v=k;
min=d[k];
}
}
S[v]=1;
for(i=0;i<N;i++)
{
if(S[i]==0 && a[v][i]!=9999) // 最短距離が計算されていないノードかつ'v'から'i'へ重みがある
{
w=i;
if(d[w]>d[v]+a[v][w])
{
d[w]=d[v]+a[v][w];
p[w]=v;
}
}
}
for(i=0;i<N;i++)
{
if(S[i]==0)
c=c+1;
}
if(c==0)
break;
}
}