设计、实现一个全国大城市间的交通咨询程序

设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。 二、实验要求 （1）选取合适的数据结构存储带权路线图 （2）实现单源最短路径算法

/*
此题为了方便测试，已经将所有图相关数据存入了in.txt文件
并且对于自己输入的希望看到的相关城市信息，直接打印出所有情况。 
*/


#include  
#include  
using namespace std;  
/*邻接矩阵的类型定义*/  
#define MAX 10000000  
#define MAX_VERTEX_NUM 20  
typedef struct  
{  
    string vexs[MAX_VERTEX_NUM];//用一维数组存储顶点信息  
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二维数组充当矩阵，来存储顶点花销边的信息
	int edges2[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二维数组充当矩阵，来存储顶点时间边的信息  
    int vexnumedgenumedgenum2;//顶点树和边数  
}MGraph;  

/*构造有向网的邻接矩阵*/  
void CreateDN_AM（MGraph &Gint nint e）  
{  
    G.vexnum=n;  
    G.edgenum=e;  
      
    int ijk;  
    int weight;
	cout<<“所有城市信息如下：请对应顺序输入“<    for（i=0;i        {
       	cin>>G.vexs[i];    //输入顶点信息 
		cout<        }
    for（i=0;i        for（j=0;j            {
            G.edges[i][j]=MAX;//将矩阵初始化为MAX
			G.edges2[i][j]=MAX;//将矩阵初始化为MAX 
            }
	//下面初始化花销边信息		 
    for（k=0;k    {  
        cin>>i>>j>>weight;  
        G.edges[i][j]=weight; 
    }    
    //下面初始化时间边信息
    for（k=0;k    {  
        cin>>i>>j>>weight;  
        G.edges2[i][j]=weight;  
    }    
}  

void ShortestPath_DJ（MGraph &Gint v）  
{  
    int ijkk2minmin2;  
    int final[MAX_VERTEX_NUM];  //该数组用来标识顶点是否已确定了最短路径，花销  
    int dist[MAX_VERTEX_NUM];   //dist[i]记录顶点i到 v 的最短距离 
    string path[2*MAX_VERTEX_NUM];  
    
    int final2[MAX_VERTEX_NUM]; //该数组用来标识顶点是否已确定了最短路径，时间  
    int dist2[MAX_VERTEX_NUM];  //dist2[i]记录顶点i到 v 的最短距离 
    string path2[2*MAX_VERTEX_NUM];
    
    int zhongzhuan[MAX_VERTEX_NUM];//记录中转次数 
    string path3[2*MAX_VERTEX_NUM]; 
    
    cout<<“下面是最短时间排序：“<	for（i=0;i    {//初始化工作  
        dist2[i]=G.edges2[v][i];//dist数组用来存储当前找到的v到其他各顶点的最短路径  
        if（dist2[i]            {
            	//cout<<“dist2[“<            	path2[i]=G.vexs[v]+“-->“+G.vexs[i];//如果v到i有边的话，把顶点字符存到path字符数组中，表示路径 
            } 
        else  
            path2[i]=“#“;  
        final2[i]=0;//初始化标识数组为0  
    }  
    dist2[v]=0;  
    final2[v]=1;  //将顶点v加入顶点集合 
    for（j=1;j    {  
        min2=MAX;  
        for（i=0;i            {
            	//cout<<“dist2[“<            	if（dist2[i]            	{  
                min2=dist2[i];  
                k2=i;  
            	}          //找到dist数组中最小值的位置k  
            }
        cout<        final2[k2]=1;//设置标志位  
        for（i=0;i        {//遍历每个顶点i和当前的已求出的最短路径的顶点k作比较，若从源点经过顶点k到顶点i的路径，比dist[i]小，  
            //则更新顶点dist[i]  
            if（dist2[i]>dist2[k2]+G.edges2[k2][i] && final2[i]==0）  
            {  
                
                dist2[i]=dist2[k2]+G.edges2[k2][i];
				//cout<<“dist[k2]:“<


 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       6220  2016-12-09 13:13  homework5.cpp

     文件     609614  2016-12-09 13:13  homework5.exe

     文件        339  2016-12-04 00:18  in.txt

     文件      13908  2016-12-18 13:23  问题描述.docx

----------- ---------  ---------- -----  ----

               630081                    4