0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 图的综合应用-迪杰斯特拉算法(导游图)

prime7 2012-12-24 15:50:00 浏览854

```#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 sum;//景点的总数
map();//初始化
void InputNode();//输入点
void BuildMap();//构建图
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++)
}
void map::InputNode()
{
cout<<"exit-0"<<endl;
while(1)
break;
if(!sum)
cout<<"input defeat"<<endl;
else
cout<<"input success"<<endl;
cout<<endl;
}
{
string num;
cin>>num;
if(num=="0")
return 0;
cic[++sum].num_bianhao=num;
cin>>cic[sum].name;
cin>>cic[sum].pro;
cic[sum].num_xuhao=sum;
cout<<endl;
return 1;
}
{
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;
return 1;
}
void map::BuildMap()
{
cout<<"exit input 0_0_0"<<endl;
while(1)
{
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++)
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++)
{
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++)
{
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<<"*                                                      *"<<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");
break;
}
case 4:
{
system("cls");
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);