算法实验三最短路径.docx

算法分析与设计实验报告(三) 姓名:XXX 班级:XXXXX 学号:XXXXXXX 一、题目最短路径问题求解二、基本思想描述 1) Dijkstra 算法思想为: 设 G=(V,E) 是一个带权有向图,把图中顶点集合 V分成两组,第一组为已求出最短路径的顶点集合(用 S 表示,初始时 S 中只有一个源点,以后每求得一条最短路径,就将加入到集合 S中,直到全部顶点都加入到 S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S 中。在加入的过程中,总保持从源点 v到S 中各顶点的最短路径长度不大于从源点 v到U 中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度, U中的顶点的距离,是从 v到此顶点只包括 S中的顶点为中间顶点的当前最短路径长度。 Dijkstra 算法具体步骤: (1)初始时,S只包含源点,即S=,v的距离为 0。U包含除 v外的其他顶点, U 中顶点 u 距离为边上的权(若 v与u 有边)或) (若 u 不是 v的出边邻接点)。(2 )从 U 中选取一个距离 v 最小的顶点 k ,把 k ,加入 S 中(该选定的距离就是 v到k的最短路径长度)。(3)以k为新考虑的中间点,修改 U中各顶点的距离;若从源点 v到顶点 u(uU)的距离(经过顶点 k)比原来距离(不经过顶点 k)短, 则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。(4)重复步骤( 2)和( 3)直到所有顶点都包含在 S中。 2) Floyd 算法的基本思想: 可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,i到j的最短距离不外乎存在经过 i与j之间的 k和不经过 k 两种可能,所以可以令 k=1 ,2,3,..., n(n 是城市的数目), 在检查 d(ij) 与 d(ik)+d(kj) 的值;在此 d(ik) 与 d(kj) 分别是目前为止所知道的 i到k与k到j 的最短距离,因此 d(ik)+d(kj) 就是 i到j经过 k的最短距离。所以,若有 d(ij)>d(ik)+d(kj) ,就表示从 i 出发经过 k再到 j的距离要比原来的 i到j 距离短,自然把 i到j的 d(ij) 重写为 d(ik)+d(kj) , 每当一个 k查完了, d(ij) 就是目前的 i到j的最短距离。重复这一过程, 最后当查完所有的 k时, d(ij) 里面存放的就是 i到j之间的最短距离了。 Floyd 算法的基本步骤: 定义n×n的方阵序列 D-1, D0 ,… Dn -1,初始化: D-1 =C, D-1[i][j] =边<i,j> 的长度,表示初始的从 i到j的最短路径长度,即它是从 i到j 的中间不经过其他中间点的最短路径。迭代:设 Dk-1 已求出,如何得到 Dk (0≤k≤ n-1 )? Dk-1[i][j] 表示从 i到j 的中间点不大于 k-1 的最短路径p:i…j ,考虑将顶点 k 加入路径 p 得到顶点序列 q:i…k…j ,若 q 不是路径,则当前的最短路径仍是上一步结果: Dk[i][j]= Dk - 1[i][j] ; 否则若q的长度小于p的长度,则用q取代p作为从i到j的最短路径。因为q的两条子路径i…k和k…j皆是中间点不大于k-1的最短路径, 所以从 i到j 中间点不大于 k 的最短路径长度为: Dk[i][j] = min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }。三、程序清单 Dijkstra1 import .*; public class dijkstra4 { public static int[] Dijsktra(int[][] weight,int start){ // 接受一个有向图的权重矩阵,和一个起点编号 start (从 0编号,顶点存在数组中) //返回一个 int[] 数组,表示从 start 到它的最短路径长度 intn= ; //顶点个数 int[] shortPath = new int[n]; // 存放从 start 到其他各点的最短路径 String[] path=new String[n]; // 存放从 start 到其他各点的最短路径的字符串表示 for(int i=0;i<n;i++) { path[i]=new String(start+"-->"+i);} int[] visited = new int[n]; // 标记当前该顶点的最短路径是否已经求出,1表示已求出//初始化,第一个顶