圖論論文Floyd算法的應(yīng)用

1、題 目 Floyd算法在旅游線路制定問題中的應(yīng)用學 院 姓 名 學 號 2010 年 11 月摘 要隨著日益增長的精神文化需求，旅游已經(jīng)逐漸成為人們假期生活中不可缺少的一部分。但是旅游的高費用和經(jīng)濟條件還有時間的限制也制約著人們的旅行計劃。尤其是對于我們這種初到某城市的學生游客，旅行路線的制定就成為了一個重要的問題。如何在有限時間內(nèi)經(jīng)濟實惠地制定自己的旅行計劃需要我們用有效的數(shù)學手段來解決。通過對圖論這門課程的學習，發(fā)現(xiàn)各種最短路徑的算法都能夠很好的解決實際生活中的問題，例如Dijkstra算法、Floyd算法、Bellman-Ford算法等等。本文主要介紹了Floyd算法的原理，以重慶市周邊

2、旅游景點為背景，選取了幾個計劃之內(nèi)的旅游景點為假設(shè)模型，希望通過Floyd算法獲得任意兩景點之間的最短路徑來制定旅游路線，中間路過的景點也是我們計劃之內(nèi)的。關(guān)鍵詞：Floyd算法 最短路徑 假設(shè)模型 距離估算 最小權(quán)重緒 論在18世紀30年代。一個非常有趣的問題引起了歐洲數(shù)學家的濃厚興趣，這個問題要求遍歷普魯士的哥尼斯堡七橋中的每一座橋恰好一次后回到出發(fā)點。歐拉證明了這是不可能完成的。此后，歐拉發(fā)表了著名的論文依據(jù)幾何位置的解題方法，這是圖論領(lǐng)域的第一篇論文，標志著圖論的誕生。圖論的真正發(fā)展始于20世紀五六十年代之間。是一門既古老又年輕的學科，圖論極有趣味性，嚴格來講它是組合數(shù)學的一個重要分支

3、。雖然圖論只是研究點和線的學問。但其應(yīng)用領(lǐng)域十分廣闊。不僅局限于數(shù)學和計算機學科，還涵蓋了社會學、交通管理，電信領(lǐng)域等等?？偟膩碚f，圖論這門學科具有以下特點：圖論蘊含了豐富的思想，漂亮的圖形和巧妙的證明；涉及的問題多且廣泛，問題外表簡單樸素，本質(zhì)上卻十分復雜深刻；解決問題的方法千變?nèi)f化，非常靈活，常常是一種問題一種解法。由以上三個特點可以看出。圖論與其他的數(shù)學分支不同，它不像群論、拓撲等學科那樣有一套完整的理論體系和解決問題的系統(tǒng)方法。而且圖論所研究的內(nèi)容非常廣泛，例如圖的連通性、遍歷性。圖的計數(shù)。圖的著色、圖的極值問題。圖的可平面性等等。最短路問題是圖論應(yīng)用的基本問題，很多實際問題，如線路的

4、布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用等問題，都可以通過建立最短路問題模型來求解。最短路問題一般是在加權(quán)圖中討論，最短路徑不僅僅是指一般意義上的距離最短，諸如時間、費用都可以被引申為最短路徑，相應(yīng)的最短路徑問題就成了最快路徑問題、最低費用問題等。1 背景介紹重慶是中華人民共和國四個直轄市之一，地處中國西南。是中國重要的中心城市之一，歷史悠久，國務(wù)院公布的第二批國家歷史文化名城之一。因為重慶的地理環(huán)境，重慶多山多霧，故又有霧都、山城的別名。重慶也是旅游勝地，周邊大大小小的旅游景點數(shù)不勝數(shù)。例如大足石刻、釣魚城、豐都、小田溪巴王墓群、金佛山、歌樂山等等。對于我們這些初到重慶的學生游客來說，由于對當?shù)乩憝h(huán)

5、境并不熟悉，而且時間有限。我們希望在有限的十一或是五一假期內(nèi)，找到最短的最經(jīng)濟的旅游線路，進行一次重慶周邊旅行。所以，如何制定旅游線路就是一個很重要的問題。通過對圖論這門課程的學習，我們知道最短路徑也是圖論中的一個重要的應(yīng)用問題。其中涉及到的各種算法在日常生活中得到了廣泛的應(yīng)用。Floyd算法就是任意兩點間最短路徑的經(jīng)典算法。2 Floyd算法描述2.1 最短路徑問題在圖G中的每一條邊，可賦以一個實數(shù)，稱為的權(quán)，G連同它邊上的權(quán)稱為賦權(quán)圖，賦權(quán)圖經(jīng)常出現(xiàn)在圖論的應(yīng)用中。例如在友誼圖中，權(quán)可以表示友誼深度；在通信圖中，權(quán)可以表示各種通訊線路的建造或維修費用。若H是賦權(quán)圖的一個子圖，則H的權(quán)是指它

6、的各邊的權(quán)和。許多最優(yōu)化問題相當于要在一個賦權(quán)圖中找出某類具有最?。ɑ蜃畲螅?quán)的子圖，其中之一就是最短路問題：就是要在一個賦權(quán)圖的兩個指定頂點和之間找出一條具有最小權(quán)的路。最短路作為圖與網(wǎng)絡(luò)技術(shù)研究中的一個經(jīng)典問題一直在工程規(guī)劃、地理信息系統(tǒng)、通信和軍事運籌學等領(lǐng)域有著十分廣泛的應(yīng)用。頂點對之間的最短路徑是指：對于給定的有向網(wǎng)，要對G中任意一對頂點有序?qū)Γ页鯲到W的最短距離和W到V的最短距離。目前，關(guān)于最短路問題的研究已有較多結(jié)果，傳統(tǒng)的最短路算法主要有Floyd算法和Dijkstra算法等。其中，Dijkstra算法求解任意頂點對之間最短距離的方法是：輪流以每一個頂點為源點，重復執(zhí)行算法n

