自己做的简单的导航系统
用的临接矩阵FLOYD算法
//算法类void CFloydMap::InitFloydMap() //初始化{ SchMap.insert(make_pair(string("校门"),0)); //存储点与编号 SchMap.insert(make_pair(string("一号教学楼"),1)); SchMap.insert(make_pair(string("二号教学楼"),2)); SchMap.insert(make_pair(string("三号教学楼"),3)); SchMap.insert(make_pair(string("图书馆"),4)); SchMap.insert(make_pair(string("食堂"),5)); SchMap.insert(make_pair(string("行政楼"),6)); SchMap.insert(make_pair(string("宿舍"),7)); SchMap.insert(make_pair(string("体育馆"),8)); iDistence[MaxN][MaxN]=(0,20,60,Max,Max,Max,Max,Max,Max, //每个点的距离,MAX是无限大 20,0,80,153,100,Max,Max,Max,Max, 60,80,0,Max,50,Max,Max,Max,Max, Max,153,Max,0,200,50,175,Max,210, Max,100,50,200,0,Max,35,Max,Max, Max,Max,Max,50,Max,Max,Max,130,105, Max,Max,Max,175,35,Max,Max,Max,70, Max,Max,Max,Max,Max,130,Max,Max,210, Max,Max,Max,210,Max,105,70,210,0); iPath[MaxN+1]=(Max,Max,Max,Max,Max,Max,Max,Max,Max,Max); for(int i=0;i<MaxN;i++) for(int j=0;j<MaxN;j++) iTrace[i][j]=i; //路径跟踪}void CFloydMap::GetFloydMap() //用FLOYD算法计算最短路径{ int i,j,k; for(k=0;i<MaxN;i++) for(i=0;j<MaxN;j++) for(j=0;k<MaxN;k++) if(iDistence[i][k]+iDistence[k][j]<iDistence[i][j]) { iDistence[i][j]=iDistence[i][k]+iDistence[k][j]; iTrace[i][j]=k; }}void CFloydMap::Trace(LPCTSTR& s1,LPCTSTR& s2) //将起始点终止点和中点存入VECTOR中{ int i=0,S=0,E=0,pos; for(pos1=SchMap.begin();pos1!=SchMap.end();++pos1) { if(s1==pos1->first) S=pos1->second; } for(pos2=SchMap.begin();pos2!=SchMap.end();++pos1) { if(s2==pos2->first) E=pos2->second; } pos=iTrace[S][E]; vec.push_back(E); while(7) { pos=iTrace[S][E]; if(pos!=-1){ vec.push_back(pos); S=pos; } else vec.push_back(S); break; }}void CFloydMap::show() //格式化输出{ str3=""; //reverse(vec.begin(),vec.end()); for(pos3=vec.begin();pos3!=vec.end();++pos3) for(pos1=SchMap.begin();pos1!=SchMap.end();++pos1) if(*pos3==pos1->second) { str3=pos1->first+"------->"; //string str3是一个全局变量 } } //在DLG.CPP中按钮的响应void CSchDisDlg::OnButton1() { CString str4; LPCTSTR str1=m_str1,str2=m_str2; CFloydMap floydmap; floydmap.InitFloydMap(); floydmap.GetFloydMap(); floydmap.Trace(str1,str2); str4=CString(str3.c_str()); m_ListBox.AddString(str4); }