西安电子科技大学算法上机报告

西安电子科技大学（2018年度）算法分析实 验 报 告实验名称：渗透实验班 级：1603012名：学 号：实验一：渗透问题（Percolation）一、实验题目使用合并-查找（union-find）数据结构，编写程序通过蒙特卡罗模拟（Monte Carlo simulation）来估计渗透阈值的值。给定由随机分布的绝缘材料和金属材料构成的组合系统:金属材料占多大比例才能使组 合系统成为电导体？给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件 下能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透（percolation） 的抽象过程来模拟这种情况。percokitesdoes 响 gog模型：我们使用NXN网格点来模型一个渗透系统。每个格点或是open格点或是blocked 格点。一个full site是一个open格点，它可以通过一连串的邻近（左，右，上，下）open格 点连通到顶行的一个open格点。如果在底行中有一个full site格点，则称系统是渗透的。（对 于绝缘/金属材料的例子，oten格点对应于金属材料，渗透系统有一条从顶行到底行的金属 路径，且full sites格点导电。对于多孔物质示例，open格点对应于空格，水可能流过，从而 渗透系统使水充满open格点，自顶向下流动。）血/open site connected fol? no open site, contiectea ro tap问题：在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率刀 独立地设置为open格点（因此以概率1-p被设置为blocked格点），系统渗透的概率是多少？ 当p = 0时，系统不会渗出；当p=1时，系统渗透。下图显示了 20X20随机网格和100X100 随机网格的格点空置概率p与渗滤概率。当N足够大时，存在阈值p*，使得当p <p*，随机Nx N网格几乎不会渗透，并且当p> p*时，随机Nx N网格几乎总是渗透。尚未得出用于确定渗滤阈值p*的数学解。你的任务 是编写一个计算机程序来估计p*。Percolation数据类型:模型化一个Percolation系统，创建含有以下API的数据类型Percolation。public class Percolation public Percolation(int N)public void open(int i, int j)public boolean isOpen(int i, int j)public boolean isFull(int i, int j) public boolean percolates()public static void main(String args)/ create N-by-N grid, with all sites blocked/ open site (row i, column j) if it is not already/ is site (row i, column j) open?/ is site (row i, column j) full?/ does the system percolate?/ test client, optional约定行/列顶下标在1和N之间，其中(1, 1)为左上格点位置:如果open(), isOpen。, or isFull。 不在这个规定的范围，则抛出IndexOutOfBoundsException例夕卜。如果N < 0，构造函数应该 抛出IllegalArgumentException例外。构造函数应该与N2成正比。所有方法应该为常量时间 加上常量次调用合并-查找方法union。，find。, connected。, and count。蒙特卡洛模拟(Monte Carlo simulation).要估计渗透阈值，考虑以下计算实验:初始化所有格点为blocked。重复以下操作直到系统渗出：o 在所有blocked的格点之间随机均匀选择一个格点(row i, columnj)。o 设置这个格点(row i, columnj)为open格点。 open格点的比例提供了系统渗透时渗透阈值的一个估计。例如，如果在20X20的网格中，根据以下快照的open格点数，那么对渗滤阈值的估计是 204/400 = 0.51，因为当第204个格点被open时系统渗透。50 open sites100 open sites150 open sites204 open sites通过重复该计算实验T次并对结果求平均值，我们获得了更准确的渗滤阈值估计。令xt是 第t次计算实验中open格点所占比例。样本均值日提供渗滤阈值的一个估计值；样本标准 差b测量阈值的灵敏性。日兀决 2兀_ ,°2 =(兀1 U)23 2 U)23_)2T 'T1假设T足够大(例如至少30),以下为渗滤阈值提供95%置信区间:1.96b7=> +public class PercolationStats public PercolationStats(int N, int T) on an N-by-N gridpublic double mean。public double stddev。public double confidenceLo。public double confidenceHi。public static void main(String args) 我们创建数据类型PercolationStats来执行一系列计算实验，包含以下API。/ perform Tindependent computational experiments/ sample mean of percolation threshold/ sample standard deviation of percolation threshold / returns lower bound of the 95% confidence interval / returns upper bound of the 95% confidence interval / test client, described below在 N < 0 或 T < 0 时，构造函数应该抛出 java.lang.IllegalArgumentException 例外。此外，还包括一个main()方法，它取两个命令行参数N和T,在NXN网格上进行T次独 立的计算实验(上面讨论)，并打印出均值3标准差和95%渗透阈值的置信区间。使 用标准库中的标准随机数生成随机数；使用标准统计库来计算样本均值和标准差。Example values after creating PercolationStats(200, 100)mean。= 0.5929934999999997stddev。= 0.00876990421552567confidenceLowQ= 0.5912745987737567confidenceHigh。= 0.5947124012262428Example values after creating PercolationStats(200, 100)mean()=0.592877stddev()=0.009990523717073799confidenceLow()=0.5909188573514536confidenceHigh()=0.5948351426485464Example values after creating PercolationStats(2, 100000)mean()=0.6669475stddev()=0.11775205263262094confidenceLow()=0.666217665216461confidenceHigh()=0.6676773347835391运行时间和内存占用分析。使用 quick-find 算法(QuickFindUF.java from algs4.jar)实现 Percolation 数据类型。进行实 验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机上的总时间，它是 输入N和T的函数表达式。使用 weighted quick-union 算法(WeightedQuickUnionUF.java from algs4.jar)实现 Percolation 数据类型。进行实验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机 上的总时间，它是输入N和T的函数表达式。二、算法设计程序要求实现对一个NxN矩阵的连通性判断问题，则可以使用quick-find算法和加权 quick-union算法来实现，因为算法中的数组是一维的，所以首要解决的问题就是将NxN矩 阵中的点经过变换转换到一维数组中对应的位置来完成之后的算法求解。将它们在连通分量数组中的编号依次设置为0NxN-1。为了之后检验连通性的问题， 有一个非常巧妙的方法。抽象出在矩阵的顶部有一个单独的注水口，它和第一行的所有点都 是连通的，在矩阵的底部有一个出水口，它和最后一行的所有点是连通的，并分别将注水口 和出水口在连通分量数组中的编号设为NxN和NxN+1。按照题目的要求每次随机打开矩阵 中的一个点，然后判断与它邻近的点(上下左右)是否已经被打开，若已经打开就将它们连 接起来。那么每次打开一个新的结点之后检验连通性，只需要检验注水口和出水口是否连通 即可。具体设计：设计 Percolation 类，分别使用 quick-find 和 weight quick-union 算法进行合并。Percolation 类中设计open方法打开一个点，并将该点与其它相邻的点合并。public class Percolation private int matrixLength;/网格大小private boolean matrix;/记录方格是否打开数组private QuickFindUF qu;/合并查找类变量/或者：private WeightedQuickUnionUF wqu;private int virtualTop;/注水口private int virtualbottom;/出水口public Percolation(int N)if (N <= 0) throw new IllegalArgumentException("length must be positive");matrixLength = N;virtualTop = matrixLength * matrixLength;virtualbottom = matrixLength * matrixLength + 1;matrix = new booleanN * N;qu = new QuickFindUF(N * N + 2); 检查边界private void checkValidIndex(int row,int col)(if(row <= 0 | row >matrixLength)throwiew IndexOutOfBoundsException("row index out of bounds"); if(col <= 0 | col >matrixLength)throwiew IndexOutOfBoundsException("col index out of bounds"); /计算点(row i, c(的一维坐标private int rowCol_to_real(int row,int col)return (row - 1) * matrixLength + col - 1; /打开一个点public void open(int row,int col)checkValidIndex(row, col);int real = rowCol_to_real(row, col);检查边界轴换成一维坐标if (matrixreal) return;matrixreal = true;如果/已经是打开的，就直接返回if (row = 1) 如果是第一行的情况，那么让他连接top的虚拟点qu.union(real, virtualTop);if (row = matrixLength) 如果是最后一行的情况，那么让他连接bottom的虚拟点qu.union(real, virtualbottom);int neighbor;/记录相邻点的坐标/判断周围的四个点是否是打开的，如果是的话就连接if (row > 1) / upneighbor = rowCol_to_real(row - 1, col); if (matrixneighbor) qu.union(real, neighbor); if (row < matrixLength) / downneighbor = rowCol_to_real(row + 1, col); if (matrixneighbor) qu.union(real, neighbor);if (col > 1) / leftneighbor = rowCol_to_real(row, col - 1); if (matrixneighbor) qu.union(real, neighbor); if (col < matrixLength) / rightneighbor = rowCol_to_real(row, col + 1); if (matrixneighbor) qu.union(real, neighbor); public boolean isOpen(int row,int col)判断这个点是不是已打开的checkValidIndex(row, col); return matrixrowCol_to_real(row, col);public boolean isPercolated()判断网格是否渗透return qu.isConnect(virtualTop, virtualbottom);QuickFindUF算法核心：每个点所在连通分量记录在以该点为下标的数组中，find方法 的复杂度低，但合并时要遍历数组中的所有点，将其中一个连通分量中所有点的连通分量记 录改为另一个连通分量，union方法的复杂度高。public int find(int p) /由标号找该点所在连通分量 return idp;public void union(int p,int q) /合并两个连通分量int pID=find(p);int qID=find(q);if(pID=qID)return;for(int i=0;i<id.length;i+)/遍历所有点，将与p点在同一连通分量的点合并到q所在的连通分量if(idi=pID) idi=qID;count-;WeightedQuickUnionUF算法核心：以每个点为下标的数组中记录该点的父亲节点，由 父亲节点找到根节点，根节点为该连通分量的标记;增加size数组记录每个连通分量的大小， 在union时比较两个连通分量的size的大小，将小连通分量连接到大连通分量上，以此来减 小树的高度减少查找根节点的时间。public int find(int p) /复杂度为两倍的树的高度h即2h while(p!=idp)p=idp;return p;public void union(int p,int q)/不计算find的情况下union的算法复杂度为 1 int i=find(p);int j=find(q);if(i=j)return;if(szi<szj)idi=j;szj+=szi; else(idj=i；szi+=szj;count-;三、实验结果及分析1. QuickFindUF 合并查找：P_ea se enter N and T : 100 50The mean of p已rcalationStats is 0.591978The 5tddev of percolationStats is 0,916985627658075362The condidence intervals of percolationStats is 0-587269S2422B104 ? 0.596686175779896 The time of the p rag ran is 1384 nosPlease eniter N and T ;1W 1即The m-ean of perco 1 atiDriiStats is B.591SS4.The s+ddev of percolationStats is G.1682Bl07124-82487The candidence intervals of percolationStats is Q.5S85966710035344 , 0.59519132S9964657The time of the program is 2736n*5Please enter IN and T z 100 2B0frhe mean of per col at ion Stat 5 is 9 B 5905950000000091The stddev of percolatinStata is 0.0164335Bl105154735The condidence intervals of percolationStats is B.S8831742135ES278 ? 6.S92S72S781411723The tiime of the program is 5395msPlease enter IN and T :200 S6The rnean of per-co 1 ation51at5 is &, 5927275000000001The stddev of percolationStats 1& 0.008923766206951327The corididence intervals of percolationStat5 is 0.5902539582053259 , 6,5952010417946743The tiiwe of the ppogrm is 2055Smi&Please enter N and T : 200 l&BThe of percolationStats is 0.5922397500000001The stddev of percolationBtat 5 is 0 B 00S43B&690643S7131The condidence intervals of percalationStats is 0.5903898884633801 . 0,59408961153662The tim吧 of the progrann is 41010nnsPlease enter N and T : 200 206The mean of perco1atiomStat5 is 0,5941488749999998The stddletf of percolationStata is 0u009618371991047439The condidence intervals of percolatioriStats is 0,5928158366524663 T 土5954819133475333 The time of the program is 81257mis通过以上数据分析：N 一定时，运行时间与T成正比；T 一定时，运行时间与Nm成正比；所以用quick-find 方法解决渗透问题的时间成长量级为：NmT2. WeightedQuickUnionUF算法：Please enter N anid T :106 56The mean of percolatioriStats is 0.5974-3GB0Q000BlThe stddev of percolationStots is 0,016397926706647526The condideince internals of percolatiainStdts. is 0.59291567333994550.6019563266600546The time of the program is 124msPlease enter IM and T :z100 10&The mean of per colet i o nStot s is 0.5926319999999999The stddev of percolationStat& is 0.01647160323500154The condidence intervals of percolationStats in &-5894035657659397015958604342340602Ths time of the program is 20SraisPlease enter- IN and T :100 200The rwmn of percolatiomStats i& 0.5931034999999997The stddev of p&rcolati&nStats is 0.0153&2181513SI79&The comdidence intervals of percolationStats is 0.59697441026648230.595232589733517The time of the program isPlease enter N and T :z200 50The nt£叩 of percolationStats is 0.5930835000000002The stddew of percolatiDFiStats is 6.009299031124097757The condlidence intervals of per cola t ionSt at 5 is 0.5 9050594077 2059.5956610599227954The time of the prog rami is 344 msPlease enter N and T :200 100The 此洞 n of pe r col a t ion St t £ is 0.59 36149999 99999 9The stddev of percolationStats is 0.9fi98524G6483065574The corididence intervals of pereolationStats is 0u5916S39126493191 . 0.5955460873506807The time of the program £& 624msPleaise enter N &rd T :200 200The mean of per col at ion Stats is 0.59138362 50000004The stddev of pereolationStats is 0-010211902356223555The condlidence intervals of percolationStats is 0.5904683275406398 , 0. 593298922-4S93609The tinne of the prog pan® i& 1140msN 一定时，运行时间与T成正比;T 一定时，运行时间与lgN2成正比;所以用quick-find方法解决渗透问题的时间成长量级为：lgN2T两种算法均得出渗透问题的阈值约为0.59。(二)几种排序算法的实验性能比较一、实验题目实现插入排序(Insertion Sort，IS)，自顶向下归并排序(Top-down Mergesort，TDM)， 自底向上归并排序(Bottom-up Mergesort，BUM)，随机快速排序(Random Quicksort，RQ)， Dijkstra 3-路划分快速排序(Quicksort with Dijkstra 3-way Partition， QD3P)。在你的计算机上 针对不同输入规模数据进行实验，对比上述排序算法的时间及空间占用性能。要求对于每次 输入运行10次，记录每次时间，取平均值。二、算法设计1. 每种排序算法均实现下列模板中的各个方法:public class Example public static void sort(Comparable a) private static boolean less(Comparable v,Comparable w) return pareTo(w)<0;private static void exch(Comparable a,int i,int j) Comparable t=ai;ai=aj;aj=t;private static void show(Comparable a) for(int i=0;i<a.length;i+)System.out.println(ai+"");System.out.println();public static boolean isSorted(Comparable a) for(int i=0;i<a.length;i+)if(less(ai,ai-1) return false;return true;参与排序的数据均实现Comparable接口。2. 插入排序算法:public static void sort(Comparable a) int N=a.length;for(int i=1;i<N;i+) for(int j=i;j>0&&Less(aj,aj-1);j-)exch(a,j,j-1);从1=0开始依次取i,将21插入到已经部分有序的a0ai-1的合适的位置。3. 自顶向下排序算法：private static void sort(Comparable a,int lo,int hi) if(hi<=lo) return;int mid=lo+(hi-lo)/2;sort(a,lo,mid);sort(a,mid+1,hi);/erge(a,lo,mid,hi);在sort方法中递归地调用sort方法将大数组二分为两个小数组直至两个小数组大小为 1，再在递归返回时调用merge方法将已经有序的两个小数组合并成一个较大的有序数组。public static void merge(Comparable a,int lo,int mid,int hi) int i=lo,j=mid+1;for(int k=lo;k<=hi;k+)auxk=ak;for(int k=lo;k<=hi;k+)if(i>mid)akj=xj+;else if(j>hi)ak时xi+;else if(Less(auxj,auxi) ak=auxj+;elseakuxi+;merg e方法不断从两个数组中取出数据进行比较，较小的数据插入到辅助数组中并取 该较小数据所在数组的下一个数据继续比较，当有某个数组中的数据取完时则将另一个数组 中剩下的数据全部放到辅助数组中，完成两个有序数组合为一个有序数组的排序。4. 自底向上排序算法：public static void sort(Comparable a) int N=a.length;aux=new ComparableN;for(int sz=1;sz<N;sz=sz*2)for(int lo=0;lo<N-sz;lo+=sz*2)werge(a,lo,lo+sz-1,Math.win(lo+sz*2-1, N-1);从数组大小size为1开始将相邻的大小为size的两个数组用merge方法归并排序， 直至辅助数组中的数排完，辅助数组成为每2*size部分有序的数组；增大数组大小size 为上一次归并的两个数组大小size的两倍，继续用merge方法将相邻的大小为size的数 组排序；增大size重复上一步直至将整个辅助数组排成有序的。merge方法同上。5. 随机快速排序算法：private static void sort(Comparable a,int lo,int hi) if(hi<=lo) return;int j=partition(a,lo,hi); sort(a,lo,j-1);sort(a,j+1,hi);private static int partition(Comparable a,int lo,int hi) int i=lo,j=hi+1;Comparable v=alo; while(true) while(Less(a+i,v) if(i=hi)break; while(less(v,a-j) if(j=lo)break; if(i>=j)break; exch(a,i,j);exch(a,lo,j); return j;Partition方法以传入的数组的第一个数据为切分数据，比切分数据小的数据全部移 动到切分数据左边，比切分数据大的全部移动到切分数据右边，将切分数据移动到正确的位 置并返回该位置j。sort方法调用Partition方法得到切分数据aj，再递归地对aj左右两边的数组调 用sort方法直至传入sort方法的数组大小为1 (大小为1的数组恒有序)，整个数组排序完 成。三、实验结果及分析< termi rated > SortCompare Java Application GiXJAVAf&I .3.0 1 91binjavaw.exe (201 9 弃1000IS已排序IS寸丸彳亍日寸间二13.053sTDM已排序TDM执彳亍日寸间：0.037&BLJM已排序BUM执彳亍时间：0.062sRQ已排序RQ执彳亍时间二0.042sQD3P已排序QD3P执彳亍时间：0.054s<terminated> S-o-rtCompsrea Java Application G:JAVAjrel .S.0 191 binjavaw.(2019 5600爵已排序issj 亍时间：12.seastd尚已排序TDM执行时间：0.034sB州已排序BUM执彳亍时间：O.031SRQ已排序RQ执彳亍时间：0.046sQD3P已排序QD3P寸丸彳亍日寸间，0.041s<teirminated> SortCompare Java Application G:JAVAjr&l91birijavaw.exe (201 910000IS已排序IS执彳亍时间：13.313sTDM已排序TDMBJ亍时间：0.042&BUM已排序BUM执彳亍时间：0.04sRQ已排序RQ执彳亍日寸间：0.052sQD3P已排序QD3P执行时间；0.053s由以上实验结果可以看出插入排序花的时间最多，其他四种排序算法时间开销相差不大， 比插入排序快很多，随机快排排序最快。(三)地图路由(Map Routing )一、实验题目实现经典的Dijkstra最短路径算法，并对其进行优化。这种算法广泛应用于地理信息 系统(GIS)，包括MapQuest和基于GPS的汽车导航系统。地图：本次实验对象是图maps或graphs，其中顶点为平面上的点，这些点由权值为欧氏 距离的边相连成图。可将顶点视为城市，将边视为相连的道路。为了在文件中表示地图， 我们列出了顶点数和边数，然后列出顶点(索引后跟其x和7坐标)，然后列出边(顶点对)， 最后列出源点和汇点。例如，如下左图信息表示右图：6 90 1000 £40。1 2000 3D002 24QQ 25003 400004 45QQ 58005 6000 15000 10 31 21 42 42 34 5 0 5Dijkstr算法：Dijkstra算法是最短路径问题的经典解决方案。它在教科书第21章中 有描述。基本思路不难理解。对于图中的每个顶点，我们维护从源点到该顶点的最短已知 的路径长度，并且将这些长度保持在优先队列(priority queue,眨)中。初始时，我们把所有 的顶点放在这个队列中，并设置高优先级，然后将源点的优先级设为0.0。算法通过从PQ 中取出最低优先级的顶点，然后检查可从该顶点经由一条边可达的所有顶点，以查看这条边 是否提供了从源点到那个顶点较之之前已知的最短路径的更短路径。如果是这样，它会降 低优先级来反映这种新的信息。这里给出了 Dijkstra算法计算从0到5的最短路径0-1-2-5的详细过程。process 0 (0.0)lower 3 to 3841.9lower 1 to 1897.4process 1 (1897.4)lower 4 to 3776.2lower 2 to 2537.7process 2 (2537.7)lower 5 to 6274.0process 4 (3776.2)process 3 (3841.9)process 5 (6274.0)该方法计算最短路径的长度。为了记录路径，我们还保持每个顶点的源点到该顶点最 短路径上的前驱。文件 Euclidean Graph.java，Point.java，IndexPQ.java，IntIterator.java 和 Dijkstra.java提供了针对map的Dijkstra算法的基本框架实现，你应该以此作为起点。客户 端程序ShortestPath.java求解一个单源点最短路径问题，并使用图形绘制了结果。客户端程 序Paths.java求解了许多最短路径问题，并将最短路径打印到标准输出。客户端程序Distances.java求解了许多最短路径问题，仅将距离打印到标准输出。目标：优化Dijkstra算法，使其可以处理给定图的数千条最短路径查询。一旦你读取 图（并可选地预处理），你的程序应该在亚线性时间内解决最短路径问题。一种方法是预 先计算出所有顶点对的最短路径；然而，你无法承受存储所有这些信息所需的二次空间。你 的目标是减少每次最短路径计算所涉及的工作量，而不会占用过多的空间。建议你选择下 面的一些潜在想法来实现，或者你可以开发和实现自己的想法。想法1： Dijkstra算法的朴素实现检查图中的所有K个顶点。减少检查的顶点数量的一 种策略是一旦发现目的地的最短路径就停止搜索。通过这种方法，可以使每个最短路径查 询的运行时间与E log，成比例，其中E和，是Dijkstra算法检查的边和顶点数。然而， 这需要一些小心，因为只是重新初始化所有距离为8就需要与K成正比的时间。由于你在 不断执行查询，因而只需重新初始化在先前查询中改变的那些值来大大加速查询。想法2:你可以利用问题的欧式几何来进一步减少搜索时间，这在算法书的第21.5节描 述过。对于一般图，Dijkstra通过将dw更新为dv +从v到w的距离来松弛边v-w。对于 地图，则将dw更新为dv +从v到w的距离+从w到d的欧式距离 从v到d的欧式 距离。这种方法称之为A*算法。这种启发式方法会有性能上的影响，但不会影响正确性。想法3：使用更快的优先队列。在提供的优先队列中有一些优化空间。你也可以考虑 使用Sedgewick程序20.10中的多路堆。测试:美国大陆文件usa.txt包含87,575个交叉口和121,961条道路。图形非常稀疏-平 均的度为2.8。你的主要目标应该是快速回答这个网络上的顶点对的最短路径查询。你的 算法可能会有不同执行时间，这取决于两个顶点是否在附近或相距较远。我们提供测试这 两种情况的输入文件。你可以假设所有的x和v坐标都是0到10,000之间的整数。二、算法设计因为要实现地图路由，地图是一个加权无向图，图中所用的边为加权无向边，实现一个 加权无向图的数据结构,初始化地图后，利用Dijkstra算法来找出最短路径。经典的Dijkstra算法是初始化时就把所有节点的最短路径找出来了，程序优化则可以重 用代码（想法1），多次查询两节点间最短路径用同一对象，并且每次查询当找到目标节点 后便停止，不再遍历其他的节点。然后将上一次查询改变的成员变量部分还原，以供下一次 的查询使用，这样便大大的优化了传统的Dijkstra算法。优化方法采用的想法1减少检查的 顶点数量,一旦发现目的地的最短路径就停止搜索。通过这种方法使每个最短路径查询的运行时间与Elog V成比例，在不断执行查询，每次 重新初始化在先前查询中改变的那些值来大大加速查询。public class DijkstraUndirectedSP (private double distTo;private Edge edgeTo;private IndexMinPQ<Double> pq;private EdgeWeightedGraph mGraph;private int from;public DijkstraUndirectedSP(EdgeWeightedGraph G) (设置算法的起点public void setFrom(int from) (/更新到节点的最短路径private void relax(Edge e, int v) (/获取到某一节点的最短距离public double distTo(intv) ()/在这里才执行相关的路径初始化public boolean hasPathTo(intv) ()还原上一次查询被修改的部分public void itijkstra() ()/遍历到一个节点所经过的边public Iterable<Edge> pathTo(int v) ()想法1实现：调用setFrom函数设置算法的起点，每次设置新的起点后，调用initDijkstra方法还原上次 查询操作被修改的数据。/设置算法的起点public void setFrom(int from) (/开始新的一-次查询后把上一次修改过的部分还原初始化initDijkstra();this.from = from;distTofrom = 0.0;pq. insert(from, distTofrom);还原上一次查询被修改的部分public void initDijkstra()(for (int i = 0; i < mGraph.v(); i+) (if (pq. contains(i) (pq.delete(i);if (edgeToil=nul1) (edgeToi=null;if (!Double. isInfinite(distT o(i) (distToi=Double. POSITIVE. INFINITY;当执行查询源点到目的地的最短路径时调用hasPathTo方法来查询，不断的从优先队列 pq中找出当前最短路径最小的节点,然后对此节点的邻节点进行relax松弛。如果从优先队列中得到的最小权值点就是目标节点的话即为找到两节点的最短路劲退 出函数循环，执行相关的路径初始化public boolean hasPathTo(int v) (while (!pq.isEmpty() (int X= pq.delMin();/找到目标节点就直接退出循环，并初始化已经被修改的值if (x=v) (return true;for (Edge e : mGraph. adj(x)relax(e, x);return distTov < Double. POSITIVE INFINITY;在主函数中从文本文件中读取相应的数据初始化所有顶点，无向边，构造出加权无向图。:三、实验结果请输入你要查询的路线的两个端点：1 253怪过的节巨为：1-4 1.000004-18 13*6014718-34 25.4951034-37 1.4142137-46 10*2956346-50 2.2360750-57 4*0000057-78 8*0000078-85 2.0000085-151 23.19483151 157 4.47214161-157 3.60555161- 162 0.00000162- 166 1.000Q0166-174 5.09902180-174 2.82843180-189 4.24264189-210 12*00000210-233 17.08801233-253 8.60233从顶点1到顶点253的最短路径长度为：150.17541408064517请输入你要查询的路城的两个端点：1 55经过的节点为：1-4 1.000004-18 13.6014728-18 21,9317155-28 19.79899从顶点1到顶点55的最短路径长度为：56,33217258142008上机心得体会这学期算法上机三道大题各对应了几个章节的内容,通过这次的上机作业对面向对象编 程思想有了更加深入的了解，熟悉了连通性问题中quick-find和加权quick-union算法数据结 构。对各种排序算法的性能,适用情况有了进一步的认识。熟悉了基于加权无向图的Dijkstra 算法,优先级队列的使用，并且自己思考对传统的Dijkstra算法进行了优化，无论是时间上还 是空间上性能都有了很大的提升。这三次试验大大加深了我对算法课上学习内容的理解，熟 悉了基本的算法与数据结构，同时综合编程能力有了很大的提升，最后感谢老师每一次上机 的耐心指导。