c++查询最短路径示例

　　C++擅长面向对象程序设计的同时，还可以进行基于过程的程序设计，因而C++就适应的问题规模而论，大小由之。本文特意为大家收集整理了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<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_

　　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

【c++查询最短路径示例】相关文章：

C++ this指针详解10-01

Dev C++安装教程10-06

c++快速排序详解10-05

C/C++内存管理10-05

计算机二级C++考点：C++语言概述10-06

C语言误用知识整理嵌入式C语言性能优化方法