這篇文章主要介紹了c++查詢最短路徑示例,需要的朋友可以參考下

代碼如下:

//shortest_path.c

#include

#include//用file

#include//可用gets(),puts()

#include"shortest_path.h"

#define MAX 32767

#define MENU "歡迎進(jìn)入導(dǎo)航系統(tǒng)!n==========菜單===========n0、載入北外地圖n1、建立地圖n2、查詢最短路徑n3、退出n==========菜單===========n"

struct stmap map;//無向網(wǎng)

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("共有幾個(gè)景點(diǎn)?(<=20)");//map.spotmun

fflush(stdin);

scanf("%d",&map.spotnum);

printf("共有幾條景點(diǎn)與景點(diǎn)之間直接相連的路徑?");//map.pathnum

fflush(stdin);//清空鍵盤緩沖區(qū)，在"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("請(qǐng)輸入第%d個(gè)景點(diǎn)的名稱(<=10letters)",i+1);

fflush(stdin);

gets(map.spot[i].name);

printf("請(qǐng)輸入第%d個(gè)景點(diǎn)的介紹(<=20letters)",i+1);

fflush(stdin);

gets(map.spot[i].intro);

}//輸入景點(diǎn)名字和簡(jiǎn)介map.spot[].name;map.spot[].intro

for(i=0;i

do{

printf("請(qǐng)輸入第%d條路徑的起點(diǎn)",i+1);

fflush(stdin);

gets(s1);

for(a=0;a

if(!strcmp(map.spot[a].name,s1))break;//查找景點(diǎn)編號(hào)

if(a==map.spotnum)printf("不存在此景點(diǎn)，請(qǐng)重新輸入。n");

}while(a==map.spotnum);

do{

printf("請(qǐng)輸入第%d條路徑的終點(diǎn)",i+1);

fflush(stdin);

gets(s2);

for(b=0;b

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

if(b==map.spotnum)printf("不存在此景點(diǎn)，請(qǐng)重新輸入。n");

}while(b==map.spotnum);

printf("請(qǐng)輸入第%d條路徑的長度",i+1);

fflush(stdin);

scanf("%d",&map.pathmatrix[a][b]);

map.pathmatrix[b][a]=map.pathmatrix[a][b];//輸入路徑長度

}

}

void shortestpath()//最短路徑，輸入起點(diǎn)終點(diǎn)輸出路徑和路程

{

struct stspath spath[20];

int s,t,v,w,min;

char s1[10],s2[10];

int pathorder[20];

struct stspath *p;//pathorder

do{

printf("請(qǐng)輸入起點(diǎn)");//查找起點(diǎn)的景點(diǎn)編號(hào)

fflush(stdin);

gets(s1);

for(s=0;s

if(!strcmp(map.spot[s].name,s1))break;

if(s==map.spotnum)printf("不存在此景點(diǎn)，請(qǐng)重新輸入。n");

}while(s==map.spotnum);

do{

printf("請(qǐng)輸入終點(diǎn)");//查找終點(diǎn)的景點(diǎn)編號(hào)

fflush(stdin);

gets(s2);

for(t=0;t

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

if(t==map.spotnum)printf("不存在此景點(diǎn)，請(qǐng)重新輸入。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請(qǐng)輸入您的選項(xiàng)(數(shù)字)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{//景點(diǎn)的頂點(diǎn)

char name[11];//景點(diǎn)名稱no more than 10

char intro[20];//景點(diǎn)介紹no more than 20

};

struct stmap{//整個(gè)無向網(wǎng)

stspot spot[20];//點(diǎn)，景點(diǎn)向量

int pathmatrix[20][20];//邊，路徑的鄰接矩陣

int spotnum;

int pathnum;

};

struct stspath//求最短路徑時(shí)的景點(diǎn)數(shù)組

{

stspath * pior;

int in;// can be boolen

int length;

};

#endif

更多信息請(qǐng)查看IT技術(shù)專欄