这篇文章主要介绍了c++查询最短路径示例,需要的朋友可以参考下

代码如下:

//shortest_path.c

#include

#include//用file

#include//可用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

{

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

for(j=0;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

for(b=0;b

{

if(a==b)map.pathmatrix[a][b]=0;

else map.pathmatrix[a][b]=MAX;

}

for(i=0;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

do{

printf("请输入第%d条路径的起点",i+1);

fflush(stdin);

gets(s1);

for(a=0;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

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

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

if(!strcmp(map.spot[t].name,s2))break;

if(t==map.spotnum)printf("不存在此景点，请重新输入。n");

}while(t==map.spotnum);

for(v=0;v

{

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

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

if((!spath[w].in)&&(spath[w].length

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_

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

更多信息请查看IT技术专栏