交通指南系统 ---c语言课程设计

古城微笑少年丶 2022-05-21 09:57 191阅读 0赞

**主要内容：**

假设以一个带权有向图表示某一区域的公交线路图，图中顶点代表一些区域中的重要站点，弧代表已有的公交路线，弧上的权表示该路线上的票价（或搭乘所需时间），设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一站点到达另一站点。

**基本要求：**

（1）设计结点和图的存储结构。

（2）设计任意两点最短路径方法。

（3）输入：图的相关信息以建立公交线路网，以及公交线路网咨询的任意两个站点。

（4）输出：两个站点间一条最短的简单路径。

**扩展功能（任选）：**

（1）如何判断任意两点是否都存在最低的票价或最少的时间可以到达。

（2）如何对程序进行修改，找一条转乘次数最少的公交线路。

**一、主要函数模块说明**

voidCreateGraph(Graph &G,Graph &G1);

生成图的邻接矩阵的函数，这个是在下面是用其他函数的前提条件。

voidShortestPath\_DiJ(Graph G,int,int\[\]\[MAX\_VERTEX\_NUM\],int\[\]);

迪杰斯特拉算法，用于求从某一源点到其余顶点的最短路径，这个是本程序的最主要的算法。完成这个算法，就完成了本系统的一般功能。

voidPrint\_ShortestPath(Graph G,int,int\[\]\[MAX\_VERTEX\_NUM\],int\[\]);

显示某点与其它点的最短路径

void Print\_ShowPath(GraphG,int v0,int v1,int P\[\]\[MAX\_VERTEX\_NUM\],int D\[\]); 显示两点之间的最短路径

voidPrint\_ShowChagePath(Graph G,int v0,int v1);

显示两点之间转站次数最少的路径，使用构造生成图的时构造的G1图。

main.cpp
    
    #include<stdio.h>
    
    //#include<stdlib.h>
    
    //#include<string.h>
    
    #define INFINITY1000    //定义一个权值的最大值
    
    #defineMAX_VERTEX_NUM 20 //图的最大顶点数
    
    enum BOOL{False,True};
    
    typedef struct
    
    {
    
        int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
    
        int vexnum,arcnum;                //图的当前顶点和边数
    
    } Graph;
    
    voidCreateGraph(Graph &G,Graph &G1);   //生成图的邻接矩阵
    
    voidShortestPath_DiJ(Graph G,int,int[][MAX_VERTEX_NUM],int[]);     //用迪杰斯特拉算法求从某一源点到其余顶点的最短路径
    
    voidPrint_ShortestPath(Graph G,int,int[][MAX_VERTEX_NUM],int[]);     //显示某点与其它点的最短路径
    
    voidPrint_ShowPath(Graph G,int v0,int v1,int P[][MAX_VERTEX_NUM],int D[]); //显示两点之间的最短路径
    
    voidPrint_ShowChagePath(Graph G,int v0,int v1);   //显示两点之间转站次数最少的路径
    
    
    
    int  main()
    
    {
    
        Graph G,G1; //采用邻接矩阵结构的图
    
        char j='y';
    
        int u,v;
    
        int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径
    
        int D[MAX_VERTEX_NUM];                 //存放从源点到各顶点的最短路径的距离
    
    
    
        printf("\n\n");
    
        printf("~~~~~~~~~~~~欢迎光临城市交通指南系统~~~~~~~~~~~~~\n\n为了给您带来更美好的体验.请先阅读演示程序\n\n");
    
        printf("*******演示本程序的使用方法*******\n");
    
        printf("首先输入图的顶点数和弧数.\n\t格式：顶点数 弧数(数据之间用空格隔开)；\n\t例如: 5 7\n");
    
        printf("然后输入各弧和权值.\n\t格式：起点 终点花费(数据之间用空格隔开)；\n\t例如: 1 2 10\n\t      1 3 18\n\t      2 4 5\n\t      3 2 5\n\t      4 3 2\n\t      4 5 2\n\t      5 3 2\n");
    
        printf("再输入从哪个起点出发，例如:1\n");
    
        printf("再输入从哪个终点结束，例如:4\n");
    
        printf("程序将会找出从1到4的最少花费和最短路径.\n");
    
        printf("15  1->2->4\n");
    
        printf("程序将会找出从1到其余顶点的最少花费和最短路径.\n");
    
        printf("10  1->2\n17 1->2->4->3\n15 1->2->4\n17 1->2->4->5\n");
    
        printf("*******演示程序执行完毕*******\n\n");
    
        while(j!='N'&&j!='n')
    
        {
    
            CreateGraph(G,G1);       //生成邻接矩阵结构的图
    
            if(!G.arcs)  return 0;
    
            printf("起始点为:\n");
    
            scanf("%d",&u);  //输入迪杰斯特拉算法中的起始顶点
    
            printf("终止点为:\n");
    
            scanf("%d",&v);  //输入迪杰斯特拉算法中的终点顶点
    
            ShortestPath_DiJ(G,u,P,D); //利用迪杰斯特拉算法求最短路径
    
            Print_ShowPath(G,u,v,P,D);  //显示起始点到终止点的最短路径
    
            printf("\n");
    
            Print_ShowChagePath(G1,u,v);    //显示两点之间的最少转站路径
    
            printf("\n");
    
            Print_ShortestPath(G,u,P,D); //显示起始点到其他各点的最短路径
    
            printf("\n");
    
            printf("程序执行完毕，继续进行吗?(Y/N)(不区分大小写)\n");
    
            scanf(" %c",&j);
    
            while(j != 'y' && j != 'Y'&& j != 'n' && j != 'N')
    
            {
    
                printf("输入错误！是否继续执行程序？(Y/N)(不区分大小写)\n");
    
                scanf(" %c",&j);
    
            }
    
        }
    
        return 0;
    
    }
    
    voidCreateGraph(Graph &G,Graph &G1) //构造邻接矩阵结构的图G
    
    {
    
        int i,j;
    
        int start,end,weight;
    
        printf("请输入图的顶点数和弧数(顶点数 弧数)(数据之间用空格隔开):\n");
    
        scanf("%d%d",&G.vexnum,&G.arcnum); //输入图的顶点数和边数
    
        G1.vexnum=G.vexnum;G1.arcnum=G.arcnum;
    
        if(G.vexnum > 20){
    
            printf("图的最大顶点数为20，超过20程序执行错误。\n");
    
            return;
    
        }
    
        for(i=1; i<=G.vexnum; i++) for(j=1;j<=G.vexnum; j++){
    
            G.arcs[i][j]=INFINITY; //初始化邻接矩阵
    
            G1.arcs[i][j]=INFINITY;
    
        }
    
        printf("输入各弧和权值，格式：起点终点 花费(数据之间用空格隔开):\n");
    
        for(i=1; i<=G.arcnum; i++)
    
        {
    
           scanf("%d %d %d",&start,&end,&weight); //输入边的起点和终点及权值
    
            G.arcs[start][end]=weight;         //邻接矩阵输入权值（花费大小）
    
            G1.arcs[start][end]=1;
    
        }
    
    }

