基于Floyd算法的道路指示牌解決方案

1、基于Floyd算法的道路指示牌解決方案緒論 中國擁有13億人口，960萬平方公里的國土面積，僅次于加拿大又略大于美國；中國公路通車?yán)锍踢_(dá)185萬公里，鐵路里程達(dá)7.43萬公里。在過去的20年里，我們在經(jīng)濟(jì)領(lǐng)域取得了巨大的成就，保持了強(qiáng)勁快速的增長態(tài)勢。在中國經(jīng)濟(jì)增長的帶動(dòng)下，中國公路客運(yùn)交通獲得了快速發(fā)展，并以每年78的速度持續(xù)增長。與此同時(shí)，中國汽車擁有量和駕車者也都有爆發(fā)性增長；而物流運(yùn)輸、集裝箱運(yùn)輸在過去的10年里增長了30。由此可以看出，汽車產(chǎn)業(yè)和交通運(yùn)輸在中國的迅猛增長。 為了滿足不斷增長的交通運(yùn)輸，高速公路系統(tǒng)的建設(shè)就迫在眉睫。隨著高速公路系統(tǒng)的不斷完善，指示牌的作用十分重要。指示

2、牌為用戶指明了前往各個(gè)城市的距離。選擇最短的路徑，方便用戶是指示牌的主要目的。 本文是基于Floyd算法，來找出設(shè)置合適的指示牌來指示用戶，從而使得用戶可以更加快速的到達(dá)目的地。第一章 問題模型 我們可以在每一個(gè)十字路口都設(shè)置指示牌，但這樣一種方式并不是最好。為了選擇哪些城市應(yīng)該在指示牌上列出，我們使用如下策略：如果在指示牌前鋒的十字路口上有一條路是到城市X的最短路，則城市X被標(biāo)上指示牌。我們假設(shè)在沒對十字路口之間只有一條最短路徑。 輸入： 輸入包括一個(gè)問題實(shí)例，描述了高速公路系統(tǒng)，接著是一組指示牌的位置。高速公路系統(tǒng)定義為一組十字路口和一組與十字路口相連的道路。第一行是是哪個(gè)正整數(shù)n、m、k

3、：n表示十字路口的數(shù)量，m表示連接各個(gè)十字路口之間道路的數(shù)量，k表示既是城市也是十字路口的數(shù)量。接下來m行，格式是i1、i2、d，表示十字路口i1和 i2直接有一條雙行道，其距離為d。接下來k行，格式是i、name，表示十字路口i是一個(gè)城市，其名字為name。在這之后的一行，有一個(gè)正整數(shù)s，表示應(yīng)防止在高速公路系統(tǒng)上的指示牌的數(shù)量。接下來的s行，格式是i1、i2、d，表示從i1到 i2應(yīng)放置一個(gè)指示牌，從i1開始的距離是d。對于所有的問題實(shí)例，名字的長短18個(gè)字符，5n30.所有的距離大于0，并精確到百分之一。 輸出： 每個(gè)指示牌的輸出格式如下： name1 d1 name2 d2 . nam

4、ei應(yīng)該左對齊，寬度為20；距離dj應(yīng)四舍五入到整數(shù)。沒對“namedistance”應(yīng)該按四舍五入后的距離排序；相同距離的依字幕順序輸出。指示牌輸出順序應(yīng)該與指示牌的輸入順序一致，每個(gè)指示牌之間有一個(gè)空行，你可以假設(shè)每個(gè)指示牌上至少列出一個(gè)城市。第二章 算法簡介 Floyd算法又稱為弗洛伊德算法，插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。該算法名稱以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名。1.核心思路 通過一個(gè)圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣。 從圖的帶權(quán)鄰接矩陣A=a(i,j) n×n開始，遞歸地進(jìn)行

