c+검색 최 단 경로 예시
//shortest_path.c
#include<stdio.h>
#include<stdlib.h>// file
#include<string.h>// gets(),puts()
#include"shortest_path.h"
#define MAX 32767
#define MENU " !
========== ===========
0、
1、
2、
3、
========== ===========
"
struct stmap map;//
const char *filepath1="D:\\spots.dat";
const char *filepath2="D:\\paths.dat";
int load1()
{
FILE *fp;
int i;
fp=fopen(filepath1,"r");
if(fp==NULL){printf("spots , ");return -1;}
fread(&map.spotnum,sizeof(int),1,fp);
for(i=0;i<map.spotnum;i++)
{
fread(map.spot[i].name,sizeof(char),10,fp);
fread(map.spot[i].intro,sizeof(char),20,fp);
}
fclose(fp);
return 0;
}
int load2()
{
FILE *fp;
int i,j;
fp=fopen(filepath2,"r");
if(fp==NULL){printf("paths , ");return -1;}
fread(&map.pathmatrix,sizeof(int),1,fp);
for(i=0;i<map.spotnum;i++)
for(j=0;j<map.spotnum;j++)
fread(&map.pathmatrix[i][j],sizeof(int),1,fp);
fclose(fp);
return 0;
}
void loadmap()
{
if(load1()==0)
printf("spot
");
else
printf("spot
");
if(load2()==0)
printf("path
");
else
printf("path
");
}
void drawmap()//
{
int i;
int a,b;
char s1[10],s2[10];
printf(" ?(<=20)");//map.spotmun
fflush(stdin);
scanf("%d",&map.spotnum);
printf(" ?");//map.pathnum
fflush(stdin);// , "stdio.h"
scanf("%d",&map.pathnum);
for(a=0;a<map.spotnum;a++)//initialize map
for(b=0;b<map.spotnum;b++)
{
if(a==b)map.pathmatrix[a][b]=0;
else map.pathmatrix[a][b]=MAX;
}
for(i=0;i<map.spotnum;i++){
printf(" %d (<=10letters)",i+1);
fflush(stdin);
gets(map.spot[i].name);
printf(" %d (<=20letters)",i+1);
fflush(stdin);
gets(map.spot[i].intro);
}// map.spot[].name;map.spot[].intro
for(i=0;i<map.pathnum;i++){
do{
printf(" %d ",i+1);
fflush(stdin);
gets(s1);
for(a=0;a<map.spotnum;a++)
if(!strcmp(map.spot[a].name,s1))break;//
if(a==map.spotnum)printf(" , 。
");
}while(a==map.spotnum);
do{
printf(" %d ",i+1);
fflush(stdin);
gets(s2);
for(b=0;b<map.spotnum;b++)
if(!strcmp(map.spot[b].name,s2))break;
if(b==map.spotnum)printf(" , 。
");
}while(b==map.spotnum);
printf(" %d ",i+1);
fflush(stdin);
scanf("%d",&map.pathmatrix[a][b]);
map.pathmatrix[b][a]=map.pathmatrix[a][b];//
}
}
void shortestpath()// ,
{
struct stspath spath[20];
int s,t,v,w,min;
char s1[10],s2[10];
int pathorder[20];
struct stspath *p;//pathorder
do{
printf(" ");//
fflush(stdin);
gets(s1);
for(s=0;s<map.spotnum;s++)
if(!strcmp(map.spot[s].name,s1))break;
if(s==map.spotnum)printf(" , 。
");
}while(s==map.spotnum);
do{
printf(" ");//
fflush(stdin);
gets(s2);
for(t=0;t<map.spotnum;t++)
if(!strcmp(map.spot[t].name,s2))break;
if(t==map.spotnum)printf(" , 。
");
}while(t==map.spotnum);
for(v=0;v<map.spotnum;v++)//initialize spath
{
spath[v].length=MAX;
spath[v].in=0;
}
spath[s].in=1;
spath[s].length=0;
spath[s].pior=NULL;
v=s;
while(v!=t){
for(w=0;w<map.spotnum;w++)
if((!spath[w].in)&&(spath[w].length>spath[v].length+map.pathmatrix[v][w])){
spath[w].length=spath[v].length+map.pathmatrix[v][w];
spath[w].pior=&spath[v];
}
min=MAX;
for(w=0;w<map.spotnum;w++)
if((!spath[w].in)&&(spath[w].length<min)){
min=spath[w].length;
v=w;
}
spath[v].in=1;
}
printf(" %d, :
",spath[t].length);//print path
for(v=0,p=&spath[t];p->pior!=NULL;p=p->pior)
{
pathorder[v]=p-spath;
v++;
}
pathorder[v]=s;
for(;v>=0;v--)
printf("%10s",map.spot[pathorder[v]].name);
}
void main()
{
int menu=1;
printf(MENU);
while(menu!=3)
{
printf("
( )
");
fflush(stdin);
scanf("%d",&menu);
switch (menu)
{
case 0: loadmap();printf("
");break;
case 1: drawmap();printf("
");break;
case 2: shortestpath();printf("
");break;
}
}
printf(" !");
}
2. [ ] shortest_path.h ~ 430B (2)
#ifndef _SHORTEST_PATH_H_
#define _SHORTEST_PATH_H_
struct stspot{//
char name[11];// no more than 10
char intro[20];// no more than 20
};
struct stmap{//
stspot spot[20];// ,
int pathmatrix[20][20];// ,
int spotnum;
int pathnum;
};
struct stspath//
{
stspath * pior;
int in;// can be boolen
int length;
};
#endif
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 원활 공사 & & 원활 공사 (차 트 법)모 성 은 도시 의 교통 상황 을 조사 하여 기 존의 도시 도로 통계 표를 얻 었 고 표 에는 모든 도로 가 직접 연 결 된 도시 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 도시...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.