圖論最短路徑選址問題

1、姓 名： 學(xué) 號： 專 業(yè)： 圖論的實際應(yīng)用蔬菜批發(fā)市場選址問題摘要：在現(xiàn)實生活和生產(chǎn)實踐中，有許多管理、組織與計劃中的優(yōu)化問題，都可借助圖論知識得以解決，而最短路問題是利用圖論解決的一個典型的實際問題。圖論中最典型的兩種求最短路徑的算法分別為Dijkstra算法和Floyd算法，其中Floyd算法廣泛應(yīng)用于求任意兩點間的最短路徑。本文介紹了利于Floyd算法來解決城市蔬菜批發(fā)市場選址的問題。關(guān)鍵詞：最短路；Floyd算法；選址問題 0引言對于許多地理問題，當(dāng)它們被抽象為圖論意義下的網(wǎng)絡(luò)圖時，問題的核心就變成了網(wǎng)絡(luò)圖上的優(yōu)化計算問題。其中，最為常見的是關(guān)于路徑和頂點的優(yōu)選計算問題5。在路徑的優(yōu)

2、選計算問題中，最常見的是最短路徑問題，最短路徑可能是給定兩點間的最短路徑，也可能是任意各點間的最短路徑。而在頂點的優(yōu)選計算問題中，最為常見的是選址問題，所謂選址問題就是在某一地理區(qū)域構(gòu)成的網(wǎng)絡(luò)中選擇一個頂點，建立服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的各個點提供服務(wù)，使得服務(wù)效率最高3。選址問題，在規(guī)劃建設(shè)中經(jīng)常可以碰到，這里所謂的服務(wù)設(shè)施，可以是某些公共服務(wù)設(shè)施，如醫(yī)院，消防站，物流中心等。也可以是生產(chǎn)服務(wù)設(shè)施，如倉庫，轉(zhuǎn)運站等等?？梢哉J(rèn)為，選址問題，就是把服務(wù)設(shè)施與服務(wù)對象，反映與統(tǒng)一的網(wǎng)絡(luò)中，便于對問題進(jìn)行研究4。盡管對選址的目標(biāo)、要求有不同的評判標(biāo)準(zhǔn)，但是要求服務(wù)對象與服務(wù)設(shè)施之間易于溝通、易于達(dá)到，這

3、是一個最基本的要求。1 最短路徑問題 最短路徑問題是圖論研究的一個經(jīng)典算法問題，其目的是求出給定兩點之間的長最短的路徑，這里所說的長具有廣泛意義，即可指普通意義的距離，也可是時間或費用等2。因此，最短路徑問題通?？梢詺w納為三類：(1)距離意義上的最短路徑，即求兩點間距離最短的路徑；(2)經(jīng)濟(jì)意義上的最短路徑，即為兩點間的費用最少的路徑；(3)時間意義上的最短路徑，即選擇兩點間最節(jié)省時間的路徑。以上三類問題，都可以抽象為同一類問題，即帶權(quán)圖上的最短路徑問題。不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值，權(quán)值既可以代表“純距離”，又可以代表“經(jīng)濟(jì)距離”，還可以代表“時間距離”。1.1 Dijks

4、tra算法Dijkstra算法是一種求解最短路徑方法。它是一個按路徑長度遞增的順序產(chǎn)生最短路徑的算法，其基本思想是：設(shè)圖中所有頂點集合為V，另設(shè)置兩個頂點集合S和T=V- S，集合S中存放已找到最短路徑的頂點，集合T存放當(dāng)前還未找到最短路徑的頂點。初始狀態(tài)時，集合S中只包含源點V1，然后不斷從集合T中選取到頂點V1 的路徑長度最短頂點Vi 加入到集合S中，集合S每加入一個新的頂點Vi，都要修改頂點V1到集合T中剩余頂點的最短路徑長度值，此過程不斷重復(fù)，直到集合T中的頂點全部加入到S中為止。這樣，就可以求出一點到其它的任一頂點的最短路徑。Dijkstra算法簡單易懂，在求給定兩點間的最短距離時效

