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

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

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

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

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

6、的各邊的權和。許多最優化問題相當于要在一個賦權圖中找出某類具有最小（或最大）權的子圖，其中之一就是最短路問題：就是要在一個賦權圖的兩個指定頂點和之間找出一條具有最小權的路。最短路作為圖與網絡技術研究中的一個經典問題一直在工程規劃、地理信息系統、通信和軍事運籌學等領域有著十分廣泛的應用。頂點對之間的最短路徑是指：對于給定的有向網，要對G中任意一對頂點有序對，找出V到W的最短距離和W到V的最短距離。目前，關于最短路問題的研究已有較多結果，傳統的最短路算法主要有Floyd算法和Dijkstra算法等。其中，Dijkstra算法求解任意頂點對之間最短距離的方法是：輪流以每一個頂點為源點，重復執行算法n

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

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

9、粗線條所連接生成的圖為文章中考察的圖，命名為G。圖3-1 重慶市周邊旅游景點圖圖中選擇的備選景點分別為：大足石刻、釣魚城、豐都、小田溪巴王墓群、金佛山、歌樂山、重慶市中心。這七個景點依次編號為1-7，且如圖所示粗線表示連接端點的邊分別命名為-。于是我們生成了考察對象圖G，如圖3-2所示。通過考察各個景點之間的實際距離（公里數），-的公里數分別為：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。假設模型中，用這些歸一化的值分別代表各個邊的權值，構成加權圖G如圖3-2所示。圖3-2 由七個景點生成的圖G3.2 用Floyd算法計算任意兩景點之間的最短路徑現在我們以上述生成的圖G為考察對象，根據算法流程，設W陣和R陣分別代表徑長和轉接路由。那么計算結果如下： 經過7輪迭代，我們得到了最終的W和R陣，分別包含了徑長信息和路由信息。我們可以從和中找到任何兩個端點間的最短徑長和最短路由，對應著我們所建立的旅行線路模型中的任何兩景點間的最短路徑長度和路線。例如我們要找從豐都到大足石刻的最短路徑以及路線長度，也就對應著節點到的最短路徑和徑長，可以從中找到對應的最小值為18，從中找到，就是要經

11、轉接；再看，此時已經到達目的節點，所以路由是，對應模型中的景點為豐都經釣魚城到大足石刻，總公里數為。綜上所述，我們可以任選幾個備選景點，然后在其中通過該算法來獲取最短旅行路線。3.3 Floyd算法的編程實現下面給出了一個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); 四 結論與心得最短路徑算法是計算機理論的重難點，可以將最短路徑的算法轉化為求花費最少和最節省時間等方面的算法，從而對最短路徑算法提出一些應用，以達到更多要求，使在交通旅游等方面的成本減到最低，不斷拓展Floyd算法的功能。圖論這門課是一門應用十分廣泛其內容豐富的數學分支，在物理、化學、生物、計算機科學、工程技術和經濟管理等各個領域都可以找到圖論的足跡。它有極富趣味性，雖然圖論只是研究點和線的學問，但其應用領域十分寬廣，不僅局限于數學和