图论最短路径选址问题

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

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

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

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

4、的路径。以上三类问题，都可以抽象为同一类问题，即带权图上的最短路径问题。不同意义下的距离都可以被抽象为网络图中边的权值，权值既可以代表“纯距离〞，又可以代表“经济距离〞，还可以代表“时间距离〞。1.1Dijkstra算法Dijkstra算法是一种求解最短路径方法。它是一个按路径长度递增的顺序产生最短路径的算法，其根本思想是：设图中所有顶点集合为V，另设置两个顶点集合S和T=V-..word.zl...S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点V1，然后不断从集合T中选取到顶点V1的路径

5、长度最短顶点Vi参加到集合S中，集合S每参加一个新的顶点Vi，都要修改顶点V1到集合T中剩余顶点的最短路径长度值，此过程不断重复，直到集合T中的顶点全部参加到S中为止。这样，就可以求出一点到其它的任一顶点的最短路径。Dijkstra算法简单易懂，在求给定两点间的最短距离时效率很高，但是其只能求图中一个特定结点到其他各个结点的最短路[1]。当需要求出图中任意两顶点的最短路径时，就需要以图中的每个顶点为起点，依次求出到另外顶点的最短路径，在顶点数目比拟多的情况下，其效率将非常低下。1.2Floyd算法Floyd算法为另外一种求最短路径的算法。在某些问题

6、中，需要求出图中任意两顶点之间的最短路径，这时，Floyd算法将比Dijkstra算法具有明显优势。Floyd算法借助于权矩阵的运算直接可以求出任意两点之间的最短路径[2]。Floyd算法的实现思路为：首先定义赋权图的边权矩D=[dij)]nxn，即dij=w(i,j)，假设结点i到j无边相连时，那么去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[

7、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)nxn由定义可知d表示从结点i到j经过k边的路(在有向图中即为有向路)中的长度最短者，而Sij为结点i到j的所有路中的长度最短者。2.最短路径问题在蔬菜批发市场中的应用某城市市政管理部门决定新建一个蔬菜批发市场，为周边的几个小区的菜市场集中供给新鲜蔬菜。由于蔬菜水果容易变质，小区菜市场的商贩必须在每天早晨把蔬菜从批发市场运送回店铺，这就要求批发市场的地址不能距离小区太远。该城

8、市管理部门经过征求意见后，决定将批发市场建在其中的一个小区旁边，现在的问题是该将此批发市场建在那个小区才能使最远的小区距离