c++查询最短路径示例_C/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 "欢迎进入导航系统！\n==========菜单===========\n0、载入北外地图\n1、建立地图\n2、查询最短路径\n3、退出\n==========菜单===========\n"

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读入成功\n");
else
  printf("spot读入失败\n");

if(load2()==0)
printf("path读入成功\n");
else
printf("path读入失败\n");
}

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("不存在此景点，请重新输入。\n");
  }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("不存在此景点，请重新输入。\n");
  }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("不存在此景点，请重新输入。\n");
}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("不存在此景点，请重新输入。\n");
}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,最短路径为：\n",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("\n请输入您的选项（数字）\n");
  fflush(stdin);
  scanf("%d",&menu);
  switch (menu)
  {
  case 0: loadmap();printf("\n北外地图载入完成\n");break;
  case 1: drawmap();printf("\n新建完成\n");break;
  case 2: shortestpath();printf("\n查询完成完成\n");break;
  }
}
printf("谢谢使用！");
}
2. [文件] shortest_path.h ~ 430B     下载(2)
#ifndef _SHORTEST_PATH_H_
#define _SHORTEST_PATH_H_