本文实例为大家分享了C++基于Floyd算法实现校园导航系统的具体代码，供大家参考，具体内容如下
首先是配置文件
//文件名'MGraph.h'
//用途：创建邻接矩阵
#include<iostream>
#include<stdlib.h>
using namespace std;
/*
*author:xcy
*date:2019.6.1
*/
#define MaxInt 32767 //表示极大值
#define MaxNum 100 //表示最大顶点数
typedef int status;
typedef string VerTexType; //顶点的数据类型
typedef int ArcType; //边的权值为整型
typedef struct
{
VerTexType vexs[MaxNum]; //顶点表
ArcType arcs[MaxNum][MaxNum]; //邻接矩阵
int vexnum,arcnum;//当前的点和边数
char name[MaxNum];
}AMGraph;
status CreateMap(AMGraph &G)//地图的创建
{
G.vexnum=10;
G.arcnum=13;
G.vexs[0]="北门";
G.vexs[1]="下沉广场";
G.vexs[2]="青年公寓";
G.vexs[3]="齐贤广场";
G.vexs[4]="15教";
G.vexs[5]="菜鸟驿站";
G.vexs[6]="汇森楼";
G.vexs[7]="图书馆";
G.vexs[8]="体育馆";
G.vexs[9]="南苑餐厅";
for(int i=0;i<MaxNum;i++)//初始化所有顶点之间距离
{
for(int j=0;j<MaxNum;j++)
{
G.arcs[i][j] = MaxInt;
}
}
//各顶点之间距离
G.arcs[0][1] = G.arcs[1][0] = 300;
G.arcs[0][2] = G.arcs[2][0] = 600;
G.arcs[1][2] = G.arcs[2][1] = 200;
G.arcs[2][3] = G.arcs[3][2] = 600;
G.arcs[2][6] = G.arcs[6][2] = 1000;
G.arcs[3][4] = G.arcs[4][3] = 100;
G.arcs[3][6] = G.arcs[6][3] = 800;
G.arcs[4][5] = G.arcs[5][4] = 100;
G.arcs[4][8] = G.arcs[8][4] = 400;
G.arcs[5][9] = G.arcs[9][5] = 700;
G.arcs[6][7] = G.arcs[7][6] = 100;
G.arcs[7][8] = G.arcs[8][7] = 100;
G.arcs[8][9] = G.arcs[9][8] = 300;
}
具体方法实现
#include<iostream>
#include<stdlib.h>
#include"MGraph.h"
using namespace std;
/*
*author:xcy
*date:2019.6.12
*change：使用弗洛依德算法
*/
int shortPath[MaxNum][MaxNum];//最短路径长度
int Path[MaxNum][MaxNum];//保存下一个节点
void ShortestPath_Floyd(AMGraph G)//弗洛依德算法
{
int i,j,k;
for(i=0;i<G.vexnum;i++)//循环遍历所有顶点（横列）
{
for(j=0;j<G.vexnum;j++)//循环遍历所有顶点（竖列）
{
shortPath[i][j]=G.arcs[i][j];//保存权值
if(shortPath[i][j]<MaxInt&&i!=j)
Path[i][j]=j;//保存下一个顶点下标
else Path[i][j]=-1;
}
}
//算法核心语句
for(k=0;k<G.vexnum;k++)//遍历所有点（作为中点）
{
for(i=0;i<G.vexnum;i++)//遍历行
{
for(j=0;j<G.vexnum;j++)//遍历列
{
//松弛操作 如果经历k点距离小于两点之间距离，选择经过k点的路线
if(shortPath[i][k]+shortPath[k][j]<shortPath[i][j])
{
shortPath[i][j]=shortPath[i][k]+shortPath[k][j];
Path[i][j]=Path[i][k];//更新操作
}
}
}
}
}
void math()//次级界面
{
int a,b,i,j,k,m,n;
AMGraph G;
CreateMap(G);
ShortestPath_Floyd(G); //弗洛依德算法
cout<<"1.北门 2.下沉广场 3.青年公寓 4.齐贤广场 5.15教"<<endl;
cout<<"6.菜鸟驿站 7.汇森楼 8.图书馆 9.体育馆 10.南苑餐厅"<<endl;
cout<<"输入起点的序号"<<endl;
cin>>a;
cout<<"输入终点的序号"<<endl;
cin>>b;
m=a-1;
n=b-1;
cout<<"最短路径："<<shortPath[m][n]<<"米"<<endl;
cout<<"路径为："<<G.vexs[m];
k=Path[m][n];
while(k!=n)
{
cout<<" -> "<<G.vexs[k];
k=Path[k][n];
}
cout<<" -> "<<G.vexs[n]<<endl;
}
void scence()//显示地图
{
cout<<"\t\t--------------------------------------------------------"<<endl;
cout<<"\t\t| 北门 |"<<endl;
cout<<"\t\t| |"<<endl;
cout<<"\t\t| 下沉 |"<<endl;
cout<<"\t\t| 广场 青年 |"<<endl;
cout<<"\t\t| 公寓 |"<<endl;
cout<<"\t\t| |"<<endl;
cout<<"\t\t| 菜鸟 |"<<endl;
cout<<"\t\t| 15教 驿站 |"<<endl;
cout<<"\t\t| |"<<endl;
cout<<"\t\t| 齐贤广场 |"<<endl;
cout<<"\t\t| 南苑 |"<<endl;
cout<<"\t\t| 餐厅 |"<<endl;
cout<<"\t\t| 汇森楼 |"<<endl;
cout<<"\t\t| 图书馆 体育馆 |"<<endl;
cout<<"\t\t--------------------------------------------------------"<<endl;
}
void Gui()//主界面
{
char a;
cout<<"\t\t\t┌--------------------------------┐"<<endl;
cout<<"\t\t\t│ │"<<endl;
cout<<"\t\t\t│ 欢迎使用南工校园导航系统 │"<<endl;
cout<<"\t\t\t│ │"<<endl;
cout<<"\t\t\t│--------------------------------│"<<endl;
cout<<"\t\t\t│ 1. 查看校园全貌 │"<<endl;
cout<<"\t\t\t│ 2. 计算最短路径 │"<<endl;
cout<<"\t\t\t│ 3. 退出导航系统 │"<<endl;
cout<<"\t\t\t└--------------------------------┘"<<endl;
while(true){
cout<<"\t\t\t输入要操作的序号(1-3):";
cin>>a;
(int)a;
if(a>'0'&&a<='3')
switch(a)
{
case '1': scence(); break;
case '2': math(); break;
case '3': cout<<"\t\t\t感谢您的使用！";exit(0);break;
}
else cout<<"\t\t\t请输入1-3!!"<<endl;
}
}
int main()
{
Gui();
}