5、n次更新，即由矩陣D(0)=A，按一個(gè)公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點(diǎn)到j(luò)號頂點(diǎn)的最短路徑長度，稱D(n)為圖的距離矩陣，同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣path來記錄兩點(diǎn)間的最短路徑。 采用的是(松弛技術(shù))，對在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時(shí)間復(fù)雜度為O(n3); 其狀態(tài)轉(zhuǎn)移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,j mapi,j表示i到j(luò)的最短距離 K是窮舉i,j的斷點(diǎn) mapn,n初值應(yīng)該為0，或者按照題目意思來做。 當(dāng)然，如

6、果這條路沒有通的話，還必須特殊處理，比如沒有mapi,k這條路。2.算法描述a) 初始化：Du,v=Au,vb) For k:=1 to n For i:=1 to n For j:=1 to n If Di,j>Di,k+Dk,j Then DI,j:=DI,k+Dk,j;c) 算法結(jié)束：D即為所有點(diǎn)對的最短路徑矩陣3.算法過程1.從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。2.對于每一對頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。 把圖用鄰接距陣G表示出來，如果從Vi到Vj有路

7、可達(dá)，則Gi,j=d，d表示該路的長度；否則Gi,j=無窮大。 定義一個(gè)距陣D用來記錄所插入點(diǎn)的信息，Di,j表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化Di,j=j。 把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來的距離，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值變小，則Di,j=k。 在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。 比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為V5,V3,V1，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。4.優(yōu)缺點(diǎn)分

8、析 Floyd算法適用于APSP(All Pairs Shortest Paths)，是一種動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。 優(yōu)點(diǎn)：容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡單 缺點(diǎn)：時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。第三章 算法分析1.樣例分析 該樣例有8個(gè)十字路口，17條道路，4個(gè)城市和3個(gè)指示牌。如圖。 輸出結(jié)果分別是三個(gè)指示牌上的城市列表。例如從路口3到路口2，在距離路口3為0.45英里處立一塊指示牌，表示到Bobtown還有7英里。2.數(shù)據(jù)結(jié)構(gòu) 使用鄰接矩陣存儲

9、高速公路系統(tǒng)圖： double graphMaxNMaxN; 對于樣例數(shù)據(jù)，數(shù)組graph的內(nèi)容如圖所示： 數(shù)組的下表與十字路口的編號一致。0123456700.007.128.345.335.360.000.000.0017.120.004.210.000.000.006.9910.2628.344.210.002.740.000.005.040.0035.330.002.740.004.127.725.710.0045.360.000.004.120.008.9410.290.0050.000.000.007.728.940.005.478.5560.006.995.045.7110.29

10、5.470.006.0170.0010.260.000.000.008.556.010.00 數(shù)組city表示城市： char cityMaxNMaxN; 對于樣例數(shù)據(jù)，數(shù)組city的內(nèi)容如圖所示：下標(biāo)0123城市AllentownBobtownCharlestownDownville 下標(biāo)是城市編號。 數(shù)組citylocation表示城市在十字路口的位置： int citylocationMaxN； 對于樣例數(shù)據(jù)，數(shù)組citylocation的內(nèi)容如圖所示：下標(biāo)01234567城市編號01-1-1-1-123下標(biāo)是十字路口編號，值為-1時(shí)表示該路口沒有城市。3.使用Floyd方法計(jì)算所有路口

11、之間的最短路徑 采用數(shù)組path存儲最短路徑： double pathMaxNMaxN； 對于樣例數(shù)據(jù)，數(shù)組path的內(nèi)容如下： 注意表中陰影部分的單元格，其數(shù)值沒有變化，表示這些路口之間沒有最短路徑。4.計(jì)算最短路徑經(jīng)過的十字路口 采用數(shù)組shortpath存儲最短路徑經(jīng)過的十字路口： int shortpathMaxNMaxN;0123456700.007.128.075.335.3613.0511.0417.0517.120.004.216.9511.0712.466.9910.2628.074.210.002.746.8610.465.0411.0535.336.952.740.004

