图论最短路径分析及应用
6页1、最短路问题及其应用1 引言图论是应用数学的一个分支,它的概念和结果来源非常广泛,最早起源于一些数学游戏的难题研究,如欧拉所解决的哥尼斯堡七桥问题,以及在民间广泛流传的一些游戏难题,如迷宫问题、博弈问题、棋盘上马的行走路线问题等 这些古老的难题,当时吸引了很多学者的注意在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿(环游世界)数学难题 1847年,图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的问题时,发挥出越来越大的作用在实践中,图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及
2、算法的有效结合使得新的最短路径算法不断涌现。2 最短路2.1 最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法。定义1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。定义2若图G=G(V,E)是赋权图且,若u是到的路的权,则称为的长,长最小的到的路称为最短路。若要找出从到的通路,使全长最短,即。2.2 最短路问题算法的基本思想及基本步骤在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网
《图论最短路径分析及应用》由会员hs****ma分享,可在线阅读,更多相关《图论最短路径分析及应用》请在金锄头文库上搜索。
2023年河北省唐山市丰南区黄各庄镇曹庄子村社区工作人员考试模拟题及答案
北师大版七下数学几何部分期末练习
土地租赁合同书标准范本(7篇)
黄河口富硒大米种植与加工项目建议书
2022年代理协议书四篇
幼儿教师辞职信汇编15篇
高一家长会学生代表发言稿
瑞萦传媒教你分析网站是否被挂木马?.docx
印染废水处理工程设计设计
芦荟订单合同模板一
精修版哈尔滨市第162中学高中地理 3.2.2.2农业地域类型学案 湘教版必修2
节能目标责任书
高校食堂投标书(技术标)(DOC 68页)
2023普通员工年终总结报告模板(4篇).doc
人力资源总监职责(六篇).doc
亿以内数的读法 (2)
传文化、承理念、扬精神-是家族企业传承的灵魂(共5页)
高中历史之历史百科“风暴角”为什么改名为“好望角”素材
2023年最新幼儿教师师德师风范文
XXXX年关于促进本土企业发展壮大的建议(可编辑).doc
2022-10-13 9页
2022-08-06 15页
2023-08-09 10页
2022-10-05 3页
2023-06-23 2页
2023-12-02 43页
2023-11-19 9页
2022-10-25 4页
2022-09-27 4页
2022-11-17 47页