资源描述：
《计算机软件基础课程设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、北京信息科技大学计算机软件基础课程设计题目:学院:专业:从某个源点到其余各顶点的最短路径信息与通信工程学院通信工程专业学生姓名:班级/学号指导老师：起止时间：至任务书题目7从某个源点到其余各顶点的最短路径（难度系数9）主要内容1、假设西安、北京、沈阳、武汉4个城市构成小型交通网，4个城市表示图的4个顶点，他们构成了无向连通图。以北京为源点，求北京到西安的最短路径；求北京到沈阳的最短路径；求北京到武汉的最短路径。2、学会建立图的邻接表，理解图的基本概念。3、学会编写DLL函数。4、根据自己构建的连通图，利用Dijkstra算法求从某个源点到其余各顶点的最短路径。5、掌握C++编程环
2、境的基本调试方法，熟练使用可视化C++编程工具。设计要求1、上交课程设计的书面材料，要求打卬。包括课程设计任务书、主要内容，源程序，对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。2、上交电子版源程序，包括邻接表建立程序、Dijkstra算法。3、自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函数中调用它。尝试把自己编写的程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用函数生成的EXE执行文件。主要仪器设备计算机一台,安装Window
3、sXP操作系统、MicrosoftVisualC++6.0、MSDNLibraryo主要参考文献[1]侯俊杰.深入浅出MFC（第二版）[M].武汉：华中科技大学出版社,2001.[2]谭浩强.C程序设计（第二版）[M].北京：清华大学出版社，1999..[3]孟彩霞.计算机软件基础[M].陕西：西安电子科技大学出版社,2003.[4]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社,2005.课程设计进度计划（起止时间、工作内容）选做最短路径题目的同学，2人1组，1人做Dijkstra算法，1人做Floyd算法，整个课程设计共20学时，具体进度如下：4学时了解课题背景，选题，
4、学习DLL,学习图的基本概念。4学时编写邻接表建立程序。4学时Dijkstra算法。4学时尝试利用Dijkstra算法求任意两个顶点之1'可的最小距离。4学时调试程序，答辩。课程设计开始日期课程设计完成日期课程设计实验室名称计算中心机房地点健翔桥校区目录任务书：2摘要内容：(宋体小四)200〜400字左右3连通图：3邻接矩阵为：4源程序：4结果：8总结：10参考文献10摘要(宋体三号，加粗)内容：(宋体小四)200-400字左右总程序可实现的功能为：1.能实现单元点到各个定点的最短路径生成。具体实现为：能从任一城市出发，算出里另外三个城市的最短距离。2.能查询两个顶点之间的最短路
5、径。例如：能查询武汉到四安的最短路径为1025kmFloyd算法简介：Floyd算法又称为弗洛伊徳算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。核心思路是：其通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(iJ)]nxn开始，递归地进行n次更新，即由矩阵D(0)=A,按一个公式，构造出矩阵D(l)；又用同样地公式由D(l)构造出D(2)；……；最后又用同样的公式由D(n・l)构造出矩阵D(n)0矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间
6、的最短路径。连通图:邻接矩阵为:{0,732,1159,1200}；{732,0,2092,1912}；{1159,2092,0,1025}；{1200,1912,1025,0}；源程序：#include"stdio.h"#include,,stdlib.hM#defineMVNum4〃最大顶点数#defineMaxinl40000enumboolean{FALSE,TURE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];〃顶点数组，类型假定为char型Adjmatri
7、xarcsfMVNum][MVNum];〃邻接矩阵，类型假定为int型}MGraph;intDI[MVNum],PI[MVNum];intDrMVNum]fMVNum],P[MVNum][MVNuml;/*建立冇向图的存储结构*/voidCreateMGraph(MGraph*G,intn,inte){〃采用邻接矩阵表示法构造有向图G,n和e表示图的顶点数和边数n=4;e=12;inti,j;for(i=l;i<=4;i++)G->vexs[i]=i;for(i=l;i<=4;i