7、次，即可求得每一對頂點之間的最短路徑，總的時間復雜度為，F(xiàn)loyd提出了另外一個求圖中任意兩頂點之間最短路徑的算法，雖然其時間復雜度也是，但其算法的形式更簡單，易于理解和編程。2.2 Floyd算法描述對于圖G，如果表示i和j之間的可實現(xiàn)的距離，那么表示端i和j之間的最短距離當且僅當對于任意的i, j, k，有。該算法用矩陣形式來表示，并進行系統(tǒng)化的計算，通過迭代來消除不滿足上述定理的情況，對于n個端，一給定邊長的圖，順序計算各個的W陣和R陣，前者代表徑長，后者代表轉(zhuǎn)接路由。其步驟如下：置 其中 和 其中 ：已得和陣，求和陣中的元素如下 ：，重復；，終止。由上述步驟可見，是計算經(jīng)轉(zhuǎn)接時是否能縮

8、短經(jīng)常，如有縮短，更改并在R陣中記下轉(zhuǎn)接的端。最后算得和，就得到了最短徑長和轉(zhuǎn)接路由。3 Floyd算法用于解決旅行線路問題3.1 旅行線路模型假設(shè)初到重慶郵電大學，同學們對重慶這個歷史悠久且極具特色的中國中心城市充滿了好奇，在節(jié)假日的時候都計劃著去重慶市周邊的旅游景點進行短期旅行。由于我們對重慶市的地理環(huán)境消費水平等并不是特別了解，制定旅行線路就成為了一個很重要的問題，由于假期時間有限，我們希望能夠在備選目的地景點中，能夠找到任何兩個景點之間的最短路，且中途經(jīng)過的節(jié)點也是備選景點中的景點。于是選擇重慶周邊的各個景點為對象如圖3-1所示，我們可以選擇圖示的任何幾個景點來生成一個考察對象圖，圖中

9、粗線條所連接生成的圖為文章中考察的圖，命名為G。圖3-1 重慶市周邊旅游景點圖圖中選擇的備選景點分別為：大足石刻、釣魚城、豐都、小田溪巴王墓群、金佛山、歌樂山、重慶市中心。這七個景點依次編號為1-7，且如圖所示粗線表示連接端點的邊分別命名為-。于是我們生成了考察對象圖G，如圖3-2所示。通過考察各個景點之間的實際距離（公里數(shù)），-的公里數(shù)分別為：78.6km，293.2km，175.6km，176.1km，129.2km，17.9km，79.8km，236.9km，124.7km，20.2km。我們以最短距離20.2為基準作歸一化處理得到近似-的值分別為：4，14，9，9，6，1，4，12，6

10、，1。假設(shè)模型中，用這些歸一化的值分別代表各個邊的權(quán)值，構(gòu)成加權(quán)圖G如圖3-2所示。圖3-2 由七個景點生成的圖G3.2 用Floyd算法計算任意兩景點之間的最短路徑現(xiàn)在我們以上述生成的圖G為考察對象，根據(jù)算法流程，設(shè)W陣和R陣分別代表徑長和轉(zhuǎn)接路由。那么計算結(jié)果如下： 經(jīng)過7輪迭代，我們得到了最終的W和R陣，分別包含了徑長信息和路由信息。我們可以從和中找到任何兩個端點間的最短徑長和最短路由，對應(yīng)著我們所建立的旅行線路模型中的任何兩景點間的最短路徑長度和路線。例如我們要找從豐都到大足石刻的最短路徑以及路線長度，也就對應(yīng)著節(jié)點到的最短路徑和徑長，可以從中找到對應(yīng)的最小值為18，從中找到，就是要經(jīng)

11、轉(zhuǎn)接；再看，此時已經(jīng)到達目的節(jié)點，所以路由是，對應(yīng)模型中的景點為豐都經(jīng)釣魚城到大足石刻，總公里數(shù)為。綜上所述，我們可以任選幾個備選景點，然后在其中通過該算法來獲取最短旅行路線。3.3 Floyd算法的編程實現(xiàn)下面給出了一個Floyd算法的通用程序：Void floyd(graph g,path *p)int i,j,k,n,x,y,z; p->n=n=n=g.n p->d=(int*)malloc(n*n*sizeof(int); p->v=(int*)malloc(n*n*sizeof(int); for(i=0;i<n;i+) for(j=0;j<n;j+)

12、*(p->d+i*n+j)=*(g.a+i*n+j); *(p->v+i*n+j)=j+1; for(k=0;k<n;k+) for(i=0;i<n;i+) for(j=0;j<n;j+) x=*(p->d+i*n+k);y=*(p->d+k*n+j); z=*(p->d+i*n+j); if(x!=0&&y!=0&&(z=0|x+y<z) *(p->d+i*n+j)x+y; *(p->v+i*n+j)=*(p->v+i*n+k); 四 結(jié)論與心得最短路徑算法是計算機理論的重難點，可以將最短路徑的算法轉(zhuǎn)化為求花費最少和最節(jié)省時間等方面的算法，從而對最短路徑算法提出一些應(yīng)用，以達到更多要求，使在交通旅游等方面的成本減到最低，不斷拓展Floyd算法的功能。圖論這門課是一門應(yīng)用十分廣泛其內(nèi)容豐富的數(shù)學分支，在物理、化學、生物、計算機科學、工程技術(shù)和經(jīng)濟管理等各個領(lǐng)域都可以找到圖論的足跡。它有極富趣味性，雖然圖論只是研究點和線的學問，但其應(yīng)用領(lǐng)域十分寬廣，不僅局限于數(shù)學和