实验11：图的最短路径实验报告(1)

最短路径问题求解实验报告学院：计算机科学与技术学院班级：***学号：***姓名：***一、实验目的1）以最短路径问题为例，掌握动态规划的基本设计策略；2）掌握dijkstra贪心法求解最短路径问题并实现；3）掌握动态规划方法Floyd算法求解最短路径问题并实现；4）分析实验结果。

二、问题基本思想描述1、实验描述及目标（1）以下图作为输入，利用dijkstra贪心法获取由结点1到其余结点最短路径长度，输出保存到外部文件dijkstra－output1.txt（2）然后改写你的程序，求得所有各点之间的最短距离; 输出保存到文件dijkstra－output2.txt.（3）以上图作为输入，利用Floyd算法求得所有各点直接的最短距离; 输出保存到文件floyd－output1.txt.2、Dijkstra算法（单源最短路径）Dijkstra算法主要解决单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。

在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。

（1）最短路径的最优子结构性质该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。

下面证明该性质的正确性。

假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。

而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。

则与P(i,j)是从i到j的最短路径相矛盾。

因此该性质得证。

（2）Dijkstra算法由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。

数据结构课程设计报告图的最短路径算法的实现班级：计算机112班姓名：李志龙指导教师：郑剑成绩：_______________信息工程学院2013 年1 月11 日目录一、题目描述 -------------------------------------------------------------------- 11.1题目内容-------------------------------------------------------------------- 12.2题目要求-------------------------------------------------------------------- 1二、设计概要 -------------------------------------------------------------------- 22.1程序的主要功能----------------------------------------------------------- 2 2.2数据结构-------------------------------------------------------------------- 22.3算法分析-------------------------------------------------------------------- 2三、设计图示 -------------------------------------------------------------------- 4四、详细设计 -------------------------------------------------------------------- 5五、调试分析 -------------------------------------------------------------------- 8六、运行结果 -------------------------------------------------------------------- 9七、心得体会 ------------------------------------------------------------------- 11参考资料 ------------------------------------------------------------------------ 12一、题目描述1.1题目内容设计校园平面图，所含景点不少于8个。

实验四：空间分析实验—最短路径一、背景在现实中，最短路径的求取问题是可以拓展为许多方面的最高效率问题，最短路径不仅指一般意义上的距离最短，还可以是时间最短、费用最少、线路利用率最高等标准。

二、目的学会用ArcGIS 9进行各种类型的最短路径分析，理解网络分析原理。

三、数据GeoDatabase地理数据库：City.mdb。

数据库中包含一个数据集：City，其中含有城市交通网net、商业中心及家庭住址place、网络节点city_Net_Junctions等要素。

四、要求根据不同的要求，获得到达指定目的地的最佳路径，并给出路径的长度；找出距景点最近的某设施的路径。

在网络中指定一个商业中心，分别求出在不同距离、时间的限制下从家到商业中心的最佳路径。

给定访问顺序，按要求找出从家出发，逐个经过访问点，最终到达目的地的最佳路径。

研究阻强的设置对最佳路径选择的影响。

五、操作步骤1．启动ArcMap。

创建新地图文档，点击菜单File—>Add Data，打开D：\GIS_Data\Ex2\city.mdb文件，加载数据。

2．对点状要素place符号化：以HOME字段，1值为家，0值为商业中心。

图1图2图33．加入网络分析工具条图44．无权重最佳路径的生成（1）在网络分析工具条上，选择旗标工具，将旗标放在“家”和想要去的“商业中心”点上。

图5（2）选择Analysis Options命令，打开Analysis Options对话框，确认Weights和Weight Filter标签项全部是None，这种情况下进行的最短路径分析是完全按照这个网络自身的长短来确定。

图6（3）在Track Task文本框中选择Find path。

单击solve按钮。

显示出最短路径，这条路径的总成本显示在状态栏中。

注：这里的“18”指的是从起点到目的地总共经过了17个网络节点，如果把两个网络节点当作一个街区的话，也就是指中间经过了17个街区。

离散数学迷宫问题问题描述：一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。

迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。

问题是让你帮助老鼠找出从入口到出口的一条最短路径。

00001000110010100001000000001010101000000011101110001000基本要求：为老鼠找出一条从入口到出口的最短路径。

实现提示：1、迷宫用数组表示，1代表是墙走不通，0表示可以通行。

边界可以扩充为墙，即M×N 迷宫用(M+2)×(N+2)数组表示。

2、向4个方向前进时的位移量可以用以下数组表示，处理是方便。

int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };3、采用图的广度优先搜索算法。

#include<stdio.h>#define m 7#define n 8void path(){int maze[m+2][n+2] ;int move[4][2]={ {0,-1},{-1,0},{0,1},{1,0} };int s[54][3];int top=0;int i,j,k,f=0;int g,h,p;for(i=0;i<m+2;++i)for(j=0;j<n+2;++j)scanf("%d",&maze[i][j]);maze[1][1]=2;s[top][0]=1;s[top][1]=1;s[top][2]=0;++top;while(top!=0&&f==0){--top;i=s[top][0];j=s[top][1];k=s[top][2];while(k<4){g=i+move[k][0];h=j+move[k][1];if(g==m&&h==n&&maze[g][h]==0) {for(p=0;p<top;++p)printf("%3d,%d\n",s[p][0],s[p][1]);printf("%3d,%d\n",i,j);printf("%3d,%d\n",m,n);f=1;}//ifif(maze[g][h]==0){maze[g][h]=2;s[top][0]=i;s[top][1]=j;s[top][2]=k;++top;i=g;j=h;k=0;}//ifk=k+1;}//while}//whileif(f==0)printf("no path\n"); }//pathvoid main(){path();}。

