最短路径问题在城市超市选址中的应用

1、 毕业论文（设计）最短路径问题在城市超市选址中的应用院 系 :数学与计算机学院专 业:数学与应用数学年级（班级）:2010级姓 名:陈妹珠学 号:20104041011指导教师:谭秋月职 称:讲师完成日期:2014年5 月20 日摘 要对于最短路径问题的探索研究,向来都是数学界和计算机科学界所热衷研究的一个方向.它不仅在学术上具有重要的理论意义,更对于实际生活的生产有着举足轻重的实用价值.例如在医疗安全上的应急急救系统、政府的城市规划系统、卫星电子导航系统等其他领域.同时,最短路径问题又可以进一步引申为最少时间问题、最低费用问题等,但它们的核心解题算法都是最短路径算法.本文利用了图论中最短路径

2、问题的相关知识及重要定理,对若干最短路径算法进行归纳,同时研究城市超市选址的影响因素,最后将最短路径问题的部分知识应用到了城市超市选址中,建立数学模型并求解,由此解决了超市经营的首要前提选址.关键词: 图论;最短路径;超市;选址AbstractThe research and exploration of the shortest path problem is always be a hot spot for passionate about maths and computer science. It not only has important theoretical significa

3、nce in academic, but also has significant practical value for the actual production of life. Such as emergency first aid system on medical safety, the governments urban planning system, electronic navigation satellite system and other fields. At the same time, the shortest path problem and can be fu

4、rther extended to a minimum time problem, the minimum cost problem, etc. But for the core of the algorithm, its the shortest path algorithm.In this paper, the use of the shortest path problem in graph theory knowledge and the important theorem, the number of shortest path algorithms are summarized,

5、at the same time, study for the influence factors of city supermarket site selection, the final will be applied to the shortest path problem of city supermarket site selection, establish mathematical model and solving, thus solved the first premise of supermarket business - location.Keywords: Graph

6、theory; The shortest path; The supermarket; Site selection目 录1 引 言12 相关概念22.1图的相关定义22.2最短路径33 最短路径问题的相关介绍43.1单源单汇最短路径问题43.2单源多汇最短路径问题43.3多源多汇最短路径问题54 最短路径问题的相关算法64.1Dijkstra算法64.2SPFA算法74.3Floyd算法85 选址问题105.1相关知识105.2引用定理:116 最短路径问题在超市选址中的应用126.1问题提出126.2问题分析136.3模型假设146.4符号说明146.5模型原理146.6模型建立与求解16

7、6.7模型结果207 结 论21谢 辞22参 考 文 献2323最短路径问题在城市超市选址中的应用1 引 言最短路径问题是图论中关于网络优化的一个重要组成部分.作为许多网络中选择最优问题的基础,在政府的城市规划系统、卫星电子导航系统、道路交通运输系统等科学领域中都占据着主导地位.生活中许多的实际问题,都可以通过数学语言,抽象为图论意义下的网络模型,然后利用图论逐步的对最短路径问题求解.对于最短路径问题的探索研究,是数学界和计算机科学界一直所热衷的话题.以数学语言描述最短路径,便是在网络上所有的有效路径中寻求一条距离最短的路径.一般来讲,口头上常说的最短路径不单单是指空间距离上的距离最短,这个意

8、义可以延伸到其他度量上,比如时间用时最少,费用花费最低,路线容量最小等.应用最短路径问题相关知识解决城市超市选址问题,进一步的可以将其拓展到生活中的其他实际问题选址中去.因此,对于最短路径问题的研究无论在学术上还是实用中都具有十分重要的意义.本文将要在城市超市选址的问题中考虑影响选址的关键因素,并利用图论中最短路径问题的相关知识确定超市选址的位置,为投资者创造更高的经济效益.2 相关概念2.1 图的相关定义对事物以点表示,并以任意点点之间的连线表示事物之间存在的某种关系,换句话说就是集合论中描述二元关系的图,这样构成的图即为图论中的图.图不能简单的看做是几何学中的三角形、多边形等这些几何图形,