5、率很高，但是其只能求圖中一個特定結(jié)點到其他各個結(jié)點的最短路1。當(dāng)需要求出圖中任意兩頂點的最短路徑時，就需要以圖中的每個頂點為起點，依次求出到另外頂點的最短路徑，在頂點數(shù)目比較多的情況下，其效率將非常低下。1.2 Floyd算法Floyd算法為另外一種求最短路徑的算法。在某些問題中，需要求出圖中任意兩頂點之間的最短路徑，這時，F(xiàn)loyd算法將比Dijkstra算法具有明顯優(yōu)勢。Floyd算法借助于權(quán)矩陣的運算直接可以求出任意兩點之間的最短路徑2。Floyd算法的實現(xiàn)思路為：首先定義賦權(quán)圖的邊權(quán)矩D =dij)n x n，即dij=w(i,j)，若結(jié)點i到j(luò)無邊相連時，則去dij=。然后依次計算出

6、矩陣D2,D3,Dn。其中D2=D*D=(d2ij)n x n，d2ij=mindi1+d1j,di2+d2j,din+dnj表示從vi出發(fā)兩步可以到達(dá)vj的道路中距離最短者；Dk=(dkij)n x n，dkij表示從vi出發(fā)k步可以到達(dá)vj的道路距離中最短路徑。 Dn = Dn-1*D = (dnij)n x n S = DD2D3Dn = (Sij)n x n由定義可知d表示從結(jié)點i到j(luò)經(jīng)過k邊的路(在有向圖中即為有向路)中的長度最短者，而Sij為結(jié)點i到j(luò)的所有路中的長度最短者。2.最短路徑問題在蔬菜批發(fā)市場中的應(yīng)用河南某城市市政管理部門決定新建一個蔬菜批發(fā)市場，為周邊的幾個小區(qū)的菜市

7、場集中供應(yīng)新鮮蔬菜。由于蔬菜水果容易變質(zhì)，小區(qū)菜市場的商販必須在每天早晨把蔬菜從批發(fā)市場運送回店鋪，這就要求批發(fā)市場的地址不能距離小區(qū)太遠(yuǎn)。該城市管理部門經(jīng)過征求意見后，決定將批發(fā)市場建在其中的一個小區(qū)旁邊，現(xiàn)在的問題是該將此批發(fā)市場建在那個小區(qū)才能使最遠(yuǎn)的小區(qū)距離該批發(fā)市場距離最短。2.1 分析問題并建立模型 已知該城市的小區(qū)位置及相互連通道路分布示意圖如圖1所示，其中結(jié)點v1，v2，v3，v4，v5，v6，v7表示七個小區(qū)，結(jié)點間的數(shù)字表示小區(qū)間的距離。V1V2V6V3V5V7V4306020151518253020圖1 小區(qū)位置分布示意圖由上面的小區(qū)位置及道路分布圖可知，若找一個合適的小

8、區(qū)來建造批發(fā)市場，使該小區(qū)到其它小區(qū)的最遠(yuǎn)距離最短，即求無向簡單圖圖1中的一點，使該點到其它點的最大值為最小。為此，我們可以使用Floyd算法來求解問題。首先根據(jù)圖1畫出對應(yīng)的權(quán)矩陣D： 30 30 20 15 20 20 60 25 D = 20 30 18 7 3 15 25 18 15 15 2.2 Floyd算法求各點間最短路徑 通過7階加權(quán)簡單圖的權(quán)矩陣D，分別算出矩陣D2，D3，D4，D5，D6，D7，然后求出最短路矩陣S，S如下：則可得出矩陣S中v1，v2，v3，v4，v5，v6，v7結(jié)點到其它個結(jié)點的最長距離分別為93，63，50，63，93，48，63，即v6結(jié)點到其它結(jié)點有

9、最短路徑。 由以上結(jié)論知，將蔬菜批發(fā)市場應(yīng)該建在小區(qū)v6處才最為合理，使得最遠(yuǎn)的小區(qū)菜市場距批發(fā)市場的距離最短。3.編程實現(xiàn) 以下為使用C+語言實現(xiàn)的Floyd算法的核心代碼：#include<stdio.h>#define MaxInt 10000/最大數(shù) const int MaxNumEdges=50; const int MaxNumVertices=10; /最大頂點數(shù) class Graph private: int vNum;/當(dāng)前頂點數(shù) int eNum;/當(dāng)前邊數(shù) int VertexMaxNumVertices;/頂點數(shù)組 int EdgeMaxNumVerti

10、cesMaxNumVertices;/邊數(shù)組 bool GetVertexPos(const int &vertex,int &i);/給出頂點vertex在圖中的位置 public: Graph(const int sz= MaxNumEdges);/構(gòu)造函數(shù) bool FindVertex(const int &vertex); bool InsertVertex(const int & vertex);/插入一個頂點vertex bool InsertEdge(const int v1,const int v2,const int weight);/插入一