12、.127.725.7111.7245.3611.076.864.120.008.949.8315.84513.0512.4610.467.728.940.005.478.55611.046.995.045.719.835.470.006.01717.0510.2611.0511.7215.848.556.010.00 對于樣例數(shù)據(jù)，數(shù)組shortpath的內(nèi)容如圖所示：012345670-11-1-1-1-13310-1-1-1-1-167231-1-1-1-166302-1-1-1-166403-1-1-1-133536-1-1-1-167631-1-1-1-1-17761-1-1-1-16

13、-1 當(dāng)路口沒有城市時(shí)，就不必計(jì)算，令其值為-1.表中的陰影單元與path表示對應(yīng)的，表示沒有最短路徑通往其他城市。單元（i，j）（i，j=0n-1）的值為k（k-1，j）時(shí)，表示從路口i到路口j有最短路徑，且經(jīng)過路口k。5.計(jì)算指示牌 有了shortpath表，計(jì)算只是牌列表就容易了。如從路口i到路口k，在shortpath表中，掃描i行，其值為k時(shí)，所對應(yīng)的列號j就是要列表顯示的城市。列表的數(shù)據(jù)結(jié)構(gòu)如下: struct sign int cityname，distance； sighlistMaxN； 輸出時(shí)要排序，采用標(biāo)準(zhǔn)函數(shù)qsort()，排序算法為函數(shù)cmp（）：首先按里程的大小升序

14、，在里程相等的情況下，按城市名稱的字幕排序。附：程序源代碼#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>const int MaxN = 31;const double Zero = 0.0001;/指示牌上要顯示的城市列表struct signint cityName, distance; signListMaxN;char cityMaxNMaxN; /城市名稱/比較函數(shù)int cmp(const void *a1,const void *b1

15、)sign *a = (struct sign*)a1;sign *b = (struct sign*)b1; /首先按里程的大小升序if (a->distance > b->distance) return 1; /在里程相等的情況下，按城市名稱的字幕順序排序else if (a->distance = b->distance) return strcmp(citya->cityName, cityb->cityName);else return -1;int main()double pathMaxNMaxN; /存儲最短路徑double grap

16、hMaxNMaxN; /存儲高速公路系統(tǒng)圖int shortPathMaxNMaxN; /存儲最短路徑經(jīng)過的十字路口int cityLocationMaxN; /存儲城市在十字路口的位置int cases; /測試?yán)龜?shù)scanf("%d", &cases);int iCase;for (iCase = 1; iCase <= cases; iCase+)int i, j, k;int a, b;double d;char nameMaxN;int n, m, cross; /路口數(shù)量，道路數(shù)量，城市數(shù)量scanf("%d %d %d", &

17、amp;n, &m, &cross);memset(graph, 0, sizeof(graph);memset(cityLocation, 255, sizeof(cityLocation);/構(gòu)造鄰接矩陣for (i = 1; i <= m; i+)scanf("%d %d %lf", &a, &b, &d);graphab = graphba = d;/讀取城市信息for (i = 0; i < cross; i+)scanf("%d", &a);cityLocationa = i;sca

18、nf("%signNum", name);strcpy(cityi, name);/使用Floyd方法計(jì)算所有路口之間的最短路徑memcpy(path, graph, sizeof(graph);for (k = 0; k < n; k+)for (i = 0; i < n; i+)if (pathik > Zero)for (j = 0; j < n; j+)if (pathkj > Zero && i != j)d = pathik+pathkj;if (pathij < Zero | pathij > d) p

19、athij = d;/對角線是路口自身，清除掉for (i = 0; i < n; i+) pathii = 0;/計(jì)算最短路徑經(jīng)過的十字路口memset(shortPath, 255, sizeof(shortPath);for (i = 0; i < n; i+)for (j = 0; j < n; j+)/該路口有城市才計(jì)算if (cityLocationj >= 0)for (k = 0; k < n; k+)if (graphik >= Zero && fabs(pathij-pathkj-graphik)<Zero)shortPathij = k; break;if (iCase != 1