9、几何图形与图论意义中图的本质区别就是只关注在于点点之间是否有连线,而对于点的位置以及连线的曲直不关心.由于图对各科学领域中的问题都能够进行恰当的描述与建模,所以图在各领域中都起到重要的作用.定义2.1.1 一个无向图是一个有序的二元组,记作G,其中（1） V称为顶点集,其元素称为顶点或结点.（2） E称为边集,它是无序积V&V的多重子集,其元素称为无向边,简称为边. 定义2.1.2 一个有向图是一个有序的二元组,记作D,其中（1）V同无向图.（2）E为边集,它是笛卡尔积VV的多重子集,其元素称为有向边,简称边.对于有向图与无向图的定义,人们常用小圆圈表示顶点,顶点之间的连线表示无向边,具有方向

10、的连线表示有向边.定义2.1.3 设G=为一无向图,vV,称v作为边的端点次数之和为v的度数,简记为度,记作,在不发生混淆时,简记为d(v).设D=为有图,vV,称v作为边的始点的次数之和为v的出度,记作,简记做.称v作为边的终点的次数之和为v的入度,记作,简记作,称+为v的度数,记作的d(v).定义2.1.4 给定图G=（G为有向图或无向图）,设W:(R为实数集),对G中任意的边e=(G为有向图时,e=),设W（e）=,称实数为边e上的权,并将标注在边e上,称G为带权图,此时常将带权图G记作.设,称为的权,并记作W(),即W()=.定义2.1.5 对于无向图G,其邻接矩阵A=,其中:对有向图

11、G=,其邻接矩阵A=,其中: 对有向赋权图G,其邻接矩阵A=,其中: 2.2 最短路径定义2.2.1 在无向图G=(V,E,)中: （1）顶点与边相互交错且（i=)的有限非空序列w=()称为一条从到的通路,记为. （2）边不重复但顶点可重复的通路叫做道路,记为. （3）边与顶点均不重复的通路叫做路径,记为定义2.2.2 在赋权图G中,从顶点u到顶点v的具有最小的路P*(u,v),称为u到v的最短路. 3 最短路径问题的相关介绍最短路径问题是图论问题中的典型代表.对于一个网络,每条边都有一个权值（如长度、成本、时间等）存在,在图中寻求一顶点到另一互异的顶点之间路径,并使该路径的总权值和最小,则所

12、寻求出的路径即叫做最短路径.图中边的权值可多种,也可以同时存在多种,只是最后根据比例,算出边的综合权值.一般将最短路径问题作如下的3种情况分类.3.1 单源单汇最短路径问题单源单汇最短路径问题就是寻求从一固定初始点u到另一固定目标点v之间的最短路径.如图3-1所示,求到的最短路径问题即为单源单汇最短路径问题.图3-1单源单汇最短路径问题是学会解决最短路径问题的基础,只有对这类问题能够熟悉应用,才能够进一步的将之扩展到更深层次的问题,如图中一固定点到其余顶点的最短路径,或者是图中任意两顶点间的最短路径.3.2 单源多汇最短路径问题单源多汇最短路径问题就是寻求从一固定初始点u到剩余点的最短路径.如

13、图3-2所示,求到其余顶点的最短路即为单源多汇的最短路径问题.图 3-2对于单源单汇最短路径问题,一般常见到的就是出发点为已知,或者是终点为已知,这两种情况在无向图里是没有区别的,可以等同为同一种情形.只有在有向图中才有区别,并且只要把关于确定出发点的最短路径问题中所有路径方向做一个反转,通过这样的方式就可以得到关于确定终点这类情形的最短路径问题.3.3 多源多汇最短路径问题多源多汇最短路径问题就是对于给定的节点集合,寻求其中任意两节点间的最短路径.如图3-3所示,求任意两顶点间的最短路即为多源多汇最短路径问题.图3-3对于多源多汇最短路径问题,有时候可以将它分解成多个单源多汇最短路题,以每一

14、个顶点为出发点来进行对单源多汇最短路径问题的求解. 4 最短路径问题的相关算法最短路径问题是在全体网络最优化问题中被研究极普遍的一类课题,它常应用于通信工程等领域中.对于最短路径问题求解的作法有许多种,包括早期将限制环境作为根据的深度优先寻求方法,将有向无环图作为根据的动态规划法,将邻接表作为根据的A*算法,最大相关边法等,以及如今发展比较活跃的Dijkstra算法（迪科斯彻算法）、SPFA算法和Floyd算法（弗洛伊德算法）.根据不同的网络图特性,实际的软硬件环境与应用需要,以及算法复杂度等方面,运用不同的最短路径算法得以实现.就最短路径问题,给出了当前运用比较广泛的最短路径理论算法Dijk

