高中信息競(jìng)賽數(shù)據(jù)結(jié)構(gòu)—最短路徑學(xué)習(xí)資料

1、高中信息競(jìng)賽數(shù)據(jù)結(jié)構(gòu)最短路徑EvvEvvwdistiiii),(),(0003u任意一對(duì)頂點(diǎn)之間的最短路徑任意一對(duì)頂點(diǎn)之間的最短路徑u這個(gè)問(wèn)題的解法有兩種：這個(gè)問(wèn)題的解法有兩種：u一一種算法：分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共調(diào)用一一種算法：分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共調(diào)用n次次Dijkstra算法算法,這種算法的時(shí)間復(fù)雜度為這種算法的時(shí)間復(fù)雜度為O(n3)；u另一種算法：另一種算法：Floyed算法算法,它的思路簡(jiǎn)單它的思路簡(jiǎn)單,但時(shí)間復(fù)雜度但時(shí)間復(fù)雜度仍然為仍然為O(n3),下面介紹下面介紹Floyed算法。算法。數(shù)據(jù)定義說(shuō)明：數(shù)據(jù)定義說(shuō)明： map;/存儲(chǔ)圖存儲(chǔ)圖 dist;/disi,j=k

2、,i和和j之間最短路徑長(zhǎng)度為之間最短路徑長(zhǎng)度為K下面給出下面給出Floyed算法算法框架算法算法框架:從文件中讀入圖的鄰接矩陣從文件中讀入圖的鄰接矩陣map； for(i=1;i=n;i+) for(j=1;jmapij);/讀入數(shù)據(jù)讀入數(shù)據(jù)數(shù)組初始化；數(shù)組初始化； for(i=1;i=n;i+) for(j=1;j=n;j+) if(mapij=0)mapij=maxint; /把沒(méi)有通路的點(diǎn)把沒(méi)有通路的點(diǎn)(mapI,j=0)間的路徑置為最大間的路徑置為最大maxintFloyed算法框架；算法框架；void floyd() int i,j,k; for(i=1;i=n;i+) /復(fù)抄數(shù)組復(fù)

3、抄數(shù)組 for(j=1;j=n;j+) distij=mapij; for(k=1;k=n;k+) /枚舉中間點(diǎn)枚舉中間點(diǎn) for(i=1;i=n;i+) /枚舉起點(diǎn)枚舉起點(diǎn) for(j=1;j=n;j+) /枚舉終點(diǎn)枚舉終點(diǎn) if(distik!=maxint)&(distkj!=maxint) &(distik+distkjn; for(i=1;ixiyi; for(i=1;i=n;i+) for(j=1;jc; if(c=1)fij=dist(i,j); else fij=maxint; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(fikmaxint-1&fkjfik+fkj) fij=fik+fkj; memset(m,0,sizeof(m); for(i=1;i=n;i+) for(j=1;j=n;j+) if(fijmaxint-1&mifij)mi=fij; minx=1e20; for(i=1;i=n;i+) for(j=1;jmaxint-1) temp=dist(i,j); if(minxmi+mj+temp)minx=mi+mj+temp; r=0; for(i=1;iminx)minx=mi; printf(%.6lf,minx); 此課件下載可自行編輯