华中科技大学计算机科学与技术学院《计算机算法基础》课程设计(最短路径)实验报告专业：班级：学号：姓名：指导教师：成绩：算法基础实验报告------最短路径一．实验目的运用所学算法分别使用动态规划和贪心算法解决有向图的最短路径问题，要求显示最短路径以及相应的路径长度。

二．动态规划1.算法思想最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。

简而言之，一个最优化策略的子策略总是最优的。

一个问题满足最优化原理又称其具有最优子结构性质。

在本次试验中具体考察i到j的最短路径：首先确定哪个节点是该路径上具有最大编号的中间结点k，计算由i、j分别到k的最短路径，这2条路径都不可能有比k-1还大的中间节点。

求解递推；用Ak（i，j）表示从i到j且不经过比k 还大的结点的最短路径长度，由于G中不存在比n还大的结点，因此A（i，j）=An（i，j），即由i到j的最短路径上不通过比n标号还大的结点。

这条路径可能通过结点n也可能不通过节点n，如果通过结点n则A n（i，j）=A n-1（i，n）+A n-1（n，j），如果不通过结点n，则A n（i，j）=A n-1（i，j）。

组合起来得到A n（i，j）=min{A n-1（i，j），A n-1（i，n）+A n-1（n，j）}同理A k（i，j）=min{A k-1（i，j），A k-1（i，k）+A k-1（k，j）}，k》1.简单的描述最短路径算法如下：I从某一点k开始，根据cost[n][n]（比较A(i,j)与A(i,k)+A(k,j)的大小）修改从i到j的最短路径值，若A(i,k)+A(k,j)<A(i,j)，A(i, j)= A(i,k)+A(k,j).II. 重复1直到所有点均考虑完。

2.程序流程图3.源代码见最后的附录4.运行结果实验的有向图如下1 2 3 4 51 02 2 00 002 1 0 00 4 003 2 00 0 2 84 00 3 00 0 25 00 00 00 1 0首先将有向图的矩阵输入如下程序输出的最短路径列表如下三．贪心算法1.算法思想题目要求为单源点最短路径问题，即已知n结点有向图G=（V，E）和边的权函数c（e），求G中某个结点到其他结点的最短路径（假设所有权均为正）。

动态规划算法实现多段图的最短路径问题算法设计与分析实验报告算法设计与分析实验报告实验名称 动态规划算法实现多段图的最短路径问题 评分 实验日期 年 月 日 指导教师 姓名 专业班级 学号一.实验要求1. 理解最优子结构的问题。

有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。

这类问题的解决是多阶段的决策过程。

在50年代，贝尔曼（Richard Bellman ）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。

对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。

最优子结构性质：原问题的最优解包含了其子问题的最优解。

子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。

问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。

2.理解分段决策Bellman 方程。

每一点最优都是上一点最优加上这段长度。

即当前最优只与上一步有关。

U s 初始值，u j 第j 段的最优值。

⎪⎩⎪⎨⎧+==≠}.{min ,0ijiji js w u u u3.一般方法1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优值（写出动态规划方程）；3）以自底向上的方式计算出最优值；4）根据计算最优值时得到的信息，构造一个最优解。

步骤1-3是动态规划算法的基本步骤。

在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

二.实验内容1.编程实现多段图的最短路径问题的动态规划算法。

2.图的数据结构采用邻接表。

3.要求用文件装入5个多段图数据，编写从文件到邻接表的函数。

4.验证算法的时间复杂性。

图的最短路径问题带权图的最短路径问题1、带权图的最短路径问题带权图的最短路径问题即求两个顶点间长度最短的路径。

其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。

路径长度的的具体含义取决于边上权值所代表的意义。

【例】交通网络中常常提出的如下问题就是带权图中求最短路径的问题。

（1）两地之间是否有路相通?（2）在有多条通路的情况下，哪一条最短?其中:交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。

2、交通网络的表示由于交通网络存在有向性，所以一般以有向网络表示交通网络。

【例】设A城到B城有一条公路，A城的海拔高于B城。

若考虑到上坡和下坡的车速不同，则边和边上表示行驶时间的权值也不同。

即和应该是两条不同的边。

3、源点和终点习惯上称路径的开始顶点为源点(Source)，路径的最后一个顶点为终点(Destination)。

为了讨论方便，设顶点集V={0，1，…，n-1}，并假定所有边上的权值均是表示长度的非负实数。

单源最短路径问题(Single-Source Shortest-PathsProblem)单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V 中其余各顶点的最短路径。

1、边上权值相等的有向网的单源最短路径用求指定源点的BFS生成树的算法可解决2、迪杰斯特拉(Dijkstra)算法求单源最短路径由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。

（1）按路径长度递增序产生各顶点最短路径若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。

【例】在有向网G8中，假定以顶点0为源点，则它则其余各顶点的最短路径按路径递增序排列如右表所示（2）算法基本思想设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。