15、stra算法、SPFA算法和Floyd算法,下面依次介绍.4.1 Dijkstra算法Dijkstra算法有些人将它称为单源最短路径法,有些人是将它称为标号法.由计算机科学家荷兰人艾兹格迪科斯彻于1959年所提的解决最短路径问题的寻求方法.该算法的作用就是用于求解单源点最短路径,在如今的这个21世纪里,它仍然是大家所公认的在网络中,解决从一固定点为起始点,到其它随意而取的顶点的最短路径问题的极佳算法.Dijkstra算法是运用贪心算法的计策,从源点出发,不断地连续通过相连通的点去寻求出到其他顶点的最短距离,它的基本思想是设立一个顶点集合S,逐步地向外探寻,从而不断的扩充这个集合.一个顶点属于集

16、合S当且仅当从源点到该点的最短路径已寻求到,从而S存放在已求到其最短路径的顶点,则未曾确立到的最短路径的顶点集合为V-S,其间V是网中全部顶点集合.开始时S中仅存在源点,同时修改V-S中点的最短路径的长度值,寻求当前最短路径点,根据最短路径长度值逐步递增的顺序逐个用V-S中的顶点将其加入到集合S中,直到S中将全部顶点包含,而V-S为空.Dijkstra算法步骤为:已知赋权有向图D=（V,A）. （a）设起始点为V,则S是只包含顶点V的集合,同时令W=V-S,则W是除V以外,包含图中所有其它顶点的集合.V所对应的的相应距离值为0,即D=0.W中顶点所对应的相应距离值是规定符合如下要求的:如果图中

17、有弧存在，则V顶点的相应距离是该弧的权值,否则就为. （b）再从W中找到一个顶点,使它到S的路径最短,同时将从W中剔除,然后使加入到S中去,即当前所求到的由S到的路径即为S到的最短路径. （c）每次再S中加入一个顶点后,就要对W中各个顶点的距离值全部再一次修改.如果加入到作为一个中间顶点,从而使+的值小于的值,则原先的距离值由+所替换,即表明新生成的最短路径的长度比原来计算那条来的更短,那么就要更新这个距离以及最短路径.（d）重复第（b）步骤和第（c）步骤,使在被修改过的W中选取距离值最小的那个顶点加入到S中,同时调整W中的各个顶点距离值,以此循环进行,直至S中将图中所有顶点全部包含才得以停止

18、,即S=V.此时的Dn即由顶点出发,到顶点的最短路径长度值.4.2 SPFA算法SPFA算法是1994年由段凡丁发布的关于求单源最短路径的一种算法.在好多时候,给定的图也是有存在负权边的,此刻对于与Dijkstra算法类似的算法便无法解决,也就没有了用武之地,则此时SPFA算法便适合派上用场了.这是一种具有高效的解决最短路径问题的算法.SPFA算法的基本思想是用动态逼近法:先设置一个先进先出的队列来存储那些用来待优化的顶点,在优化的时候每次取出队的首顶点u,同时将对离开u点所指向的顶点v根据u目前所有的最短路径估算值做松弛操作.假如v点的最短路径估算值有些变化或调整,并且v点不存在于当前的队列

19、中,就将v点置于队尾.依据此方法,不断从队列中取出节点以松弛方式进行操作,直到队列变空停止.此方法能够保证只要存在最短路径,以上SPFA算法必将能求出路径最小值.SPFA算法不仅可以求解出最短路径,同时也可以对网络图进行判断是否存在负环.如果某个点已经不止N次进入到队列,则负环存在,而SPFA对于处理带负环的图是无计可施的,即无法求解.因此在该算法执行前,可以实行一次拓扑排序,从而判断负权回路在图中是否存有.在对SPFA算法的具体步骤说明前,作如下说明: disti的意思是从源点到顶点的最短路径长度.SPFA算法的步骤为:（a）初始化,将源点加入到队列中,dist=0,其他点dist=+.（b

