#include <iostream>
#include <string>
#include <fstream>
using namespace std;
#define INFINITY 30000 //定义一个权值的最大值
#define VERTEX_NUM 80 //图的最多顶点数 enum BOOL {False,True};
class Graph
{public:
int arcs[VERTEX_NUM][VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点和边数
}; void CreateGraph(Graph &); //生成图的邻接矩阵
void ShortestPath_DiJ(Graph,int,int[][VERTEX_NUM],int[]);
//用迪杰斯特拉算法求从某一源点到其余顶点的最短路径
void Print_ShortestPath(Graph,int,int,int[][VERTEX_NUM],int[],char [][20]);
//显示最短路径
void Trans( char a[][20] );
//将数字转换为中文站名int main()
{ Graph G; //采用邻接矩阵结构的图
char a[VERTEX_NUM][20]; //转换矩阵
char j='y';
int u,t; //起始顶点号
int P[VERTEX_NUM][VERTEX_NUM]; //存放从源点到各顶点的最短路径
int D[VERTEX_NUM];
Trans(a) ;
cout<<"请输入你所选择的起点和终点:"<<endl;
while(j!= 'N '&&j!= 'n ')
{CreateGraph(G); //生成邻接矩阵结构的图
cin>>u>>t;
ShortestPath_DiJ(G,u,P,D); //利用迪杰斯特拉算法求最短路径
Print_ShortestPath(G,u,t,P,D,a); //显示最短路径
cout<< "最短路径演示完毕,继续进行吗?(Y/N) ";
cin>>j;
}
return 0;
} void Trans( char a[][20])
{
ifstream in_file;
in_file.open("D:\\translate.txt",ios::in);
for (int i=0; i<VERTEX_NUM;i++) in_file>>a[i];
in_file.close();
}void CreateGraph(Graph &G)
{//构造邻接矩阵结构的图G
ifstream in_file;
in_file.open("D:\\graphinfo.txt",ios::in);
int i,j;
int start,end,weight;
//cout<< "请输入图的顶点数和弧数(顶点数,弧数): \n";
//cin>>G.vexnum>>G.arcnum; //输入图的顶点数和边数
in_file >> G.vexnum>>G.arcnum;
for(i=1;i <=G.vexnum;i++)
for(j=1;j <=G.vexnum;j++)
G.arcs[i][j]=INFINITY; //初始化邻接矩阵
//cout<< "输入各弧和权值,格式:弧尾,弧头,权值\n ";
for(i=1;i <=G.arcnum;i++)
{ //cin>>start>>end>>weight; //输入边的起点和终点及权值
in_file >>start>>end>>weight;
G.arcs[start][end]=weight;
G.arcs[end][start]=weight;
}
in_file.close();
} void ShortestPath_DiJ(Graph G,int v0,int P[][VERTEX_NUM],int D[])
{//用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]
//若P[v][0]≠0,表明从源点出发存在一条到顶点v的最短路径,该路径存放在P[v]中
//final[v]为True则表明已经找到从v0到v的最短路径
int i,j,w,v;
int min;
BOOL final[VERTEX_NUM];
for(v=1;v <=G.vexnum;v++) //初始化
{final[v]=False; D[v]=G.arcs[v0][v];
for(i=0;i <=G.vexnum;i++) P[v][i]=0; //设空路径
//if(D[v] <INFINITY) P[v][0]=v0; //若从v0到v有直达路径
}
D[v0]=0; final[v0]=True; //初始时,v0属于S集
//开始主循环,每次求得v0到某个顶点v的最短路径,并加v到S集
for(i=1;i <=G.vexnum;i++) //寻找其余G.vexnum-1个顶点
{v=0;
min=INFINITY;
for(w=1;w <=G.vexnum;w++) //寻找当前离v0最近的顶点v
if((!final[w])&&(D[w] <min))
{v=w;min=D[w];}
if(!v) break; //若v=0表明所有与v0有通路的顶点均已找到了最短路径,退出主循环
final[v]=True; //将v加入S集
for(j=0;P[v][j]!=0;j++) ;
P[v][j]=v; //将路径P[v]延伸到顶点v
for(w=1;w <=G.vexnum;w++) //更新当前最短路径及距离
if(!final[w]&&(min+G.arcs[v][w] <D[w]))
{ D[w]=min+G.arcs[v][w];
for(j=0;P[v][j]!=0;j++) P[w][j]=P[v][j];
}
}
} void Print_ShortestPath(Graph G,int v0,int v1,int P[][VERTEX_NUM],int D[],char a[][20])
{//显示从顶点u到其余顶点的最短路径及距离
int j,p,n,s,e;
if (D[v1]<12) p=3;
else if (D[v1]<23) p=4;
else if (D[v1]<34) p=5;
else if (D[v1]<45) p=6;
else if (D[v1]<56) p=7;
else if (D[v1]<67) p=8;
else p=9;
if (v0<27) s=1;
else if (v0<42) s=2;
else if(v0<64) s=3;
else if(v0<78) s=4;
if (v1<27) e=1;
else if (v1<42) e=2;
else if(v1<64) e=3;
else if(v1<78) e=4;
switch(s*10+e)
{ case 11:
case 22:
case 33:
case 44:
case 23: n=0; break;
case 12:
case 32:
case 42:
case 21:
case 24:
case 31:
case 13:
case 14:
case 34:
case 41:
case 43: n=1; break;
}
// for(v=1;v <=G.vexnum;v++)
{if(P[v1][0]==0) //continue; //表明顶点v0到顶点v没有通路
cout << "全程用时"<<D[v1] <<"分钟"<< endl;
cout << "全程需转站"<< n <<"次"<< endl;
cout << "票价为"<<p <<"元"<< endl;
cout<< "从"<< a[v0-1] <<"站到"<< a[v1-1]<<"站的最短线路为:"<<endl;
cout << a[v0-1] ;
for(j=0;P[v1][j]!=0;j++) cout <<"-> "<< a[P[v1][j]-1];
cout << endl;
}
}
我已在mfc中已添加了此文件的“***.cpp”文件,现在想在对话框类中调用该文件的一些变量,我该加头文件应该是加include"***.h",这是控制台编程,只有 .cpp 文件,我怎么生成它?
急求大神,等待中。。
#include <string>
#include <fstream>
using namespace std;
#define INFINITY 30000 //定义一个权值的最大值
#define VERTEX_NUM 80 //图的最多顶点数 enum BOOL {False,True};
class Graph
{public:
int arcs[VERTEX_NUM][VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点和边数
}; void CreateGraph(Graph &); //生成图的邻接矩阵
void ShortestPath_DiJ(Graph,int,int[][VERTEX_NUM],int[]);
//用迪杰斯特拉算法求从某一源点到其余顶点的最短路径
void Print_ShortestPath(Graph,int,int,int[][VERTEX_NUM],int[],char [][20]);
//显示最短路径
void Trans( char a[][20] );
//将数字转换为中文站名int main()
{ Graph G; //采用邻接矩阵结构的图
char a[VERTEX_NUM][20]; //转换矩阵
char j='y';
int u,t; //起始顶点号
int P[VERTEX_NUM][VERTEX_NUM]; //存放从源点到各顶点的最短路径
int D[VERTEX_NUM];
Trans(a) ;
cout<<"请输入你所选择的起点和终点:"<<endl;
while(j!= 'N '&&j!= 'n ')
{CreateGraph(G); //生成邻接矩阵结构的图
cin>>u>>t;
ShortestPath_DiJ(G,u,P,D); //利用迪杰斯特拉算法求最短路径
Print_ShortestPath(G,u,t,P,D,a); //显示最短路径
cout<< "最短路径演示完毕,继续进行吗?(Y/N) ";
cin>>j;
}
return 0;
} void Trans( char a[][20])
{
ifstream in_file;
in_file.open("D:\\translate.txt",ios::in);
for (int i=0; i<VERTEX_NUM;i++) in_file>>a[i];
in_file.close();
}void CreateGraph(Graph &G)
{//构造邻接矩阵结构的图G
ifstream in_file;
in_file.open("D:\\graphinfo.txt",ios::in);
int i,j;
int start,end,weight;
//cout<< "请输入图的顶点数和弧数(顶点数,弧数): \n";
//cin>>G.vexnum>>G.arcnum; //输入图的顶点数和边数
in_file >> G.vexnum>>G.arcnum;
for(i=1;i <=G.vexnum;i++)
for(j=1;j <=G.vexnum;j++)
G.arcs[i][j]=INFINITY; //初始化邻接矩阵
//cout<< "输入各弧和权值,格式:弧尾,弧头,权值\n ";
for(i=1;i <=G.arcnum;i++)
{ //cin>>start>>end>>weight; //输入边的起点和终点及权值
in_file >>start>>end>>weight;
G.arcs[start][end]=weight;
G.arcs[end][start]=weight;
}
in_file.close();
} void ShortestPath_DiJ(Graph G,int v0,int P[][VERTEX_NUM],int D[])
{//用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]
//若P[v][0]≠0,表明从源点出发存在一条到顶点v的最短路径,该路径存放在P[v]中
//final[v]为True则表明已经找到从v0到v的最短路径
int i,j,w,v;
int min;
BOOL final[VERTEX_NUM];
for(v=1;v <=G.vexnum;v++) //初始化
{final[v]=False; D[v]=G.arcs[v0][v];
for(i=0;i <=G.vexnum;i++) P[v][i]=0; //设空路径
//if(D[v] <INFINITY) P[v][0]=v0; //若从v0到v有直达路径
}
D[v0]=0; final[v0]=True; //初始时,v0属于S集
//开始主循环,每次求得v0到某个顶点v的最短路径,并加v到S集
for(i=1;i <=G.vexnum;i++) //寻找其余G.vexnum-1个顶点
{v=0;
min=INFINITY;
for(w=1;w <=G.vexnum;w++) //寻找当前离v0最近的顶点v
if((!final[w])&&(D[w] <min))
{v=w;min=D[w];}
if(!v) break; //若v=0表明所有与v0有通路的顶点均已找到了最短路径,退出主循环
final[v]=True; //将v加入S集
for(j=0;P[v][j]!=0;j++) ;
P[v][j]=v; //将路径P[v]延伸到顶点v
for(w=1;w <=G.vexnum;w++) //更新当前最短路径及距离
if(!final[w]&&(min+G.arcs[v][w] <D[w]))
{ D[w]=min+G.arcs[v][w];
for(j=0;P[v][j]!=0;j++) P[w][j]=P[v][j];
}
}
} void Print_ShortestPath(Graph G,int v0,int v1,int P[][VERTEX_NUM],int D[],char a[][20])
{//显示从顶点u到其余顶点的最短路径及距离
int j,p,n,s,e;
if (D[v1]<12) p=3;
else if (D[v1]<23) p=4;
else if (D[v1]<34) p=5;
else if (D[v1]<45) p=6;
else if (D[v1]<56) p=7;
else if (D[v1]<67) p=8;
else p=9;
if (v0<27) s=1;
else if (v0<42) s=2;
else if(v0<64) s=3;
else if(v0<78) s=4;
if (v1<27) e=1;
else if (v1<42) e=2;
else if(v1<64) e=3;
else if(v1<78) e=4;
switch(s*10+e)
{ case 11:
case 22:
case 33:
case 44:
case 23: n=0; break;
case 12:
case 32:
case 42:
case 21:
case 24:
case 31:
case 13:
case 14:
case 34:
case 41:
case 43: n=1; break;
}
// for(v=1;v <=G.vexnum;v++)
{if(P[v1][0]==0) //continue; //表明顶点v0到顶点v没有通路
cout << "全程用时"<<D[v1] <<"分钟"<< endl;
cout << "全程需转站"<< n <<"次"<< endl;
cout << "票价为"<<p <<"元"<< endl;
cout<< "从"<< a[v0-1] <<"站到"<< a[v1-1]<<"站的最短线路为:"<<endl;
cout << a[v0-1] ;
for(j=0;P[v1][j]!=0;j++) cout <<"-> "<< a[P[v1][j]-1];
cout << endl;
}
}
我已在mfc中已添加了此文件的“***.cpp”文件,现在想在对话框类中调用该文件的一些变量,我该加头文件应该是加include"***.h",这是控制台编程,只有 .cpp 文件,我怎么生成它?
急求大神,等待中。。
解决方案 »
免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货