**系统部分源代码**

**六、系统测试结果及分析**

1.    给出测试数据

5个顶点，5条边。

起点 终点花费 ：如下

1 2 2

1 3 2

2 4 3

2 5 3

3 4 2

测试所用交通线路图如下所示：

![70][]

2.开始进行对系统的测试

a．系统的首页面

![70 1][]

b．先输入数据，数据如上步已给出。

c．输入起始点与终止点

测试已存在数据数据，如起始点1，终止点4.程序执行结果如下：

![70 2][]

从测试所用的交通线路图上可以得到答案，本程序的测试结果是正确的。

对于其他的测试结果，多输入了几个，也得到了正确的结果，便不再演示。

d．对有针对性的测试数据进行测试

如测试起点为5的，因为在有向交通线路图中顶点5无可达顶点。

![70 3][]

由测试交通线路图可以得出，起点为5，确实到不了任何一个地方，系统也给出了友好提示，以便用户再次查询。

e．对于不存在数据的异常情况

如输入起点8，终点9的不存在数据，系统的反应如下图所示：

![70 4][]

如第d步的测试类似，系统会给出输入顶点有误或者花费有误的提示，表示出客户所给出的数据可能是一个异常数据，并提示客户是否继续进行程序。不进行则退出系统。

源代码下载地址。

[https://download.csdn.net/download/iiiiiilikangshuai/11224119][https_download.csdn.net_download_iiiiiilikangshuai_11224119]

[70]: /images/20220521/7eebbdc7aea6476db060eb504f3cc1a0.png
[70 1]: /images/20220521/82ae256fa7774edaad7d081ddbc52081.png
[70 2]: /images/20220521/1f910b1a163640f5b91d659a09f3cb13.png
[70 3]: /images/20220521/863d4c53f44e423893a07ad58559d48a.png
[70 4]: /images/20220521/4887e2cbcd564c6cb023891900307db0.png
[https_download.csdn.net_download_iiiiiilikangshuai_11224119]: https://download.csdn.net/download/iiiiiilikangshuai/11224119