20、）每次在队列中掏取首个元素,以此点作为一个中间点,并对与该点存在边相连的点进行松弛操作.如果松弛成功,则调整dist的值,同时在队列中将点加入.（c）重复执行步骤（b）,直至队列为空.4.3 Floyd算法通常在某些问题里,对图需要确定任意两点间的最短路径长度.解决此问题的一个有效方法是采用贪心策略的dijkstra算法求解,将每一个顶点依次轮流的作为源点,将dijkstra算法重复执行n次,从而求出每对顶点间存在的最短路径,这样所用的总的时间复杂度则为.程序越复杂,计算量越大,这显然过于繁琐.并且一个有向图里,当节点间权值为负数时,dijkstra算法就行不通了,斯坦福大学计算机科学系教授f

21、loyd对此提出了另外一个求图中任意两顶点之间最短路径的算法,即floyd算法.其是一种用来对给定的加权图搜索它顶点间最短路径的算法,它是依靠权矩阵,对随意而选取的两点直接寻求最短路径.对于稠密图,处于它紧凑的三重循环结构,而比执行dijkstra算法|V|次的效率还高,虽然时间复杂度为,空间复杂度为,不适合计算大量数据,但其算法的形式更简单,易于理解.且floyd算法对边的权值条件不做任何限制,即可正可负,只要图中不存在负环就可以算出任意两个节点之间的最短路径长度.floyd算法的基本思想是以随意而取的两个互异顶点和组成的距离带权邻接矩阵开始,在插入一个中间点时,将以上已知得到的和组成的距离

22、带权邻接矩阵中最短路径同插入形成的和可能形成的路径做个对比,然后选取最小值形成一个新距离矩阵.根据此方法,依次插入中间点,构造出对应矩阵,在每个顶点都作为随意而取的两个互异顶点到的中间点时,得到的那个最后矩阵即为图的距离矩阵.相应的由此可以看出任意两点之间存在的最短路径.构造图G的距离矩阵过程是:（a）对一个具有n个顶点的图G,将顶点用n个整数（即为1,2,n）进行编号,将G的带权邻接矩阵D作为距离矩阵的初值,换句话也就是说=D.若两点间有边时,则 与边的权相等.如果两点之间边不存在时,则.其中当i=j时,=0.（b）构造=,而=min（,+）是从到的只允许以 作为它们中间点的所有路径中最短路

23、长度.（c）将=min（,+）,作为依据,逐步的构造,而其中表示的是以为出发点,以为最终点的只允许最短路的长度是根据、 、作为中间点的路径.即是从以为出发点,以为最终点 ,同时中间可插入随意选择的一个顶点的路径中最短路的长度.（d）此时就构造出来了图G的距离矩阵.5 选址问题5.1 相关知识选址即是在一定区域内为某种服务设施选择确定它的位置,并使其达到它指标最优值,解决的是服务设施与服务对象间的联系效益或效益问题.而其中的区域即可通过图来表示服务设施所服务的范围及其联系.所谓的服务设施可以是公共服务设施（如医院、消防中心等）,也可以说是生产服务设施（仓库、配送中心等）.选址问题的类型多样,如社

24、会服务型与经营型、离散型与连续型、单服务设施与多服务设施.其中的社会服务型又可分为普通型选址（如学校、银行等）和紧急服务型选址（如紧急医疗救助中心、消防中心等）.在此介绍服务设施和服务对象都位于同一个图上顶点的单服务设施问题.对于单服务设施问题,可以将其整体的划分为如下两类,即重心问题、中心问题.5.1.1 重心问题在服务对象有相对集中的区域位置时,通过网络反应各对象间的联系关系.对于服务设施(如学校、图书馆等非紧急型服务)的选址,要求的是设施到所有服务对象点的最短路径距离的总和最小,通常情况下则考虑人口密度问题,从而使全体被服务对象的来往平均路程最小.对此问题的求解算法为:(a)求距离矩阵D

