当前位置: 首页 > 设计/艺术 >

最短路问题的设计

最短路问题的设计
3.1 程序开发目标
为使用者提供一个修改方便、操作简单的运行程序。
3.2 最短路问题程序设计
3.2.1 最短路问题简介 对于图 Graph,在所有的路径的情况下,目前效率最高的方法是由 Dijkstra 于 1959 年提出的。 3.2.2 程序设计 对于任意一个有向或无向交通图,每条弧都具有一个数字属性,该数字属性 表示通过通过这段路程所需要的时间,现在某人要从一个起点出发,要通过这个 交通图到交通网内另一点。求花费总时间最小的旅行路线。 Dijkstra 方法的基本思想是规定一个起点。程序搜索时从起点出发,成环 形发散地探索最短路径经过的顶点。Dijkstra 方法把交通图中的点集合分化为 两个集合。分别称为集合 S 和集合 V-S。第一个集合 S 表示目标交通图中据起点 的最短路径已经确定的顶点集。交通图中还未涉及的其余的顶点暂时存放在另一 个集合 V-S 中。算法开始后,集合 S 只包含起点或源点,此时只知道源点或起点 到本身的路径为 0,为最短路径。设 v 是 V 中的某个顶点。一条路径被称为中间 路径,当且仅当它满足从起点开始到目标顶点的过程中只经过 S 中的顶点。 Dijkstra 算法用矩阵 D 来记录当前所找到的从源点 s 到每个顶点的最短中间路 径长度。矩阵 D 的初始状态为:如果从源点 s 到顶点 v 有路径,则 D[sv]记为弧 的权值;否则将 D[v]置为无穷大或一个对于此交通图来说近似无穷大的值。 Dijkstra 算法在每次运算中都作用。算法从集合 V-S 中裁出顶点 u。其中顶点 u 满足在 D[su]是集合内最短路径。将 u 增补进集合 S,同时修改矩阵中由 s 到 达的最短路径长度。如果增补 u 作中间顶点后,的最短中间路径比之前减少,则 修改的最短中间路径。然后,重复上述操作,一旦 S 包括了所有 V 中的路径经过 点,矩阵 D 中的各顶点的最短中间路径值就相当于从起始点 s 到该顶点的最短路 径长度。 堆中的数据一般采用数组的形式存储。存储时可以采用具有三个存储域的一 维数组或具有四个存储域的一维数组。其中前者包含节点的值,节点左下方子节 点的值,节点右下方子节点的值;后者包含节点的值,节点左下方子节点的值,

节点右下方子节点的值,节点父节点的值。数组的数量由堆的具体大小决定。数 组中不存在的部分由空值表示。
最小堆是包含关键码的序列。一般来讲,最小堆可以表示为完全二叉树的形 式。不过与二叉搜索树不同,最小堆不是完全排序的。最小堆一般只满足部分有 序的性质。通常来说,最小堆只需满足父节点的值小于左右两个子节点的值即可。
最小堆的遍历思想是朴素而又简单的。最小堆中比较复杂的操作是插入与删 除。
对于最小堆中的插入操作,先将要插入的数值放在堆的尾部,随后逐一自尾 部开始比较,如果能够保持最小堆的性质,就保持元素位置不变。如果不能保持 最小堆的性质,就交换元素位置。
对于最小堆中的删除操作(被删除的元素只能为根节点上的元素),删除某 个元素后,将最小堆的尾部元素替换入被删除元素的位置,随后如同插入操作一 样,检测更新后的堆是否满足最小堆的性质。如果不满足,则自上而下的交换元 素位置。
3.3 程序功能模块
本文编译的最短路径计算程序可以生成数组形式的最短路径计算结果与图 像形式的最短路径计算结果。




友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版