图查询图中任意两个景点间的最短路径。
山东理工大学计算机学院课程设计
（数据结构）
班级计科1002
姓名李继柱
学号1011051059
指导教师刘晓红
二○一一年一月十日
课程设计任务书及成绩评定
课题名称图遍历的应用
Ⅰ、题目的目的和要求：
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
Ⅱ、设计进度及完成情况
Ⅲ、主要参考文献及资料
[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999
[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999
[3] 谭浩强 C语言程序设计清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定：
设计成绩：（教师填写）
指导老师：（签字）
二○一一年一月十日
目录
第一章概述 (1)
第二章系统分析 (2)
第三章概要设计 (3)
第四章详细设计 (4)
第五章运行与测试 (11)
第六章总结与心得 (12)
参考文献 (13)
第一章概述
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是图遍历的应用。和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。本程序是以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。
第二章系统分析
1. 以邻接多重表为存储结构，实现连通无向图的深度优先个广度优先遍历。
2. 设图的结点不超过30个，每个结点用一个编号。通过输入图的全部边输入一个图，每个边为一个数对。
3. 以用户指定的结点，来输出其邻接结点，并且输出每种遍历下的结点访问序列。
4. 演示程序使用C++语言。
5. 本程序的运行环境为windows操作系统，执行的文件为：图遍历（邻接多重表）.cpp。
6.进入程序即显示提示信息：
输入无向图顶点的数目和弧的数目：
待用户将顶点数和弧的数目输入，敲回车键，便会继续显示提示信息。
7. 测试数据。教科书图7.33。<北京，天津>、<天津，徐州>、<徐州，郑州>、<郑州，北京>、<天津，沈阳>、<沈阳，大连>，暂时忽略里程。起点为北京。
1、数据结构的设计
因课程要求，程序采用图的邻接多重表结构。邻接多重表和邻接表类似，主要差别在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。
2、算法的设计
本程序包含四个模块：
1）主程序模块：
int main()
{
处理命令
}
2）邻接多重表的构造模块
3）深度优先遍历模块
4）广度优先遍历模块
各模块之间的调用关系如下：
3、抽象数据类型的设计
struct EBox
{
int mark;
int ivex,jvex;
EBox *ilink,*jlink;
};
struct VexBox
{
string data;
EBox *firstedge;
};
class amlgraph
{
private:
VexBox *adjmulist;
int vexnum;
int arcnum;
int maxnum;
public:
各功能函数的定义
};
1、设计抽象数据类型对应的类定义。
struct EBox
{
int mark;
int ivex,jvex;
EBox *ilink,*jlink;
};
struct VexBox
{
string data;
EBox *firstedge;
};
class amlgraph
{
private:
VexBox *adjmulist;
int vexnum;
int arcnum;
int maxnum;
public:
各功能函数的定义
};
2、设计每个成员函数
amlgraph(int num=30)
{
adjmulist=new VexBox[num];
maxnum=num;
}
~amlgraph()
{
delete[]adjmulist;
}
int Locate_Vex(string v) //定位顶点在顶点数组中的位置{
for(int i=0;i if(adjmulist[i].data == v) return i; return -1; } void CreateUDG_AML()//邻接多重表，存储无向图 { string v1,v2; int i,j,k,s=1; cout<<"输入无向图顶点的数目和弧的数目："; cin>>vexnum>>arcnum; while(vexnum>maxnum) { cout<<"顶点数目太多，请重新输入顶点数和边数："; cin>>vexnum>>arcnum; } cout<<"输入每个顶点的名称："; for(i=0;i { cin>>adjmulist[i].data; adjmulist[i].firstedge=NULL; } for(k=0;k { cout<<"输入第"< cin>>v1>>v2; while(Search_Arc(v1,v2)) { cout<<"该边已存在，本图不支持存在平行边"< cout<<"重新输入边的两个顶点："; cin>>v1>>v2; } i=Locate_Vex(v1); j=Locate_Vex(v2); while(i == -1 || j == -1) { cout<<"两个顶点中有不符合要求的，请重新输入："; cin>>v1>>v2; i=Locate_Vex(v1); j=Locate_Vex(v2); } EBox *p=new EBox; p->ivex=i; p->jvex=j; p->ilink=adjmulist[i].firstedge; p->jlink=adjmulist[j].firstedge; adjmulist[i].firstedge=adjmulist[j].firstedge=p; s++; } cout<<"无向图构造完成"< } bool Search_Arc(string v1,string v2)//搜索对应的边是否存在{ int i,j; EBox *p; i=Locate_Vex(v1); j=Locate_Vex(v2); if(i == -1 || j == -1) { cout<<"顶点错误，该边不存在"< return false; } p=adjmulist[i].firstedge; while(p) { if(p->ivex == i && p->jvex == j) return true; else if(p->jvex == i && p->ivex == j) return true; else if(p->ivex == i) p=p->ilink; else if(p->jvex == i) p=p->jlink; } return false; } void Find_Neighbour(string v)//输出顶点v的邻接顶点{ int i=Locate_Vex(v); if(i == -1) { cout<<"该顶点在图中不存在"< return ; } EBox *p=adjmulist[i].firstedge; if(p) { cout<<"顶点"< while(p) { if(p->ivex == i) { cout< p=p->ilink; } else { cout< p=p->jlink; } } } else cout<<"该顶点无相邻顶点"< } void DFS_Traverse() //深度优先遍历 { for(int i=0;i visited[i]=false; for(i=0;i if(!visited[i]) DFS(i); cout< } void DFS(int v) { visited[v]=true; cout< EBox *p=adjmulist[v].firstedge; while(p) { if(p->ivex == v) { if(!visited[p->jvex]) DFS(p->jvex); p=p->ilink; } else { if(!visited[p->ivex]) DFS(p->ivex); p=p->jlink; } } } void BFS_Traverse() //广度优先遍历 { for(int i=0;i visited[i]=false; for(i=0;i if(!visited[i]) BFS(i); cout< } void BFS(int v) { visited[v]=true; cout< EBox *p; int pos; queue qu.push(v); while(!qu.empty()) { pos=qu.front(); qu.pop(); p=adjmulist[pos].firstedge; while(p) { if(p->ivex == pos) { if(!visited[p->jvex]) { visited[p->jvex]=true; cout< qu.push(p->jvex); } p=p->ilink; } else { if(!visited[p->ivex]) { visited[p->ivex]=true; cout< qu.push(p->ivex); } p=p->jlink; } } } } void Mark_Unvisited() //置边的访问标志为未访问 { int i; EBox *p; for(i=0;i { p=adjmulist[i].firstedge; while(p) { p->mark=0; if(p->ivex == i) p=p->ilink; else p=p->jlink; } } } void Display() //输出邻接多重表 { int i; EBox *p; Mark_Unvisited(); cout<<"顶点："; for(i=0;i cout< cout< cout<<"总共有"< for(i=0;i { p=adjmulist[i].firstedge; while(p) { if(p->ivex == i) { if(!p->mark) { cout< p->mark=1; } p=p->ilink; } else { if(!p->mark) { cout< p->mark=1; } p=p->jlink; } } } } 3、设计主函数 int main() { amlgraph G; G.CreateUDG_AML(); string v,v1,v2; cout<<"请输入顶点名称，将输出其相邻顶点："; cin>>v; G.Find_Neighbour(v); cout< cout<<"邻接多重表结构如下："< G.Display(); cout<<"无向图遍历结果如下"; cout<<"深度优先遍历序列为："; G.DFS_Traverse(); cout<<"广度优先遍历序列为："; G.BFS_Traverse(); return 0; } 第五章运行与测试 1、在程序的调试过程中，经常遇到输入出错的情况，致使程序中断。通过在代码中加入对不同的输入的情况的应对方法问题得以解决。 2、测试数据：测试数据：教科书图7.33，忽略里程，起点为北京。 第六章总结与心得 通过这次的课程设计，巩固和提升了我对图的建立和遍历的掌握。并且发现了自身一些细节上的问题，这在平时是不容易发现的。像一些指针指向问题，稍不注意就会出现错误。另外像一些比较大的程序代码，首先要了解清楚需求，然后画出框图，确定基本步骤，逐步完成代码的编写，每项功能要分步实现，不能过分的急于求成。再有就是程序编译调试过程要从第一个错误改起，调试的过程也是加强知识的过程。 还有在设计过程中，难免会有自己不懂的地方，这是就要及时的相同学或者老师请教，像以后更大的项目设计，一个人的力量肯定是不够的，这时就更需要团队共同的协作才能完成。 参考文献: [1] 严蔚敏、吴伟民主编《数据结构》（C语言版）清华大学出版社 2002 [2] 殷人昆等著《数据结构》（C++版）清华大学出版社 2001 [3] 金远平著《数据结构》（C++描述）清华大学出版社 2005 [4] 许卓群等著《数据结构与算法》高等教育出版社 2004 [5] Frank M.Carrano 等著《数据结构与Ｃ++高级教程》清华大学出版社 2004 [6] 严蔚敏、吴伟民《数据结构习题集》（C语言版）清华大学出版社 最短路径问题 1、①如右图是一个棱长为4的正方体木块，一只蚂蚁要从木块的点面 爬到点B处，则它爬行的最短路径是 _______________ 。 ②如右图是一个长方体木块，已知AB=3,BC=4,CD=2假设一只蚂蚁在点A处, 它要沿着木块侧面爬到点D处，则蚂蚁爬行的最短路径是____________________ 。 2、①如图，要在河边修建一个水泵站，分别向张村、李庄送水，水泵站修在河边什么地方可使所用的水管最短。 *李庄 张村. ②如图，直线L同侧有两点A B，已知A、B到直线L的垂直距离分别为1和3, 两点的水平距离为3,要在直线L上找一个点P,使PA+PB勺和最小。请在图中找出点P的位置，并计算PA+P啲最小值。.B A■ _____________________ L ③要在河边修建一个水泵站，向张村、李庄铺设管道送水，若张村、李庄到河边的垂直距离分别为1Km和3Km张村与李庄的水平距离为3Km则所用水管最短长度为。 A沿木块侧 A B 是一个长方体木块，已知 AB=5,BC=3,CD=4假设一只蚂 蚁在点A D 处，则蚂蚁爬行的最短路径是2、 现要在如图所示的圆柱体侧面 A 点与B 点之间缠一条金丝带（金丝带的宽度 忽略不计），圆柱体高为6cm 底面圆周长为16cm ，则所缠金丝带长度的最小值 为 。 3、 如图是一个圆柱体木块，一只蚂蚁要沿圆柱体的表面从 A 点爬到点B 处吃到 食物，知圆柱体的高为5 cm ,底面圆的周长为24cm 则蚂蚁爬行的最短路径 为 。 5、 在菱形ABCD 中 AB=2 / BAD=60，点E 是AB 的中点，P 是对角线 AC 上 的一个动点，贝S PE+PB 勺最小值为 ___________ 。 6、 如图，在△ ABC 中, AC= BC= 2,Z ACB= 90°, D 是 BC 边的中点，E 是 AB 边 上一动点，则EO ED 的最小值为 ____________ 。 7、 AB 是OO 的直径，AB=2 OC 是O O 的半径，OCL AB,点 D 在 AC 上，AD 二 2CD 点P 是半径OC 上的一个动点，贝S AP+PD 勺最小值为 __________ 。 &如图，点P 关于OA OB 的对称点分别为 C D,连接CD 交OA 于M 交OB 于N 若CD= 18cm 则厶PMN 勺周长为 ___________ 。 9、已知，如图DE >^ ABC 的边AB 的垂直平分线，D 为垂足，DE 交BC 于 E ,且 AC= 5, BC= 8,则厶 AEC 的周长为 __________ 。 10、已知，如图，在△ ABC 中, AB 算法设计与分析大作业 班级：物联网1401 学号： 姓名：zk 江南大学物联网工程学院 一、多项式分治 1.1算法简介 分治字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 因为多项式的表示是Pn(x)= a n x n＋a n-1x n-1＋…＋a1x＋a0 任意大整数都可以看作是一多项式（其中X=10，a n是第n+1位上的数字，个位用a0表示）。如：9876=6+7*101+8*102+9*103 所以大整数相乘可以用多项式乘积的分治算法实现，实际上大整数相乘就是多项式乘积的一个特例。把一个多项式分为两个 P (x)= P0(x)+ P1(x)x n/2 q(x)=q0(x)+q1(x)x n/2 P(x)*q(x)=P0(x)*q0(x)+P1(x)*P1(x)*x n+((P0(x)+ P1(x))*( q0(x)+q1(x))- P0 * q0– P1* q1)* x n/2 令：R0= P0(x)*q0(x) R1= P1(x)*q1(x) R2= P0(x)+ P1(x))*( q0(x)+q1(x))- P0 * q0– P1* q1 于是上式可化简为P(x)*q(x)= R0 +（R2- R0- R1）* x n/2+ R1*x n 由于多项式乘法时间远多于加法时间，所以多项式乘积分治算法对比较大的n将有很大的改进。 1.2调试过程 ①在调试过程中poly_product()函数出错，单步调试发现 图1poly_product()错误部分 第16,17行出错，多项式阶数相同系数相加，所以讲r2+k改为r2或17,18行r3改为r3+k 即可。 ②多项式的输入只能是2的倍数。 1.3运行结果 一、课程设计题目：校园最短路径问题 二、课程设计目的： 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规进行软件开发，培养软件工作者所具备的科学工作方法和作风。 三、课程设计要求： 1.设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。 2.编写出课程设计报告书，容不少于10页（代码不算）。 四、需求分析： 1、问题描述 图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。 校园最短路径问题中的数据元素有： a) 顶点数 b) 边数 c) 边的长度 2、功能需求 要求完成以下功能： a)输出顶点信息：将校园各位置输出。 b)输出边的信息：将校园每两个位置（若两个位置之间有直接路径）的距 离输出。 c)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输 出每两个位置（若两个位置之间有直接路径）的距离。 d)求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出 任意一点与其它各点的最短路径。 e)删除：删除任意一条边。 f)插入：插入任意一条边。 3、实现要点 a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。 为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。 b) 为了便于访问，用户可以先输出所有的地点和距离。 c) 用户可以随意修改两点之间好的距离。 d) 用户可以增加及删除边。 e) 当用户操作错误时，系统会出现出错提示。 五、概要设计: 动态规划算法实现多段图的最短路径问题算法设计与分析实验报告 算法设计与分析实验报告 实验名称 动态规划算法实现多段图的最短路径问题 评分 实验日期 年 月 日 指导教师 姓名 专业班级 学号 一.实验要求 1. 理解最优子结构的问题。 有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman ）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。 对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。 最优子结构性质：原问题的最优解包含了其子问题的最优解。 子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。 2.理解分段决策Bellman 方程。 每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。 U s 初始值，u j 第j 段的最优值。 ? ????+==≠}.{min , 0ij i j i j s w u u u 3.一般方法 1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优值（写出动态规划方程）；3）以自底向上的方式计算出最优值； 4）根据计算最优值时得到的信息，构造一个 最优解。 步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。 二.实验内容 1.编程实现多段图的最短路径问题的动态规 划算法。 2.图的数据结构采用邻接表。 3.要求用文件装入5个多段图数据，编写从文件到邻接表的函数。 4.验证算法的时间复杂性。 三.程序算法 多段图算法： Procedure FGRAPH（E,k,n,P） //输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c（i，j）是边 两个计数原理的应用 一、选择题 1．如图，小明从街道的E处出发，先到F处与小红会合，再一起到位于G处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为【答案】B （A）24 （B）18 （C）12 （D）9 【解析】 试题分析：由题意，小明从街道的E处出发到F处最短路径的条数为6，再从F处到G ?=，故处最短路径的条数为3，则小明到老年公寓可以选择的最短路径条数为6318 选B. 【考点】计数原理、组合 【名师点睛】分类加法计数原理在使用时易忽视每类中每一种方法都能完成这件事情，类与类之间是相互独立的；分步乘法计数原理在使用时易忽视每步中某一种方法只是完成这件事的一部分，而未完成这件事，步步之间是相互关联的． 2．如图，一只蚂蚁从点出发沿着水平面的线条爬行到点，再由点沿着置于水平面的长方体的棱爬行至顶点，则它可以爬行的不同的最短路径有（ B ）条 A. 40 B. 60 C. 80 D. 120 【解析】试题分析：蚂蚁从到需要走五段路，其中三纵二竖，共有条路径，从到共有条路径，根据分步计数乘法原理可知，蚂蚁从到可以爬行的不同的最短路径有条，故选B. 考点：分步计数乘法原理. 二、解答题 3．某城市有连接8个小区A、B、C、D、E、F、G、H和市中心O的整齐方格形道路网，每个小方格均为正方形，如图，某人从道路网中随机地选择一条最短路径，由小区A前往H. (1)列出此人从小区A到H的所有最短路径(自A至H依次用所经过的小区的字母表示)； (2)求他经过市中心O的概率． 【答案】(1)见解析（2）2 3 【解析】 解：(1)此人从小区A前往H的所有最短路径为： 中南大学 《数据结构》课程设计 题目第9题 Dijkstra算法求最短路径 学生姓名 XXXX 指导教师 XXXX 学院信息科学与工程学院 专业班级 XXXXXXX 完成时间 XXXXXXX 目录 第一章问题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra算法实现最短路径--------------------------------------------------------------10 第四章上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章测试结果-----------------------------------------------------------------------------------12 第六章学习心得体会-----------------------------------------------------------------------------12 第七章参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12 造价师土建复习:双代号网络计划时间参数的计算 (四双代号网络计划时间参数的计算。此部分看着乱,实际很简单,理清思路也不会很难 1、网络图的计算十分重要。想对网络图进行计算,首先要从它们的基本概念入手,通过分析基本概念就可以得出计算的原理和公式。有的同志经常对基本概念一扫而过,直接去做网络计算题目,这样事倍功半。所以我们要从基本概念入手进行分析。 2、工作最早开始时间,是本工作所有的紧前工作,本工作可以有一个也可以有多个紧前工作,但是需要所有的紧前工作都结束,本工作才可能开始,如果有一个紧前工作没有完成,那么本工作也就不可能开始。所以我们计算工作最早开始时间时要顺着箭线方向依次计算,有两个以上紧前工作的,取所有紧前工作最早完成时间的最大值为本工作的最早开始时间,这也就是我们常说的“顺着箭线计算,依次取大”。起始结点工作最早开始时间为0。 3、工作最早完成时间是指本工作最早开始时间加上本工作必须的持续时间,可以和工作最早开始时间同时计算。终点节点的最早完成时间就是该网络计划的计算工期,我们一般以这个计划工期为工期要求。 4、工作最迟完成时间是指不影响整个任务按期完成的条件下,本工作最迟完成的时间。最后一个工作的终点节点的最早完成时间(计算工期就是最后一个工作的最迟完成时间。 5、用最迟完成时间减去工作的持续时间就是该工作的最迟开始时间。最迟开始时间的含义简单理解就是如果本工作不能在这个时间开始,那么就会影响整个任务的完成,也就是要拖延计算工期。对于最迟开始时间计算的程序是:“逆着箭线计算,依次取小”。 6、总时差,总时差是指一个工作在不影响总工期的条件下,该工作可以利用的机动时间。计算公式是最迟开始时间减最早开始时间或者最迟完成时间减最早完成时 算法设计与分析实验报告 实验名称 动态规划算法实现多段图的最短路径问题 评分 实验日期 年 月 日 指导教师 姓名 专业班级 学号 一.实验要求 1. 理解最优子结构的问题。 有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman ）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。 对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。 最优子结构性质：原问题的最优解包含了其子问题的最优解。 子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。 2.理解分段决策Bellman 方程。 每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。 U s 初始值，u j 第j 段的最优值。 3.一般方法 1） 找出最优解的性质，并刻画其结构特征； 2） 递归地定义最优值（写出动态规划方程）； 3） 以自底向上的方式计算出最优值； 4） 根据计算最优值时得到的信息，构造一个最优解。 步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。 二.实验内容 1.编程实现多段图的最短路径问题的动态规划算法。 2.图的数据结构采用邻接表。 ?? ???+==≠}. {min , 0ij i j i j s w u u u 双代号网络图时间参数的计算一、网络计划的时间参数及符号 二、工作计算法 【例题】：根据表中逻辑关系，绘制双代号网络图，并采用工作计算法计算各工作的时间参数。 （一）工作的最早开始时间ES i-j --各紧前工作全部完成后，本工作可能开始的最早时刻。 （二）工作的最早完成时间EF i-j EF i-j ＝ES i-j + Di-j 1．计算工期T c 等于一个网络计划关键线路所花的时间，即网络计划结束工作最早完成时间的最大值，即T c ＝max ｛EF i-n ｝ 2．当网络计划未规定要求工期T r 时， T p ＝T c 3．当规定了要求工期T r 时，T c ≤T p ，T p ≤T r --各紧前工作全部完成后，本工作可能完成的最早时刻。 （三）工作最迟完成时间LF i-j 1．结束工作的最迟完成时间LF i-j ＝T p 2. 其他工作的最迟完成时间按“逆箭头相减，箭尾相碰取小值”计算。 --在不影响计划工期的前提下，该工作最迟必须完成的时刻。 （四）工作最迟开始时间LS i-j LS i-j ＝LF i-j －D i-j --在不影响计划工期的前提下，该工作最迟必须开始的时刻。 （五）工作的总时差TF i-j TF i-j ＝LS i-j －ES i-j 或TF i-j ＝LF i-j －EF i-j --在不影响计划工期的前提下，该工作存在的机动时间。 （六）自由时差FF i-j FF i-j ＝ES j-k －EF i-j --在不影响紧后工作最早开始时间的前提下，该工作存在的机动时间。 作业1：根据表中逻辑关系，绘制双代号网络图。 咸阳职业技术学院课堂授课计划 教师（签名）：教研室审批：年月日 3.5双代号网络图时间参数的计算 计算方法：图上计算法、分析计算法、表上计算法、矩阵计算法、电算法等。只讲解图上计算法。 1、双代号网络计划各项时间参数的分类及表示符号 设有线路h→i→j→k： （1）节点的时间参数 ①节点的最早时间（TE ）。 i ）。 ②节点的最迟时间（TL i （2）工作的时间参数 ①工作的持续时间（D ） i，j ） ②工作的最早可能开始时间（ES i，j ） ③工作的最早可能完成时间（EF i，j ④工作的最迟开始时间（LS ） i，j ） ⑤工作的最迟完成时间（LF i，j ） ⑥工作的总时差（TF i，j ） ⑦工作的自由时差（FF i，j （3）网络计划的工期 ），由时间参数计算确定的工期，即关键线路的各项工作总 ①计算工期（T C 持续时间。 ），根据计算工期和要求工期确定的工期。 ②计划工期（T P ③要求工期（T ），指合同规定或业主要求、企业上级要求的工期。 r 2、时间参数的计算 时间参数在网络图上的表示方法：P60（图3-40）。 以下内容结合P61（图3-41）讲解： （1）节点最早时间（TE ）： i （2）节点最迟时间（TL i ） （3）工作的最早可能开始时间（ES i，j ）：ES i，j = TE i （4）工作的最早可能完成时间（EF i，j ）：EF i，j = TE i + D i，j （5）工作的最迟完成时间（LF i，j ）：LF i，j = TL j （6）工作的最迟开始时间（LS i，j ）：LS i，j = LF i，j - D i，j = TL j - D i，j （7）工作的总时差（TF i，j ）：它是指在不影响后续工作按照最迟必须开始时间开工的前提下，允许该工作推迟其最早可能开始时间或延长其持续时间的幅度。 TF i，j = TL j - TE i - D i，j = LF i，j - EF i，j = LS i，j - ES i，j （8）工作的自由时差（FF i，j ）：它是指在不影响后续工作按照最早可能开始时间开工的前提下，允许该工作推迟其最早可能开始时间或延长其持续时间的幅度。 FF i，j = TE j - TE i - D i，j = TE j - EF i，j 3、利用时间参数确定关键工作和关键线路 总时差TF i，j = TL j - TE i - D i，j ，其计算差值可以分为以下三种情况： （1）TF i，j = TL j - TE i - D i，j >0，说明i-j这项工作存在机动时间，是非关键工作。 （2）TF i，j = TL j - TE i - D i，j =0，说明i-j这项工作不存在机动时间，是关键工作。 （3）TF i，j = TL j - TE i - D i，j <0，说明i-j这项工作存在负时差，说明了i-j这项 工作持续时间确定的不合理，没有满足总工期的要求，应采取措施缩短本工作的持续时间。 由关键工作组成的线路就是关键线路。关键线路通常用双线或粗线表示。【练习题1】计算图示双代号网络图的各项时间参数。 数据结构课程设计题目 2012-1 1、医务室模拟。（5人） 问题描述：假设只有一位医生，在一段时间内随机地来几位病人；假设病人到达的时间间隔为0~14分钟之间的某个随机值，每个病人所需处理时间为1~9分钟之间的某个随机值。试用队列结构进行模拟。 实现要求：要求输出医生的总等待时间和病人的平均等待时间。 程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有一位病人到达，则这些病人应依次排队，等候就诊。 2、招聘模拟（5人） 问题描述：某集团公司为发展生产向社会公开招聘m个工种的工作人员，每个工种各有不同的编号（0，1，2，…，m-1）和计划招聘人数，参加招聘的人数有n个（编号为0，1，2，。。。，n-1）。每位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩，从高到低的顺序排队录取。公司的录取原则是：从高分到低分依次对每位应聘者按其第一志愿录取；当不能按第一志愿录取时，便将他的成绩扣去5分后，重新排队，并按其志愿考虑录取。 程序为每个工种保留一个录取者的有序队列。录取处理循环直至招聘额满，或已对全部应聘者都做了录用处理。 实现要求：要求程序输出每个工种录用者的信息（编号、成绩），以及落选者的信息（编号、成绩）。 3、组织机构问题（5人） 问题描述：以物资学院为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求： （1）树中每个结点保存部门名称； （2）假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？ （3）软件可以查询某部门下面的具体编制？ 4、最少换车次数问题（5人） 问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0~n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。 实现要求：求得从站0出发乘公交车至站n-1的最少换车次数。 设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边 初中数学［最短路径问题］典型题型及解题技巧 最短路径问题中，关键在丁，我们善丁作定点关丁动点所在直线的对称点，或利用平移和 展开图来处理。这对丁我们解决此类问题有事半功倍的作用。理论依据：“两点之间线段最短”， “垂线段最短”，“点关丁线对称”，“线段的平移” “立体图形展开图”。教材中的例题“饮马问 题”，“造桥选址问题” “立体展开图”。考的较多的还是“饮马问题”。 知识点：“两点之间线段最短问题”，“造桥选址问题”。考的较多的还是“饮马问题”，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。 解题总思路：找点关丁线的对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查。 一、两点在一条直线异侧 例：已知：如图，A , B在直线L的两侧，在L上求一点P,使得PA+PB * 最小。? 解：连接AB,线段AB与直线L的交点P，就是所求。（根据：两点之间线 二、两点在一条直线同侧 例：图所示，要在街道旁修建一个奶站，向居民区A、B提供牛奶，奶站应建在什么地 方，才能使从A、B到它的距离之和最短. 虻叩 解：只有A、C、B在一直线上时，才能使AC+BC最小.作点A关丁直线“街道”的对称点A',然后连接A ' B,交“街道” 丁点C,则点C就是所求的点. 、一点在两相交直线内部 例：已知：如图A是锐角Z MON内部任意一点，在Z MON的两边 OM , ON上各取一点B, C,组成三角形，使三角形周长最小 的两边 解：分别作点A关丁OM , ON的对称点A' , A〃；连接A' , A〃，分别交 OM , ON 丁点B、点C ,则点B、点C即为所求 分析：当AB、BC和AC三条边的长度恰好能够体现在一条直线上时，三角形的周长最小 例：如图，A.B两地在一条河的两岸，现要在河上建一座桥MN ,桥造在何 处才能使从A到B的路径AMNB最短？（假设河的两岸是平行的直线，桥要与河垂直）解：1.将点B沿垂直与河岸的方向平■移一个河宽到E, 2. 连接AE交河对岸与点M, 则点M为建桥的位置，MN为所建的桥。 证明：由平移的性质，得BN// EM 且BN=EM, MN=CD, BD // CE, BD=CE, 所以A.B 两地的距:AM+MN+BN=AM+MN+EM=AE+MN, 若桥的位置建在CD处，连接AC.CD.DB.CE, 则AB两地的距离为: AC+CD+DB=AC+CD+CE=AC+CE+MN, 在/\ACE 中，v AC+CE >AE,二AC+CE+MN >AE+MN,即AC+CD+DB 所以桥的位置建在CD处，AB两地的路程最短。 例：如图，A、B是两个蓄水池，都在河流a的同侧，为了方便灌溉 作物，？要在河边建一个抽水站，将河水送到A、B两地，问该站建在 A\M f —广11 B >AM+MN+BN 网络图的时间参数计算 计算网络计划的时间参数，是编制网络计划的重要步骤，可以说，网络计划如果不计算时间参数，就不是一个完整的网络计划。 (一)计算时间参数的目的 1.确定关键线路 网络图从起点节点顺着箭头方向顺序通过一系列箭杆和节点，最后到达终点节点的一条条道路称为线路。关键线路就是网络图中最重要、需时最长的线路。关键线路上的工序叫做关键工序。关键线路的总长度所需时间叫做总工期，一般用方框“口”标在终点节点的右方。 关键线路的工期决定整个工期的长短，它拖后一天，总工期就相应拖后一天；它提前一天，则总工期有可能提前一天。 关键线路最少必有一条，也可能有多条。一般来讲，安排得好的计划，往往出现有关零件同时完成，组成部件；有关部件同时完成，进行总装配的情况。这样，关键线路就不是一条了。愈好的计划，关键线路愈多，作领导的更要全面加强管理，不然一个环节脱节会影响全局。多条关键线路也可以作为劳动竞赛的依据。 关键线路在网络图上可以用带箭头的粗线、双线或红线表示。 2．确定非关键线路上的机动时间(或称浮动时间、富裕时间) 在一份网络图中，不是关键线路的线路称非关键线路。非关键线路上的工序，由于前后工序及平行工序的作用，使得它被限制在某一段时间之内必须完成，而当该工序的工作持续时间小于被限制的这段时间时，它就存在富裕时间(机动时间)，其大小是一个差值，因此也称为“时差”。时差只能是正值或者为零。 一项工程的网络图画出来之后，如果要想提前完成，则要想方设法压缩关键线路的工期。为达此目的，要调动人力物力等资源，要么从外部调整，要么从内部调整。一般认为，从内部调整是较为经济的。从内部调，就是从非关键线路上调。调多少，则要看非关键线路上富裕时间的“富裕”程度，即时差有多少。3．时间参数的计算是网络计划调整和优化的前提 通过时间参数的计算，可据以采用各种办法不断改进网络计划，使其达到在既定条件下可能达到的最好状态，以取得最佳的效果。优化内容有时间优化、资源优化和工期优化等。 (二)符号与计算公式 1．工作时间t(或称持续时间D) 工作时间是完成某项工作所需时间。 工作时间可以用劳动定额或历史经验统计资料确定，在无定额或历史资料时也可用三时估算法确定。 时间单位可根据需要分别定为年、月、旬、周、天、班、小时、分等等。 t ij表示本工序的持续时间； t hi表示紧前工序的持续时间； t jk表示紧后工序的持续时间。 2．最早可能开工时间(简称早开)ES (l)定义紧前工序全部完成、本工序可能开始的时间。 (2)公式ES ij＝max(ES hi＋t hi) 计算早开是由网络图的第一道工序开始，由箭尾顺着箭头方向依次顺序进行的，直至最后一道工序为止。紧前工序的最早完工时间就是本工序最早可能开工时间，即EF hi＝ES ij。当有两个以上紧前工序时，取其最大值。 3．最早可能完工时间(简称早完)EF (l)定义本工序最早可能完工的时间，也就是最早开始时间与持续时间之和。 (2)公式EF ij＝ES ij＋t ij 4．总工期Lcp或PT 《数据结构课程设计》最短路径问题实验报告 目录 一、概述 0 二、系统分析 0 三、概要设计 (1) 四、详细设计 (5) 4.1建立图的存储结构 (5) 4.2单源最短路径 (6) 4.3任意一对顶点之间的最短路径 (7) 五、运行与测试 (8) 参考文献 (11) 附录 (12) 交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 三、概要设计 可以将该系统大致分为三个部分： ①建立交通网络图的存储结构； ②解决单源最短路径问题； ③实现两个城市顶点之间的最短路径问题。 迪杰斯特拉算法流图： 一、 工程中为什么要使用网络图 工程中常用横道图和网络图表示工程进度计划，横道图又叫甘特（GANTT ）图，由于其不能反映出工作之间的错综复杂的相互关系，不能明确反映关键工作和关键线路，不能 反映工作所具体的机动时间，看不到潜力所在，故存在很大 的局限性，在工程上使用较少。 工程中应用最多的是网络图，与横道图相比网络图有以下几个优点： 1、网络计划能够明确表达各项工作之间的逻辑关系。 2、通过网络计划时间参数的计算，可以找出关键线路和 关键工作。 3、通过时间参数的计算，可以明确各项工作的机动时间。 4、网络计划可以利用电子计算机进行计算优化、调整。 由于网络图有上述优点，因此得到普遍应用。 大家在大学里可能学过相关知识，但由于未经常性使用，就又忘掉了。即便没忘，也可能不会在具体的工程中使用， 通过这次讲座，起到抛砖引玉的作用，学员参加注册监理工 程师或注册建造师考试都可运用此法答题，有心者可进一步 研究学习。 九、网络图的时间参数计算<双代号网络图最为常用，故讲双 代号网络图> 十、先讲几个名词：工艺关系、组织关系、紧前工作、紧后 工作、平行工作、先行工作、后续工作、关键工作、关键线路、线路、总工期。 例： 支模 1 扎筋 1 ①②③ 3 天 2 天 砼1 天 支模 2 3 天 扎筋 2 砼 ④⑤⑥ 1 天 2 天 支模1 扎筋 1 砼1 之间为工艺关系（这是施工程序决定的） 支模1 支模2 扎筋 1 扎筋 2 等是组织关系（这是人为组织形成的，支模可以不分段，可以分若干段等） 相对于某工作而言，紧排在其前的工作为该工作的紧前工作。 相对于某工作而言，紧排在其后的工作为该工作的紧后工作。 相对于某工作而言，与该工作同时进行的工作为该工作的平行工作。 相对于某工作而言，排在其前（包括紧排在其前）的工作为该工 作的先行工作。 相对于某工作而言，排在其后（包括紧排在其后）的工作为该工 作的后续工作。 关键线路上的工作为关键工作。 线路上持续时间最长的线路为关键线路。 线路有若干条，除关键线路外，其余可简称线路。 关键线路的长度，就是总工期。 数据结构课程设计报告 图的最短路径算法的实现 班级：计算机112班 姓名：李志龙 指导教师：郑剑 成绩：_______________ 信息工程学院 2013 年1 月11 日 目录 一、题目描述 -------------------------------------------------------------------- 1 1.1题目内容-------------------------------------------------------------------- 1 2.2题目要求-------------------------------------------------------------------- 1 二、设计概要 -------------------------------------------------------------------- 2 2.1程序的主要功能----------------------------------------------------------- 2 2.2数据结构-------------------------------------------------------------------- 2 2.3算法分析-------------------------------------------------------------------- 2 三、设计图示 -------------------------------------------------------------------- 4 四、详细设计 -------------------------------------------------------------------- 5 五、调试分析 -------------------------------------------------------------------- 8 六、运行结果 -------------------------------------------------------------------- 9 七、心得体会 ------------------------------------------------------------------- 11参考资料 ------------------------------------------------------------------------ 12 《数据结构课程设计》报告 最短路径—拯救007 专业 xxxxxx 学生姓名 xxxx 班级 xxxx 学号 xxxx 指导教师 xxxxx 完成日期 xxxxxx 目录 一、简介 (3) 二、算法说明 (4) 三、测试结果 (7) 参考文献 (14) 一、简介 最短路径是，在一个图中，若从一个顶点到另一个顶点存在着一条路径（这里只讨论无回路的简单路径），则称该条路径长度为为该路径上所有经过的边的数目，它也等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在着多条路径，在每条路径上所经过的边数可能不同，把路径长度最短（经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短距离。这是对无权图而言的，若图是帯权图，则把从一个顶点vi到vj的一条路径上所有经过边的权值之和定义为该路径的带权路径长度。把带权路径长度最短的那条路径称为该有权图的最短路径，其路径长度称为最短距离。 Dijksra算法：如何求解从一个顶点到其余每个顶点的最短路径呢？狄克斯特拉于1959年提出了解决此问题的一种按路径长度的递增次序产生最短路径的算法。基本思想是，从图中给定源点到其他各个顶点之间客观上应个存在一条最短路径，在这组最短路径中，按其长度的递增次序求出到不同顶点的最短路径和路径长度。 图是一种较线性结构和树形结构更为复杂的非线性数据结构，这种复杂性主要来自数据元素之间的复杂关系。在图结构中，任何两个数据元素之间都可能存在关系，一般用顶点表示数据元素，而用顶点之间的连线表示数据元素之间的关系。图的二元组定义为：G=(V,E)。其中V是非空的顶点集合，E是V上的二元关系集合。 题目内容： 看过007系列的电影的人们一定很熟悉Jams Bond这个世界上最著名的特工了。在电影“Live And Let Die”中Jams Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时Jams Bond做出了一个最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反映过来的时候，他有跳到另一支鳄鱼的头上.。。。。。。最后他终于安全地跳到了湖岸上。 假设湖是100*100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆环小岛的圆心在（0，0），直径是15.。一些凶残的鳄鱼分布在湖中不同的位置。现已知的湖中的鳄鱼的位置和Jams Bond可以跳的最大距离，请你告诉Jams Bondyitiao 最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。 青岛理工大学琴岛学院 设计报告 课题名称：求解最优交通路径 学院：计算机工程系 专业班级：计算机科学与技术 学号：####### 学生：** 指导教师：** 青岛理工大学琴岛学院教务处 2011 年 7 月 7日 图1 B.具体功能实现及相应的弗洛伊德算法 首先,建立查询信息对话框，使用户能够录入需要查询的城市代号，并显示路径长度及最短路径沿途经过的城市。并相应地添加如下变量int m_v0;int m_v1;int m_lj;CString m_zd; 具体代码如下： #define MAXV 25 //最大顶点个数 #define INF 32767 //用32767表示∞ //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 char name[10]; //顶点名称 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int vexnum,arcnum; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 1.通过函数CreatUDN()存放城市路径信息，输入顶点之间的路径长度，创建带权图的邻接矩阵。 void CTDialog::CreatUDN() { MGraph *g=(MGraph*)malloc(sizeof(MGraph)); int i,j; for(i=0;i专题训练之最短路径问题(最全面的经典例题)
多项式分治,背包问题,单元最短路径,克鲁斯卡尔,多段图
数据结构课程设计校园最短路径问题
动态规划算法实现多段图的最短路径问题算法设计与分析实验报告
排列组合中的最短路径问题
数据结构课程设计报告Dijkstra算法求最短路径
双代号网络计划时间参数的计算
动态规划算法实现多段图的最短路径问题算法设计与分析实验报告
双代号网络图时间参数的计算_百度文库(精)
双代号网络图时间参数的计算精
数据结构课程设计题目(最终版)-2011
(完整版)初中数学[最短路径问题]典型题型及解题技巧
网络图的时间参数计算
《数据结构课程设计》最短路径问题实验报告
工程网络图时间参数最简单计算方法
图的最短路径算法的实现
课程设计--最短路径：拯救007
数据结构课程设计报告_最短路径C++
- 彻底弄懂最短路径问题
- 排列组合中的最短路径问题
- 最短路径问题专项练习
- 实验九 多段图的最短路径问题的设计与实现
- 最短路径问题-几何题技巧
- 排列组合中的最短路径问题
- (完整版)初中数学[最短路径问题]典型题型及解题技巧
- 多种方法求多段图的最短路径问题 算法设计与分析课程设计
- 实验三-动态规划法求多段图问题
- 多种方法求多段图的最短路径问题算法设计与分析课程设计
- 动态规划算法实现多段图的最短路径问题算法设计与分析实验报告
- 最短路径问题总动员(含答案)
- 实验八 多段图的最短路径问题
- 初中数学《最短路径》问题(12个详解+经典例题)
- 最短路径问题专项练习
- 最短路径问题(经典)精编版
- 八年级最短路径问题归纳小结
- 算法设计与分析多段图最短路径问题
- 专题训练之最短路径问题(最全面的经典例题)
- 实验三动态规划求多段图问题