25、(b)计算各顶点作为超市时的总路程: 其中d（z，j）表示在网络中以顶点z为起始点,到顶点的最短距离.顶点z或许在网络的顶点上,也或许是位于某一边上.若z在边（a,b）上,且距顶点的比例是c,则,若网络为有向,则.(c)求,使,即就是超市选址的最优点.此点称为图G的重心点或中位点.5.1.2 中心问题对于服务设施（如医院,消防中心等紧急服务设施）的选址,关键在于网络中处于最远位置的被服务点与服务设施的距离尽可能的小.对此问题求解的算法为:(a)求距离矩阵D(b)计算各顶点作为超市时的最大服务距离:(c)求,使,即就是超市选址的最优点.此点称为图G的中心点.5.2 引用定理定理5.2.1 重心问

26、题的最优解一般是坐落在网络的某一顶点上.定理5.2.2 网络的中心,必位于网络中最长的路的中点.6 最短路径问题在超市选址中的应用 某种服务设施在一个确立的区域内选定它的位置,同时使其某一指标达到最优值,就是常在实际生活中所要研究的选址问题.随着社会的繁荣发展和国民生活水平的逐渐提高,人们对生活的便捷度也要求的越来越高,而作为以经营大众化衣、食、日用品为主,为人们生活提供各种需求产品的超市,其选址问题倍受关注. 超市作为一种非紧急型的公共服务设施,一般主要考虑人口密度问题,建立在居民周围.作为消费者,对超市服务点设置的选址莫过于在质量保证的前提下对距离远近的要求,追求购物便利.那么这就涉及到了

27、上面所提到的最短路径问题.超市如何选址建立,能使得居民购物方便,是每个投资所考虑的问题.6.1 问题提出对于超市的经营,其主要目的就是创造经济效益,而选址是影响经济效益的首要因素.具备有利的地理位置将会吸引永不截断的顾客,其选择恰当,就意味着享有“地利”,将会与竞争对手在产品类似、服务水平基本相同等条件下获取更好的经济效益.因此,超市在分析经济效益时,应注重超市地址的影响效果,根据对超市选址产生重大影响的重要因素进行量化分析,与图论中最短路径问题结合,对超市的选址提出有益且有效的建议.以武夷山市武夷学院超市选址为例,如图6-1所示:图6-1 武夷山市武夷学院图6.2 问题分析首先,应该明确店址

28、选择的重要性.其合适的选址,将会与竞争对手在规模类似、产品质量、服务水平等基本等同条件下享受更好的经济效益,提高超市的销售业绩.而销售业绩的提高主要在于超市对于居民市场吸引力的大小,即超市将那些优先选择本超市作为消费产地的有效顾客所分布的位置区域.若市场吸引力越大则客流量越多,从而带动销售业绩.否则超市的营业将会变的萧条.在分析出顾客与超市市场吸引力的关系后,则需要分析影响市场吸引力的因素,进行量化分析,求出各个选址影响因素的综合指标Y,以此作为一个地址点的影响有效区域,成为该点的权值.并由实际城市环境,用最短路径问题的算法求出各顶点间的最短路径的距离矩阵.再以各顶点的权值加权,从而求出每个顶

29、点到其他剩余顶点的最短路径长度的加权和,最后对此进行判断,选出网络的重心点即为建立超市的最佳位置.6.3 模型假设（1） 超市物品齐全,可以容纳全部进来消费的顾客以及满足她们的需求;（2） 人们选址购物消费的地点都是距离自己最近的超市;（3） 不考虑政府政策影响.6.4 符号说明S:竞争者营业面积 BK:商业繁荣程度 I:该市场吸引力区域内第i居民区 BD:城市规划系数:居民区到超市的距离 TC:需求指数 CLI:影响指数 PI:增长估计 RDP:消费人口数目 CI:竞争指数 ADP:人均购买力 CL:竞争者与本店址距离的长远 PDI:人均可支配收入 MI:未来可预见的人口搬迁率CPI:消费价