11、條邊(v1,v2),該邊上的權(quán)值為weight void Hospital();/選址函數(shù); Graph:Graph(const int sz): vNum(0), eNum(0)/構(gòu)造函數(shù) int n,e; int name,tail,head; int weight; for(int i=0;i<sz;i+) for(int j=0;j<sz;j+) if(i=j) Edgeij=0;/頂點到自身權(quán)值為0 else Edgeij=10000;/鄰接矩陣初始化為最大值 printf("請輸入頂點數(shù),注意本程序最多為10個!n"); scanf("%d

12、",&n); printf("請依次輸入頂點名稱:n"); for(int r=0;r<n;r+)/依次輸入頂點，插入圖中 scanf("%d",&name); InsertVertex(name); vNum+; printf("請輸入邊數(shù):n"); scanf("%d",&e); printf("以下輸入邊信息:n"); for(int k=0;k<e;k+) printf("請輸入第%d邊頭頂點:n",k+1); scanf

13、("%d",&head); printf("請輸入該邊尾頂點：n"); scanf("%d",&tail); printf("請輸入該邊權(quán)值：n"); scanf("%d",&weight); if(!InsertEdge(head,tail,weight) printf("不存在該邊，請重輸！n"); continue; bool Graph:FindVertex(const int& vertex)/給出頂點vertex在圖中的位置 for

14、 (int i = 0; i < vNum; i+) if (vertex = Vertexi) return true; return false; bool Graph: GetVertexPos(const int &vertex,int &i)/給出頂點vertex在圖中的位置 for (i = 0; i < vNum; i+) if (vertex = Vertexi) return true; return false; bool Graph:InsertVertex(const int & vertex)/插入一個頂點vertex if (Fi

15、ndVertex(vertex) return false; VertexvNum = vertex; return true; bool Graph:InsertEdge(const int v1,const int v2,const int weight)/插入一條邊(v1,v2),該邊上的權(quán)值為weight int k=0,j=0; if(GetVertexPos(v1,k) && GetVertexPos(v2,j) Edgekj=weight; eNum+; Edgejk=weight; eNum+; return true; else return false; v

16、oid Graph:Hospital() /在以鄰接帶權(quán)矩陣表示的n個小區(qū)中，求批發(fā)市場建在何處，使離市場距離最遠(yuǎn)的小區(qū)到達(dá)市場的路徑最短。 int k,i,j,s; for (k=0;k<vNum;k+) /求任意兩頂點間的最短路徑 for (i=0;i<vNum;i+) for (j=0;j<vNum;j+) if (Edgeik+Edgekj<Edgeij) Edgeij=Edgeik+Edgekj; int m=MaxInt; /設(shè)定m為機(jī)器內(nèi)最大整數(shù)。 printf("*n"); /以下為求各小區(qū)離批發(fā)市場最近的選址 int min=Max

17、Int ; /設(shè)定機(jī)器最大數(shù)作小區(qū)間距離之和的初值。 k=0; /k設(shè)小區(qū)位置。 for (j=0;j<vNum;j+) m=0 ; for (i=0;i<vNum;i+) m=m+Edgeij; /頂點到其它頂點最短距離的距離之和 if (min>m) min=m;k=j; /取頂點間的距離之和的最小值。 /for printf("各小區(qū)離批發(fā)市場最近的選址,要建批發(fā)市場的小區(qū)為:%dn",k+1); /輸出要建批發(fā)市場的小區(qū)編號 for(j=0;j<vNum;j+) if(j!=k) printf("該小區(qū)離%d小區(qū)最短距離為:%dn",j+1,Edgekj);/算法結(jié)束int main() Graph Town(MaxNumVertices); Town.Hospital(); return 0;運行程序，并將2.1中的加權(quán)矩陣D的數(shù)值輸入程序，得到的程序運行的結(jié)果如圖2所示：25圖2 程序運行結(jié)果圖 對圖2中結(jié)果分析知，將批發(fā)市場建在V6小區(qū)，使得到其它6個小區(qū)的最長距離為48。結(jié)果和2.2中的矩陣S的計算結(jié)果相同。4. 總結(jié) 通過利用學(xué)習(xí)到的Floyd算法解決了一個城市蔬菜批發(fā)市場的選址問題，我認(rèn)識到最短路徑問題在現(xiàn)實生活中的巨大作用