图论最短路径选址问题.doc

《图论最短路径选址问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.姓名：学号：专业：word范文.图论的实际应用——蔬菜批发市场选址问题摘要：在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，都可借助图论知识得以解决，而最短路问题是利用图论解决的一个典型的实际问题。图论中最典型的两种求最短路径的算法分别为Dijkstra算法和Floyd算法，其中Floyd算法广泛应用于求任意两点间的最短路径。本文介绍了利于Floyd算法来解决城市蔬菜批发市场选址的问题。关键词：最短路；Floyd算法；选址问题0．引言对于许多地理问题，当它们被抽象为图论意义下的网络

2、图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题[5]。在路径的优选计算问题中，最常见的是最短路径问题，最短路径可能是给定两点间的最短路径，也可能是任意各点间的最短路径。而在顶点的优选计算问题中，最为常见的是选址问题，所谓选址问题就是在某一地理区域构成的网络中选择一个顶点，建立服务设施，为该网络中的各个点提供服务，使得服务效率最高[3]。选址问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。也可以

3、是生产服务设施，如仓库，转运站等等。可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究[4]。尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。1．最短路径问题最短路径问题是图论研究的一个经典算法问题，其目的是求出给定两点之间的长最短的路径，这里所说的长具有广泛意义，即可指普通意义的距离，也可是时间或费用等[2]word范文.。因此，最短路径问题通常可以归纳为三类：(1)距离意义上的最短路径，即求两点

4、间距离最短的路径；(2)经济意义上的最短路径，即为两点间的费用最少的路径；(3)时间意义上的最短路径，即选择两点间最节省时间的路径。以上三类问题，都可以抽象为同一类问题，即带权图上的最短路径问题。不同意义下的距离都可以被抽象为网络图中边的权值，权值既可以代表“纯距离”，又可以代表“经济距离”，还可以代表“时间距离”。1.1Dijkstra算法Dijkstra算法是一种求解最短路径方法。它是一个按路径长度递增的顺序产生最短路径的算法，其基本思想是：设图中所有顶点集合为V，另设置两个顶点集合S和T=

5、V-S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点V1，然后不断从集合T中选取到顶点V1的路径长度最短顶点Vi加入到集合S中，集合S每加入一个新的顶点Vi，都要修改顶点V1到集合T中剩余顶点的最短路径长度值，此过程不断重复，直到集合T中的顶点全部加入到S中为止。这样，就可以求出一点到其它的任一顶点的最短路径。Dijkstra算法简单易懂，在求给定两点间的最短距离时效率很高，但是其只能求图中一个特定结点到其他各个结点的最短路[1]。当需要

6、求出图中任意两顶点的最短路径时，就需要以图中的每个顶点为起点，依次求出到另外顶点的最短路径，在顶点数目比较多的情况下，其效率将非常低下。1.2Floyd算法Floyd算法为另外一种求最短路径的算法。在某些问题中，需要求出图中任意两顶点之间的最短路径，这时，Floyd算法将比Dijkstra算法具有明显优势。Floyd算法借助于权矩阵的运算直接可以求出任意两点之间的最短路径[2]。Floyd算法的实现思路为：首先定义赋权图的边权矩D=[dij)]nxn，即dij=w(i,j)，若结点i到j无边相连

7、时，则去dij=∞。然后依次计算出矩阵D[2],D[3],…,D[n]。其中D[2]=D*D=(d[2]ij)nxn，d[2]ij=min{di1+d1j,di2+d2j,…,din+dnj}表示从vi出发两步可以到达vj的道路中距离最短者；D[k]=(d[k]ij)nxn，d[k]ij表示从vi出发k步可以到达vj的道路距离中最短路径。D[n]=D[n-1]*D=(d[n]ij)nxnS=DD[2]D[3]…D[n]=(Sij)nxnword范文.由定义可知d表示从结点i到j经过k边的路(在有

8、向图中即为有向路)中的长度最短者，而Sij为结点i到j的所有路中的长度最短者。2.最短路径问题在蔬菜批发市场中的应用某城市市政管理部门决定新建一个蔬菜批发市场，为周边的几个小区的菜市场集中供应新鲜蔬菜。由于蔬菜水果容易变质，小区菜市场的商贩必须在每天早晨把蔬菜从批发市场运送回店铺，这就要求批发市场的地址不能距离小区太远。该城市管理部门经过征求意见后，决定将批发市场建在其中的一个小区旁边，现在的问题是该将此批发市场建在那个小区才能使最远的小区距离该批发市场距离最短。2.1分析问题并建立模型已知该城