30、格指数 SS:未来可能出现的威胁指数BII:竞争者品牌强度指数 FS:未来一年内竞争者营业面积:便捷函数 FBII:未来一年内竞争者品牌强度:该居民区在地图上的坐标 :该居民区在地图上的坐标;:点到超市所在位置（a,b）的最短实际距离FL:未来一年内竞争者与本店址距离的长远6.5 模型原理将影响市场吸引力因素分成收入与成本两类,本市场内各个居民点所具备的购买力是收入类主要考虑的方向;各居民点到连锁网点的距离以及连锁网点之间的竞争状况是成本类主要考虑的方向,以同一市场区域内同行竞争者数目或营业面积之和表示.由于以郝夫模型为基本而提出来的市场引力模型,考虑的因素比较与实际情况相符,且可验性强,所以

31、本论文选用市场引力模型进行研究.市场引力模型为: ; 将r设为1其中Y 表示超市所处位置的市场吸引力, m 代表该市场吸引力区域内居民点个数,表示区域内各个居民点的购买力,代表各个居民点到超市的距离,n表示同一区域内同行业竞争者的个数.对选址产生影响的因素,主要考虑以下几类:（a） 城市规划.对城市规划进行分析,研究是否会有街道拓宽、大型商业中心开发等建设,从而预期店址周围环境变化,对市场吸引力做出合理估计与措施,并预测超市的长远发展.（b） 交通便捷度.由于现代人逐渐追求绿色环境,则对便捷度的分析主要考虑自行车、机动车的停放位置方便度和公交乘坐的方便度.若未来超市选址处于交通方便位置,将会有

32、源源不断的客流.（c） 人口需求.对人口需求的影响主要动态分析备选店址周边是否有光大居住人口、人均购买力以及消费习惯等.同时预测人口增长、收入增长等变化的增长性.（d） 同行业竞争.对同行业竞争的分析主要考虑对竞争者营业面积、与本店址距离的长远、品牌强度指数、未来可能出现威胁等所表现的竞争抗衡力.（e） 商业繁荣程度.对商业繁荣程度的分析主要考虑备选店址所处的商业环境繁华程度,比例商店数目、客流量、营业面积等,从而判断属于城市中心、二区、三区或郊区环境.对选址因素的量化分析:a) 量化城市规划和商业繁荣程度.以影响指数CLI表示城市规划系数BD和商业繁荣程度BK的量化,且CLI=BDBK.若处

33、于商业中心,BD设为3;若处于城市二区,BD设为2;若处于普通街道,BD设为1.本论文BK指两年城市规划影响下肯增加的商业繁荣系数.b) 量化人口需求.以需求指数TC表示本区域内人口需求的量化.包括消费人口数目（RDP）,人均购买力（ADP）和增长估计（PI）.人均购买力（ADP）可由人均可支配收入（PDI）除以消费价格指数（CPI）求得,即 ADP=PDI/CPI.（PDI、CPI、RDP可查询统计年鉴得到）其中的增长估计（PI）是指该区域在未来可预见的经营期内的人口自然增长（NR）,人口搬迁率（MI）以及人均购买力增长对该区域消费需求的影响的估计PDII, PI=（NR+MI）PDII.c

34、) 量化交通便捷度.以便捷函数表示对交通便捷度的量化. 其中i表示该市场吸引力区域内第i居民区,表示该居民区在地图上的坐标;表示居民区到超市的距离;（a,b）为超市的位置;为点到超市所在位置（a,b）的最短实际距离.d) 量化同行业竞争.以竞争指数CI表示对同行业竞争的量化,包括竞争者营业面积S、与本店址距离的长远CL、品牌强度指数BII以及未来可能出现的威胁SS,其中SS包括未来一年内竞争者营业面积FS、与本店址距离的长远FL以及品牌强度FBII.若竞争者品牌强则BII1;若品牌相当,则BII=1;若品牌若,则BII1.设目前竞争者有 q 个,一年之内将 p 个竞争者进入,则其中k为比例常数

35、,可取1.6.6 模型建立与求解综合分析影响选址的因素之后,得到各因素的综合评价指数Y.Y满足以下公式:其中, k 为比例常数,在本文城市超市选址问题中将k设为1;, 为各选址影响要素在影响选址决策中的权重，可根据统计数据由层次分析法得出行业权重常数.经量化后,以上各数据都可查询或测量,最终可得到已知的综合评价指数Y.按如下规则将武夷山市武夷学院地图取点连线,如图6-2所示;由于学生、教师生活消费地主要分布在图下方,故本题只考虑学生的生活区:（1）将人口比较聚集的地方出口作为一个点,如宿舍、商店等.（2）将人口汇集处作为一个点. （3）将连接各点的线段作为边,道路的距离就是边的权.图6-2 武

