49
圖的綜合應用-迪傑斯特拉算法(導遊圖)
數據結構的大實驗 基本跟線性鏈表的什麼學生管理係統沒什麼區別 還有什麼查詢景點之類的 對於這種的係統函數寫完了
但是主函數偷懶了沒寫 唯一有算法的就是迪傑斯特拉求兩個景點的最短路徑了 圖是用鄰接矩陣存的
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 100
#define oo 99999999
class Ciceroni
{
public:
int num_xuhao;
string num_bianhao;//景點編號
string name;//景點名稱
string pro;//景點簡介
};
class map
{
public:
Ciceroni cic[MAX];//存景點的數組
int AdjacencyMatrix[MAX][MAX];//景點鄰接矩陣
int sum;//景點的總數
map();//初始化
void InputNode();//輸入點
bool AddNode();//加點
void BuildMap();//構建圖
int AddEdge();//加邊 //0-退出 1-正確 2-無點
void QueryNode();//查詢點
void Queryminpath();//查詢兩點最短路徑 迪傑斯特拉
void Oueryminpath_s();//查詢多點最短路徑
};
map::map()
{
sum=0;
for(int i=0; i<MAX; i++)
for(int j=0; j<MAX; j++)
AdjacencyMatrix[i][j]=oo;
}
void map::InputNode()
{
cout<<"exit-0"<<endl;
while(1)
if(!AddNode())
break;
if(!sum)
cout<<"input defeat"<<endl;
else
cout<<"input success"<<endl;
cout<<endl;
}
bool map::AddNode()
{
string num;
cout<<"please input num of node"<<endl;
cin>>num;
if(num=="0")
return 0;
cic[++sum].num_bianhao=num;
cout<<"please input name of node"<<endl;
cin>>cic[sum].name;
cout<<"please input pro of node"<<endl;
cin>>cic[sum].pro;
cic[sum].num_xuhao=sum;
cout<<endl;
return 1;
}
int map::AddEdge()
{
string startnum,endnum;
int dis,s=-1,e=-1;
cout<<"input start node's num, end node's num, distance"<<endl;
cin>>startnum>>endnum>>dis;
if(startnum==endnum&&endnum=="0"&&!dis)
return 0;
for(int i=1; i<=sum; i++)
{
if(cic[i].num_bianhao==startnum)
s=i;
if(cic[i].num_bianhao==endnum)
e=i;
if(s!=-1&&e!=-1)
break;
}
if(s==-1||e==-1)
return 2;
AdjacencyMatrix[s][e]=AdjacencyMatrix[e][s]=dis;
return 1;
}
void map::BuildMap()
{
cout<<"exit input 0_0_0"<<endl;
while(1)
{
int s=AddEdge();
if(!s) break;
if(s==2) cout<<"input num error"<<endl;
cout<<endl;
}
cout<<"bulid success"<<endl;
}
void map::QueryNode()
{
cout<<"input node's num"<<endl;
string num;
cin>>num;
int flag=0,i,j;
for(i=1; i<=sum; i++)
if(cic[i].num_bianhao==num)
{
flag=1;
break;
}
if(flag)
{
cout<<"node's num:"<<endl<<cic[i].num_bianhao<<endl;
cout<<"node's name:"<<endl<<cic[i].name<<endl;
cout<<"node's pro:"<<endl<<cic[i].pro<<endl;
cout<<"this node can arrive:"<<endl;
for(j=1; j<=sum; j++)
if(AdjacencyMatrix[i][j]<oo)
cout<<"("<<cic[j].num_bianhao<<")"<<cic[j].name<<endl;
}
else
cout<<"no this node"<<endl;
}
void map::Queryminpath()
{
int distance[MAX];
bool final[MAX];
int pre[MAX][MAX];
int s=-1,e=-1;
string start,end;
cout<<"input start num end num"<<endl;
cin>>start>>end;
for(int i=1; i<=sum; i++)
{
if(cic[i].num_bianhao==start)
s=i;
if(cic[i].num_bianhao==end)
e=i;
if(s!=-1&&e!=-1)
break;
}
if(s==-1||e==-1)
{
cout<<"no node"<<endl;
return;
}
memset(final,0,sizeof(final));
memset(pre,0,sizeof(pre));
for(int i=1; i<=sum; i++)
{
distance[i]=AdjacencyMatrix[s][i];
if(distance[i]<oo)
pre[i][1]=i;
}
distance[s]=0;
final[s]=1;
for(int i=2; i<=sum; i++)
{
int min=oo,p;
for( int j=1; j<=sum; j++)
if(!final[j]&&distance[j]<min)
min=distance[j],p=j;
final[p]=1;
for(int j=1; j<=sum; j++)
if(!final[j]&&(min+AdjacencyMatrix[p][j])<distance[j])
{
distance[j]=min+AdjacencyMatrix[p][j];
for(int k=1; k<=sum; k++)
pre[j][k]=pre[p][k];
for(int k=1; k<=sum; k++)
if(!pre[j][k])
{
pre[j][k]=j;
break;
}
}
}
if(pre[e][1])
{
cout<<"the min distace between "<<cic[s].name<<" and "<<cic[e].name<<" is "<<distance[e]<<endl;
cout<<"the path is :"<<endl;
for(int k=1; k<=sum; k++)
{
if(!pre[e][k])
break;
cout<<cic[pre[e][k]].name<<" ";
}
cout<<endl;
}
else
cout<<"no path between "<<cic[s].name<<" and "<<cic[e].name<<endl;
}
int main()
{
map a;
int n;
do
{
system("cls");
cout<<"********************************************************"<<endl;
cout<<"* welcome come to this xitong made by HanFangchong *"<<endl;
cout<<"* *"<<endl;
cout<<"* 1-build node 2-build edge *"<<endl;
cout<<"* *"<<endl;
cout<<"* 3-add node 4-add edge *"<<endl;
cout<<"* *"<<endl;
cout<<"* 5-query node 6-query minpath *"<<endl;
cout<<"* *"<<endl;
cout<<"* 0-exit *"<<endl;
cout<<"********************************************************"<<endl;
printf("Selcet the operation you want:\n");
cin>>n;
switch(n)
{
case 1:
{
system("cls");
a.InputNode();
break;
}
case 2:
{
system("cls");
a.BuildMap();
break;
}
case 3:
{
system("cls");
a.AddNode();
break;
}
case 4:
{
system("cls");
a.AddEdge();
break;
}
case 5:
{
system("cls");
a.QueryNode();
int s;
cout<<"exit-0"<<endl;
cin>>s;
if(!s)
break;
}
case 6:
{
system("cls");
a.Queryminpath();
int s;
cout<<"exit-0"<<endl;
cin>>s;
if(!s)
break;
}
}
}
while(n);
cout<<"thank for your using";
return 0;
}
最後更新：2017-04-04 07:03:12