- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论最短路径算法图形化演示及系统设计
图论最短路径算法的图形化演示及系统设计 摘要:关于图论最短路径算法的图形化演示程序的开发和系统的设计。这里首先介绍最短路径问题的概念和最短路径的算法(指迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法)。然后,在Eclipse和JDK1.6环境下开发演示最短路径问题算法的流程。最后,运行系统演示程序进行正确性验证。该算法演示程序简单易用、清晰明了、形象而生动的演示了算法
关键词:图论;最短路径;Dijkstra;Floyd;演示系统
中图分类号:TP393 文献标识码:A 文章编号:1009-3044(2016)18-0159-02
图论问题始终渗透整个计算机科学,可以说每个编程者都不可避免地与图打交道,因而图论算法对计算机科学至关重要。它的应用领域非常多。例如,图论可以应用于电路网络分析、运筹学、网络、信息论、控制论以及计算机科学等各个领域。我们知道最短路径问题是网络理论中应用最为广泛的问题之一。而这里介绍的最短路径算法是图论算法中重要的一支。最短路径算法可以解决许多问题,例如:线路安排、管道铺设、路由选择、地址选择、设备更新、广场布局、时变拓扑网络等。我们这里研究的就是最短路径问题的算法,具体指的是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法。这里通过开发一个系统演示程序来生动的阐述迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法。该系统演示程序简单易用、清晰明了、界面友好、非常实用。该系统演示程序是在Eclipse和JDK1.6的环境下用java语言开发而成的。它为解决最短路径问题提供了一个简单实用的平台
1 最短路径问题
定义:我们给定一个带权重的有向图G=(V,E)和权重函数w:E→R,该权重函数将每条边映射到实数值的权重上。图中一条路径p=的权重w(p)是构成该路径的所有边的权重之和:w(p)=∑w(vi-1 , vi) ,i=1,2,3…,k
假设一条从节点m到节点n的最短路径权重为W(m,n),且W(m,n)计算如下:
①如果存在一条从节点m到节点n的路径,则:W(m,n)=min{w(p)|p是一条从节点m到节点n的路径};②否则,W(m,n)=∞
从节点m到节点n的路径p,如果满足w(p)= W(m,n)则该路径p即为从节点m到节点n的最短路径。求从节点m到节点n的最短路径和最短距离的问题就是最短路径问题
2 最短路径算法
2.1弗洛伊德算法思想
我们使用三重for循环产生一个矩阵来记录每个节点间的最小距离。对于弗洛伊德(Floyd)算法我们使用矩阵Juzhen[i][j](i,j=1,2,……n+1)存储有向图的权重值。所以,其基本思想为:初始化一个n阶矩阵A(k),其主对角线上的元素初始化为0,非对角线上的元素初始化A(k) [i][j],其中每一个A(k) [i][j]是节点i到节点j的权重值,k是运算到第几步。算法一开始,我们选择任意两个节点分别作为起始点和终止点,若他们之间有边则取其权重值作为他们的路径长度,若无权重边,则令其路径长度为∞,再有k=0时,我们初始化A(k)[i][j],此时A(0)[i][j]=Juzhen[i][j],将路径上的节点加入集合S中,之后再选择不在集合S中但能构成最短路径的节点,使其加入集合S,如果在i节点和j节点之间增加了中间节点后,使得节点i到节点j的路径比A(k) [i][j]小,就用新的权重值去更新A(k) [i][j]
因此,弗洛伊德(Floyd)算法步骤如下:
(1)当k=0时,A(0)[i][j]= Juzhen[i][j]; 其中Juzhen[i][j]为邻接矩阵
(2)当k=i+1,i+2,…,j时,A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中A(k)[i][j]表示节点点vi 到vj , 中间节点的不大于k的最短路径的长度,这里求的是中间节点的不大于n的最短路径的长度即A(n)[i][j]
因而,其算法可以描述为:
(1)令D[i][j]=A[i][j]
(2)for(k=1;k D[i][k]+ D[k][j])
{D[i][j]=D[i][k]+ D[k][j]}
(3)算法结束后矩阵D存储了所有节点之间的最短路径值
2.2 迪杰斯特拉算法的思想
Dijkstra算法解决的是带权重的有向图上单源点最短路径的问题。该算法要求所有边的权重都为非负值。Dijkstra算法把图中所有的节点分为两组:设集合S表示已经求出的最短路径上的节点的集合;集合T=V-S表示在集合V中而在节点S之外的所有的节点的集合。然后把集合
您可能关注的文档
- 初中生在学习数学过程中出现错误成因分析及对策.doc
- 初中生物教学中突破重难点几种尝试.doc
- 初中物理教学中德育渗透.doc
- 初中生现代文阅读能力培养策略.doc
- 初中生自我管理能力培养探究.doc
- 初中生数学课堂主动提问能力培养策略.doc
- 初中生文言文学习兴趣培养探究.doc
- 初中生英语阅读存在问题及对策.doc
- 初中生非中考学科堂学习氛围现状与对策.doc
- 初中社政课在教学中作用及教学方法探讨.doc
- 2024年江西省寻乌县九上数学开学复习检测模拟试题【含答案】.doc
- 2024年江西省省宜春市袁州区数学九上开学学业水平测试模拟试题【含答案】.doc
- 《GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语》.pdf
- 中国国家标准 GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语.pdf
- GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- 《GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构》.pdf
- 中国国家标准 GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 中国国家标准 GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 《GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南》.pdf
文档评论(0)