端末で始点と終点を入力します。a点~e点まであり、a点は0、b点は1、・・・c点は4と考えて入力します。
また、つながっていない点同士のデータの値は1000にしてfor文でまわしています。
longP[5]の初期値も書いているのであってるのかよくわかりません。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
/*データ(隣接行列)*/
int d[5][5] = {
/* a, b, c, d, e */
1000, 8, 1000, 1000, 4, /*a*/
8, 1000, 5, 6, 1000, /*b*/
1000, 5, 1000, 3, 2, /*c*/
1000, 6, 3, 1000, 4, /*d*/
4, 1000, 2, 4, 1000, /*e*/
};
void BF(int start, int goal){
int shortL = 1000, longL = 0;
int shortP[5]={-1,-1,-1,-1,-1}, longP[5]={-1,-1,-1,-1,-1};
int i, j, k;
int tmp;
//2節点の場合
tmp = d[start][goal];
if(tmp < 1000){
if(shortL > tmp){
shortL = tmp;
shortP[0] = start;
shortP[1] = goal;
}
if(longL < tmp){
longL = tmp;
longP[0] = start;
longP[1] = goal;
}
}
//3節点の場合
for(i=0; i<5; i++){
tmp = d[start][i] + d[i][goal];
if(tmp < 1000){
if(shortL > tmp){
shortL = tmp;
shortP[0] = start;
shortP[1] = i;
shortP[2] = goal;
}
if(longL < tmp){
longL = tmp;
longP[0] = start;
longP[1] = i;
longP[2] = goal;
}
}
}
//4節点の場合
for(i=0; i<5; i++){
for(j=0; j<5; j++){
tmp = d[start][i] + d[i][j] + d[j][goal];
if(tmp < 1000){
if(shortL > tmp){
shortL = tmp;
shortP[0] = start;
shortP[1] = i;
shortP[2] = j;
shortP[3] = goal;
}
if(longL < tmp){
longL = tmp;
longP[0] = start;
longP[1] = i;
longP[2] = j;
longP[3] = goal;
}
}
}
}
//5節点の場合
for(i=0; i<5; i++){
for(j=0; j<5; j++){
for(k=0; k<5; k++){
tmp = d[start][i] + d[i][j] + d[j][k] + d[k][goal];
if(tmp < 1000){
if(shortL > tmp){
shortL = tmp;
shortP[0] = start;
shortP[1] = i;
shortP[2] = j;
shortP[3] = k;
shortP[4] = goal;
}
if(longL < tmp){
longP[0] = start;
longP[1] = i;
longP[2] = j;
longP[3] = k;
longP[4] = goal;
}
}
}
}
}
if(start == goal){
printf("最短経路");
printf("%c->%c\n", start+97, goal+97);
printf("最短経路長0\n");
}else{
printf("最短経路");
printf("%c",shortP[0]+97);
for(i=1; shortP[i] != -1; i++){
printf("->%c",shortP[i]+97);
}
printf("\n最短経路長");
printf("%d\n", shortL);
}
}
int main(){
int start;
int goal;
while(1){
printf("始点:");
scanf("%d", &start);
printf("終点:");
scanf("%d", &goal);
BF(start, goal);
}
return 0;
}