OpenGraph_P(GP); //打开已经存在飞机的数据
Main_Menu(GT,GP);
SaveGraph_T(GT); //保存火车数据
SaveGraph_P(GP); //保存飞机数据
DestoryGraph(GT);
DestoryGraph(GP);
}
/****<迪杰斯特拉算法求取最少钱数和最短时间>*********/
10．print_Money(GT,p)算法流程图
11．LeastMoneyPath(GT,st,nd,p)算法流程图
11．ShortestTimePath(GT,st,nd,p)算法流程图
12．Manage_Menu(GT,GP)算法流程图
13．City_Edit(GT,GP)算法流程图
14.Train_Edit(GT,GP)算法流程图
在程序中，利用迪杰斯特拉算法求花钱最少和花时间最少的交通方式。
三、概要设计
1
2
3．打开图算法流程图：
4．主菜单操作算法流程图：
5．咨询菜单流程图
6．咨询钱最少模块图
7．input_Money(Graph G, int &st,int &sn)算法流程图
8．inputVex(G,st)算法流程图
9．LocateVex(G,name,i)算法流程图
bool SaveGraph_P(Graph G);
void main()
{
Graph GT; //火车交通图
Graph GP; //飞机交通图
CreateGraph(GT); //建立空的火车交通图
CreateGraph(GP); //建立空的飞机交通图
OpenGraph_T(GT); //打开已经存在火车的数据
EdgeInfo t; //边的信息
bool found;
int min=9999,min_i,v,w;
for(i=0;i<MAXVTXNUM;i++) //初始化
{
dijkst[i]=9999;
InitPath(path[i]); //path[i].len=0;
}
p=G.Adjlist[st].firstEdge;
//设int dijkst[MAXVTXNUM];Path path[MAXVTXNUM];
int i;
int dijkst[MAXVTXNUM];
bool final[MAXVTXNUM]={false};
Path path[MAXVTXNUM]; //每个顶点都有路径
EdgeNode *p,*q; //边的信息弧结点
}Edge;
typedef struct
{
Edge edges[MAXVTXNUM]; //路径中边的序列: edges[i]表示从起点到i的最短路径
int len; //路径中边的数目
}Path;
/************<路径基本操作>**********************/
void copyPath (Path &p1,Path &p2)
//设int dijkst[MAXVTXNUM];Path path[MAXVTXNUM];
int i;
int dijkst[MAXVTXNUM];
bool final[MAXVTXNUM]={false};
int now[MAXVTXNUM];
Path path[MAXVTXNUM];
EdgeNode *p,*q;
（1）提供对城市信息进行编辑（如：添加和删除）的功能.
（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班表进行编辑（增加或删除）的功能。
（3）提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。
（4）旅途中耗费的总时间应该包括中转站的等候时间。
（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘哪趟列车或哪一次班机到何地。
}
void ShortestTimePath(Graph G, int st, int nd, int n ,Path &pathA)
{
//st：起点号，nd：终点号，n：当前时间（秒），结果存储在pathA中
//利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条
//最短路径PathInfo,路径长度pathLength
全国交通咨询模拟系统
全国交通咨询模拟系统
一、
旅客对由于出行目的的不同对交通工具的要求也有不同。例如，因公事出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。为了能满足广大旅客的需求，方便旅客出行，就此编制一个全国城市间的交通咨询程序，为旅客提供两种或者三种最优决策的交通咨询，达到如下的基本要求:：
{
//复制路径p1=p2
int i;
for(i=0;i<p2.len;i++)
{
p1.edges[i].vx=p2.edges[i].vx;
p1.edges[i].vy=p2.edges[i].vy;
p1.edges[i].p =p2.edges[i].p;
}
p1.len=p2.len;
}
void SetPath(Path &pa, int v, int w, EdgeInfo t)
EdgeInfo t;
bool found;
int min=99999,min_i,v,w,time;
for(i=0;i<MAXVTXNUM;i++) //初始化
{
dijkst[i]=99999;
InitPath(path[i]);
now[i]=0;
}
now[st]=n;
p=G.Adjlist[st].firstEdge;
while(p) //初始化dijkst数组，检测依附于起始点的每一条边
{
q=p->nextEdge;
if(p->elem.StartTime<now[st]&&p->elem.EndTime>=now[st])
{
time= 1440-TimeSub(p->elem.EndTime,now[st]);
if(min_i==nd)
found=true;
else
{wk.baidu.com
v=min_i;
p=G.Adjlist[v].firstEdge;
while(p)
{
q=p->nextEdge;
w=p->elem.jvex;
if(final[w]==false &&((dijkst[v]+p->elem.Money)<dijkst[w]))
{
dijkst[w]=dijkst[v]+p->elem.Money;
copyPath(path[w],path[v]);
InsertPath(path[w],v,w,p->elem);
}
p=q;
} //while(p)
} //else
}// while(!found)
copyPath(pathA,path[nd]);
#include "Time.h"
#include "Path.h"
#define NULL 0
bool OpenGraph_T(Graph &G);
bool OpenGraph_P(Graph &G);
int Main_Menu(Graph >,Graph &GP);
bool SaveGraph_T(Graph G);
}
p=q;
}
found= false;
while(!found)
{
//在所有未求得最短路径的顶点求使得dijkst[i]取最小的i
for(i=0;i<MAXVTXNUM;i++)
{
if(final[i]==false && dijkst[i]<min)
min_i=i;
}
final[min_i]=true;
void LeastMoneyPath(Graph G, int st, int nd, Path &pathA)
//st：起点号，nd：终点号，结果存储在pathA中
//path包括路径的长度，起点，终点和路径信息
{
//利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条
//最短路径PathInfo,路径长度pathLength
{
EdgeInfo elem;
EdgeNode *nextEdge;
}EdgeNode, *EdgePtr;//边的结点类型，指向边的指针
typedef struct //城市信息头结点
{
char cityName[10];
int cityNumber;
EdgePtr firstEdge; //指向的一条依附该顶点的边的指针
while(p) //初始化dijkst数组，检测依附于起始点的每一条边
{
q=p->nextEdge;
if(p->elem.Money<dijkst[p->elem.jvex])
{
dijkst[p->elem.jvex]=p->elem.Money;
t=p->elem;
SetPath(path[p->elem.jvex],st,p->elem.jvex,t);
注释：部分算法的设计思想相同，只是参数不同，故省略部分程序流程图。
四、
#define MAXVTXNUM 30 //图中顶点数的最大值
/************顶点、边和图类型**********************************/
typedef struct //定义各车次及航班的信息 弧的信息
if(minute>60)
{
hour=hour+minute/60;
minute=minute%60;
}
if(hour>24)
{
hour=hour%24;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Graph.h"
/*****************图的基本操作**********************/
/************路径类型*************************/
typedef struct
{
int vx,vy; //vx为路径的起点,vy为路径的终点
EdgeInfo p; //路径中边的信息
now[p->elem.jvex]=p->elem.EndTime;
}Vnode; //顶点类型
typedef struct //图的结构
{
Vnode Adjlist[MAXVTXNUM];//邻接表
int vexNum, edgeNum; //图中的顶点数和边数
int Flag[MAXVTXNUM]; //标志是否是图中的顶点,0表示不是,1表示是
}Graph; //图类型
{
///设置pa从v到w的第一条边,边的信息为t
pa.edges[0].vx=v;
pa.edges[0].vy=w;
pa.edges[0].p=t;
pa.len=1;
}
#include <iostream.h>
int TimeChange(int hour,int minute)
{ //把输入的小时和分钟树转换成分钟的形式，忽略天数
}
else
time= TimeSub(p->elem.EndTime,now[st]);
if(time<dijkst[p->elem.jvex])
{
dijkst[p->elem.jvex]=time;
t=p->elem;
SetPath(path[p->elem.jvex],st,p->elem.jvex,t);
（6）通过对比以及用户操作基本达到旅客出行的便利。
二、
此次课程设计是对全国城市交通图列车时刻表及飞机航班表的编辑。此次课设是利用VC工具在dos环境下实现全国交通的咨询与管理。通过此次程序可以对全国城市之间火车与飞机进行两方面的咨询，即最少的时间与最少的费用的咨询，从而方便旅客的出行。通过此次课程设计，我要学会怎样用在VC dos环境下编程，而且要通过此次课程设计加深对数据结构的理解，在设计中用邻接表作交通图的存储结构，表示边的结点中除含有邻接点的信息外，还包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等属性。图中顶点城市的信息，包括城市名称、城市编号和依附该顶点的边的指针。
{
int ivex;//起始点号
int jvex;//终点号
char Number[10]; //车次号
int Money; //费用
int StartTime; //起始时间（秒）
int EndTime; //终止时间（秒）
int Time; //中途时间（秒）
}EdgeInfo;//边的信息
typedef struct EdgeNode //边的信息弧结点
