//文件名'MGraph.h'
//用途：創(chuàng)建鄰接矩陣
#include<iostream>
#include<stdlib.h>
using namespace std;
/*
*author:xcy?
*date:2019.6.1?
*/
#define MaxInt 32767 //表示極大值
#define MaxNum 100 ?//表示最大頂點(diǎn)數(shù)
typedef int status;
typedef string VerTexType; ?//頂點(diǎn)的數(shù)據(jù)類型
typedef int ArcType; ?//邊的權(quán)值為整型
typedef struct
{
? ? VerTexType vexs[MaxNum]; ? //頂點(diǎn)表
? ? ArcType arcs[MaxNum][MaxNum]; ? //鄰接矩陣
? ? int vexnum,arcnum;//當(dāng)前的點(diǎn)和邊數(shù)
? ? char name[MaxNum];
}AMGraph;

status CreateMap(AMGraph &G)//地圖的創(chuàng)建?
{
? ? 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++)//初始化所有頂點(diǎn)之間距離?
? ? {
? ? ? ? for(int j=0;j<MaxNum;j++)
? ? ? ? {
? ? ? ? ? ? G.arcs[i][j] = MaxInt;
? ? ? ? }
? ? }
? ? //各頂點(diǎn)之間距離
? ? 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];//保存下一個節(jié)點(diǎn)?
void ShortestPath_Floyd(AMGraph G)//弗洛依德算法
{
? ? int i,j,k;
? ? for(i=0;i<G.vexnum;i++)//循環(huán)遍歷所有頂點(diǎn)（橫列）?
? ? {
? ? ? ? for(j=0;j<G.vexnum;j++)//循環(huán)遍歷所有頂點(diǎn)（豎列）
? ? ? ? {
? ? ? ? ? ? shortPath[i][j]=G.arcs[i][j];//保存權(quán)值?
? ? ? ? ? ? if(shortPath[i][j]<MaxInt&&i!=j)?
? ? ? ? ? ? ?? ?Path[i][j]=j;//保存下一個頂點(diǎn)下標(biāo)?
? ? ? ? ? ? else Path[i][j]=-1;
? ? ? ? }
? ? }
? ? //算法核心語句?
? ? for(k=0;k<G.vexnum;k++)//遍歷所有點(diǎn)（作為中點(diǎn)）?
? ? {
? ? ? ? for(i=0;i<G.vexnum;i++)//遍歷行?
? ? ? ? {
? ? ? ? ? ? for(j=0;j<G.vexnum;j++)//遍歷列?
? ? ? ? ? ? {
? ? ? ? ? ? ?? ?//松弛操作 如果經(jīng)歷k點(diǎn)距離小于兩點(diǎn)之間距離，選擇經(jīng)過k點(diǎn)的路線?
? ? ? ? ? ? ? ? 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<<"輸入起點(diǎn)的序號"<<endl;
? ? cin>>a;
? ? cout<<"輸入終點(diǎn)的序號"<<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│ ? 歡迎使用南工校園導(dǎo)航系統(tǒng) ? ? │"<<endl;
? ? cout<<"\t\t\t│ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?│"<<endl;
? ? cout<<"\t\t\t│--------------------------------│"<<endl;
? ? cout<<"\t\t\t│ ? ? ?1. 查看校園全貌 ? ? ? ? ? │"<<endl;
? ? cout<<"\t\t\t│ ? ? ?2. 計(jì)算最短路徑 ? ? ? ? ? │"<<endl;
? ? cout<<"\t\t\t│ ? ? ?3. 退出導(dǎo)航系統(tǒng) ? ? ? ? ? │"<<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();
}