国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構(gòu)

手機站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時隨地免費學(xué)

千鋒教育

掃一掃進入千鋒手機站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時隨地免費學(xué)習(xí)課程

當(dāng)前位置:首頁  >  技術(shù)干貨  > floyd算法為什么要用鄰接矩陣實現(xiàn)而不用鄰接表?

floyd算法為什么要用鄰接矩陣實現(xiàn)而不用鄰接表?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 05:00:46 1696971646

一、floyd算法為什么要用鄰接矩陣實現(xiàn)而不用鄰接表

floyd算法要用鄰接矩陣實現(xiàn)而不用鄰接表是因為需要O(1)時間查詢?nèi)我鈨蓚€頂點的邊權(quán)值,在這一句中:d(i, j) = d(i, k) + d(k, j)。Floyd 算法是一個基于「貪心」、「動態(tài)規(guī)劃」求一個圖中 所有點到所有點 最短路徑的算法,時間復(fù)雜度 O(n3)。

1)算法思想原理:

Floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話,首先我們的目標(biāo)是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題,我們需要為這個目標(biāo)重新做一個詮釋(這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在)

從任意節(jié)點i到任意節(jié)點j的最短路徑不外乎2種可能,1是直接從i到j(luò),2是從i經(jīng)過若干個節(jié)點k到j(luò)。所以,我們假設(shè)Dis(i,j)為節(jié)點u到節(jié)點v的最短路徑的距離,對于每一個節(jié)點k,我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短,我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j),這樣一來,當(dāng)我們遍歷完所有節(jié)點k,Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。

2)算法描述:

a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán),如果兩點之間沒有邊相連,則權(quán)為無窮大。   

b.對于每一對頂點 u 和 v,看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。

3)Floyd算法過程矩陣的計算—-十字交叉法

方法:兩條線,從左上角開始計算一直到右下角。

給出矩陣,其中矩陣A是鄰接矩陣,而矩陣Path記錄u,v兩點之間最短路徑所必須經(jīng)過的點。

延伸閱讀:

二、滾動數(shù)組

滾動數(shù)組是一種動態(tài)規(guī)劃中常見的降維優(yōu)化的方式,應(yīng)用廣泛(背包dp等),可以極大的減少空間復(fù)雜度。在我們求出的狀態(tài)轉(zhuǎn)移方程中,我們在更新f[k]層狀態(tài)的時候,用到f[k-1]層的值,f[k-2] f[k-3]層的值就直接廢棄了。所以我們大可讓名列前茅層的大小從n變成2,再進一步,我們在f[k]層更新f[k][i][j]的時候,f[k-1][i][k] 和 f[k-1][k][j] 我們?nèi)绻鼙WC,在更新k層另外一組路徑m->n的時候,不受前面更新過的f[k][i][j]的影響,就可以把名列前茅維度去掉了。我們現(xiàn)在去掉名列前茅個維度,寫成我們在代碼中的那樣,就是f[i][j] 依賴 f[i][k] + f[k][j] 我們在更新f[m][n]的時候,用到了f[m][k] + f[k][n] 假設(shè)f[i][j]的更新影響到了f[m][k] 或者 f[k][m] 即 {m=i,k=j} 或者 {k=i,n=j} 這時候有兩種情況,j和k是同一個點,或者i和k是同一個點,那么 f[i][j] = f[i][j] + f[j][j],或者f[i][j] = f[i][i]+f[i][j] 這時候,我們所謂的“前面更新的點對”還是這兩個點本來的路徑,也就是說,少數(shù)兩種在某一層先更新的點,影響到后更新的點的情況,是完全合理的,所以說,我們即時把名列前茅維去掉,也滿足無后效性原則。因此可以用滾動數(shù)組優(yōu)化。優(yōu)化之后的狀態(tài)轉(zhuǎn)移方程即為:f[i][j] = min(f[i][j],f[i][k]+f[k][j])。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學(xué)習(xí)老師24小時內(nèi)將與您1V1溝通
免費領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
計算機網(wǎng)絡(luò)管理軟件有哪些好用?

1、Nagios CoreNagios Core在全球范圍內(nèi)用于幫助監(jiān)控網(wǎng)絡(luò)和跟蹤各種基礎(chǔ)設(shè)施。它的主動監(jiān)控功能可以檢測它負責(zé)監(jiān)控的服務(wù)器上的網(wǎng)絡(luò)設(shè)備、服務(wù)...詳情>>

2023-10-11 06:33:55
oa系統(tǒng)怎么注冊?

一、選擇合適的OA系統(tǒng)首先,需要選擇一款適合自己公司的OA系統(tǒng)。市面上有很多OA系統(tǒng),如用友、金蝶等,不同的OA系統(tǒng)有不同的功能和價格。在選擇...詳情>>

2023-10-11 06:32:35
大整數(shù)類型和一般的整數(shù)類型相比各有什么優(yōu)劣?

一、大整數(shù)類型和一般的整數(shù)類型相比大整數(shù)類型和一般的整數(shù)類型相比優(yōu)點是不會溢出,能表示任意長度的數(shù)字做各種精度的運算。缺點是沒有直接的...詳情>>

2023-10-11 06:22:59
功能安全開發(fā)與ASPICE和CMMI之間有什么樣的聯(lián)系?

一、功能安全開發(fā)與ASPICE和CMMI之間的聯(lián)系CMMI是產(chǎn)品和系統(tǒng)開發(fā)的通用模型,ASPICE是針對車這個垂直領(lǐng)域,(軟件)產(chǎn)品和系統(tǒng)開發(fā)的標(biāo)準(zhǔn)。ASPI...詳情>>

2023-10-11 05:59:32
在C語言下數(shù)組array與鏈表linklist各自的優(yōu)點和缺陷是什么?

一、在C語言下數(shù)組array與鏈表linklist各自的優(yōu)點和缺陷數(shù)組可以通過下標(biāo)訪問,隨機訪問效率高,鏈表需要通過指針遍歷,訪問效率低。數(shù)組在分配...詳情>>

2023-10-11 05:43:25