- 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
- 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
图论赵娜S130101237
Floyd-Warshall算法在日常出行时路径选择中的应用
2013-2014学年 第一学期
指导教师 张清华
科 目 图论及其应用
姓 名 赵 娜
学 号 S130101237
专 业 信息与通信工程
2013年 12 月 16 日
摘 要
最短路问题是图论解决的典型实际问题之一,应用其中的Floyd-Warshall算法,我们可以求出任意两点间的最短路径。本文在介绍Floyd-Warshall算法算法算法算法
摘 要 2
1.引言 4
1.引言 4
2.Floyd-Warshall算法介绍 4
2.1算法的选择 4
2.2 Floyd-Warshall算法思想 5
3.模型分析 5
4.算法编程实现及结果分析 11
4.1算法编程实现 11
4.2结果分析 12
5 .结论 15
6 .参考文献 15
附录 16
1.Floyd-Warshall算法的java实现 16
2.利用Matlab计算边权矩阵的迭代代码 21
1.引言
人们在实际出行中都很关心如何以最短的时间到达目的地,这其中涉及的问题之一就是在有多条道路可用时如何选取最短的一条的问题。图论在这方面成为解决问题的有力工具之一。图论中的“图”,并不是通常意义下的几何图形或物体的形状图,也不是工程设计图中的“图”,而是以一种抽象的形式来表达一些确定的对象,以及这些对象之间具有或不具有某种特定关系的一个数学系统[1]。其中最短路径问题是现实生活和网络理论中应用最广泛的问题之一。
本文介绍了最短路径问题中的Floyd-Warshall算法Dijkstra算法流程,在理论分析的基础上验证了程序的可用性。
2.Floyd-Warshall算法介绍
2.1算法的选择
求最短路径问题有几种典型的算法可以选择,例如:Dijkstra算法、Floyd算法、Floyd-Warshall算法。相比较而言,Dijkstra算法是一种求一个点到所有其他点的最短路径,该算法可以用来找到两个城市之间的最短路径。其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质[2],而且Dijkstra算法只求出图中一个特定顶点到其它各顶点的最短路,但是在很多实际问题中,需求出任意两点之间的最短路,如全国各城市之间最短的航线,选址问题等[3];Floyd算法可以解决求任意两点间最短路径,其算法的时间复杂性为O(N4);Floyd-Warshall算法解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)[4]。Warshall算法Warshall算法思想
在利用Floyd-Warshall算法求最短路径时,我们首先需要得到图的边权矩阵D。边权矩阵的定义为:已知n阶加权简单图G,设D=(dij)n*n是图G的边权矩阵,即dij=ω(i,j)(若G是有向图,则dij=ωi,j),若节点i到节点j无边相连时,则取dij=∞[4]。
已知n阶加权简单图G,设D=(dij)n*n ,是图G的边权矩阵Floyd-Warshall算法流程[5]为:
输入D矩阵;
k←1;
i←1;
dij←min(dij,dik+ dkj),j=1,2,???????,n;
i←i+1,若i≤n,转;
k←k+1,若k≤n,转;否则停止。
3.模型分析
从城市道路网络的实际特点出发,对保定市区中心城市电子地图的道路网进行网络分析,选取部分主要地点,将最佳路径有哪些信誉好的足球投注网站问题转化为图论中的最短路径有哪些信誉好的足球投注网站问题,通过对最短路径有哪些信誉好的足球投注网站算法的分析实现两个目的地间最短路径选择问题。
保定市区中心地图为:
图3-1 保定市区中心地图
这里选取保定市新市区政府、保定市政府、保定市北市区政府、保定市第一医院、华北电力大学、保定市职业技术学院、东风公园、保定火车站、古莲花池、保定市南市区政府十处地点为节点。对其进行数学模型分析,建立数学图模型为(其中各权值数据由网络资料中路途距离按比例得到):
图3-2 主干道模型图
进一步对其进行数学模型分析,利用图论中的知识建立网络节点模型图为:
图3-3 数学网络模型图
我们用边权矩阵来存储图。由上图我们可以用一个10*10的矩阵D=(dij)10*10来表示不同地点间的连接情况。其
文档评论(0)