36、夷山市武夷学院简图将图6-2抽象为网络图G,如图6-3所示;记G=（V ,E）,V表示边集,E表示点集,由图6-2可知A中共有11个点,每条边的权（即相邻两点间有以线段连接而成的距离）为已知条件.图6-3 武夷山市武夷学院网络图运用最短路径算法求出最短路径.由于floyd算法的复杂度整体较低,本论文对最短路径采用floyd算法.由图6-3可读取有11个结点,用表示；用表示各点间的长度;用表示该节点的综合评价指数,即该节点权值.解题步骤，如下所述:(a) 判断初始矩阵,如果顶点与顶点有边相连,则就是该边的权值,数据经过实际勘察测量可知.如果到,即为0,若无边相连,则将该权值设为.根据图6-3.从

37、而得到初始带权邻接； （b) 根据floyd算法的原理插入中间点,通过已知得到的,求出. 主对角线上元素都为0则不需要计算,而第3行至第10行的首个元素都为,故其余元素与相应的元素一样,第2行首元素为3,根据可得只有变化,即=19;第11行首元素为16,根据可得只有变化,即=19,因此同理,依次插入中间点,得到逐步更新的距离矩阵;从而得到优化矩阵D（c）根据市场吸引力模型,经查找数据计算可得各顶点的综合评价指数,以下假设算得的各顶点的综合评价指数为：=0.8;=0.7;=0.5; =0.4; =0.3;=0.9;=1.1;=1;=0.5;=0.6; =0.7; 将各顶点的综合评价指数(i=1,

38、2,11)根据进行加权,求出得到如下每个顶点到其余各顶点间最短路径长度的载荷加权和: （d）根据（c）中求出的载权加权和进行判断.求出点使所以顶点是图6-3的重心点,即超市建立在点是最优决策方式.6.7 模型结果通过建立数学模型可知,在综合考虑对超市选址产生影响的因素后,得到了对于该点作为超市备选址时,所产生的对消费者市场吸引力大小,即优先选择本超市作为消费产地的有效顾客所分布的位置区域大小,同时进一步的联系最短路径知识与选址问题知识，得到到其他各点的载荷加权和最小.因此,在武夷山市武夷学院应该在点建立超市是最优的方案.7 结 论最短路径问题是图论问题的典型代表,本文利用它的定义、定理等知识与

39、实际问题联系,将问题转化为图论语言建立数学模型,从而从根本上解决实际问题.应当明白,图不仅仅是处理和表达问题的有效手段,而且在各个科学领域内也已成为对有系统功能的模型进行分析和设计等不可或缺的理论.对于最短路径涉及选址问题在实际生活中应用广泛,如图书馆、急救中心等公共服务设施的建立.以图解释实际问题,用点表示事物,以两点间连接的线表示两个事物之间具有特定关系,这是运用图论解题必要翻译初始阶段.在应用图论知识来解决实际问题中,其关键点就是在于将原来的问题正确的翻译成图论语言,也就是对题目正确判断所要研究的各个元素之间的关系,再用图论语言描述,使问题变得易于分析,简单明了.本文将影响选址的因素进行量化,然后与最短路径问题结合,从而求出超市选址的最佳位置.进一步的,我们也可以将本论文的知识扩展到其它选址问题,如运动场、学校、图书馆等.但是,图论中仍然有许多知识等待着去进一步的探究,它的应用领域目前依然狭隘,希望在今后能够有更多的探寻者去进一步的挖掘其中奥秘,使图论的研究领域更广泛,为人类经济服务发展提供更便捷的方向.谢 辞弹指一挥间,在完成毕业论文的同时,四年的大学生活即将落下帷幕.站在毕业的门槛上,回首往事,四年的求学生涯彷如电影般在脑海一一放映,那些曾经的奋斗与辛苦此时已化作丝丝细雨,在我的心间落下甜美的回忆.在毕业论文即将付梓之际,我要向我的指导老师谭秋月老师致以崇