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

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

手機(jī)站
千鋒教育

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

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

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

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

當(dāng)前位置:首頁  >  技術(shù)干貨  > 負(fù)權(quán)形成環(huán)路的圖為什么不能用弗洛伊德算法求任意兩點之間的最短路徑?

負(fù)權(quán)形成環(huán)路的圖為什么不能用弗洛伊德算法求任意兩點之間的最短路徑?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 04:46:08 1696970768

一、負(fù)權(quán)形成環(huán)路的圖為什么不能用弗洛伊德算法求任意兩點之間的最短路徑

負(fù)權(quán)形成環(huán)路的圖,任意兩點間可能沒有最短路徑。例如負(fù)權(quán)環(huán)C,點A,B是C上的點,A可以在C中轉(zhuǎn)上任意圈后再沿C到B,這條路徑權(quán)值可以任意小。而Floyd算法可以給出網(wǎng)絡(luò)中任意兩個節(jié)點之間的最短路徑。

Floyd算法的基本思想

從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能:

1是直接從A到B;2是從A經(jīng)過若干個節(jié)點到B。

所以,我們假設(shè)dist(AB)為節(jié)點A到節(jié)點B的最短路徑的距離,對于每一個節(jié)點K,我們檢查dist(AK) + dist(KB) < dist(AB)是否成立,如果成立,證明從A到K再到B的路徑比A直接到B的路徑短,我們便設(shè)置 dist(AB) = dist(AK) + dist(KB),這樣一來,當(dāng)我們遍歷完所有節(jié)點K,dist(AB)中記錄的便是A到B的最短路徑的距離。

Floyd算法與Dijkstra算法的不同

Floyd算法是求任意兩點之間的距離,是多源最短路,而Dijkstra(迪杰斯特拉)算法是求一個頂點到其他所有頂點的最短路徑,是單源最短路。

Floyd算法屬于動態(tài)規(guī)劃,我們在寫核心代碼時候就是相當(dāng)于推dp狀態(tài)方程,Dijkstra(迪杰斯特拉)算法屬于貪心算法。

Dijkstra(迪杰斯特拉)算法時間復(fù)雜度一般是o(n2),Floyd算法時間復(fù)雜度是o(n3),Dijkstra(迪杰斯特拉)算法比Floyd算法塊。

Floyd算法可以算帶負(fù)權(quán)的,而Dijkstra(迪杰斯特拉)算法是不可以算帶負(fù)權(quán)的。并且Floyd算法不能算負(fù)權(quán)回路。

延伸閱讀:

二、最短路徑問題(SPP)

最短路徑問題(Shortestpath problem)是圖論研究中的一個經(jīng)典算法問題,旨在尋找圖(由結(jié)點和路徑組成的)中兩結(jié)點之間的最短路徑。

最短路徑問題根據(jù)初始條件的不同,可分為五種情況:

1)最短路徑問題:旨在尋找圖中兩點之間的最短路徑;

2)確定起點的最短路徑問題:即已知起點,求最短路徑的問題;

3)確定終點的最短路徑問題:與確定起點的問題相反,該問題是已知終點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題;

4)確定起點終點的最短路徑問題,即已知起點和終點,求兩點之間的最短路徑;

5):全局最短路徑問題:求圖中任意兩點間的最短路徑。也可以合并為一種情況——全局最短路徑問題,只要求出全局最短路徑,那其余四種情況也已經(jīng)包含在內(nèi)了。

而計算最短路徑的常用算法有迪杰斯特拉算法、貝爾曼-福特算法、弗洛伊德算法等,下面小競將為大家一一介紹其基本概念、優(yōu)缺點、適用情況和案例分析。

迪杰斯特拉(Dijkstra)算法:用于解決從起點到其他各結(jié)點的最短路徑,解決的是有向圖中最短路徑問題。其主要特點是以初始點為中心向外層層擴(kuò)展,直到擴(kuò)展到終點為止,但也有圖中不能存在負(fù)權(quán)值的邊的限制。

貝爾曼-福特(Bellman–Ford)算法:用于解決從起點到其他各節(jié)點的最短距離。與迪杰斯特拉算法不同的是,貝爾曼-福特算法可支持存在負(fù)權(quán)重的情況,即打破了圖中不能存在負(fù)權(quán)值的邊的限制,其邊的權(quán)值可以為負(fù)數(shù)、實現(xiàn)簡單,但也存在時間復(fù)雜度過高的缺點。可對原始算法進(jìn)行若干優(yōu)化,提高效率。貝爾曼-福特算法可用于解決以下問題:

1)從A出發(fā)是否存在到達(dá)各個節(jié)點的路徑(有計算出值當(dāng)然就可以到達(dá));

2)從A出發(fā)到達(dá)各個節(jié)點最短路徑(時間最少、或者路徑最少等);

3)圖中是否存在負(fù)環(huán)路(權(quán)重之和為負(fù)數(shù))。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學(xué)習(xí)老師24小時內(nèi)將與您1V1溝通
免費(fèi)領(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
計算機(jī)網(wǎng)絡(luò)管理軟件有哪些好用?

1、Nagios CoreNagios Core在全球范圍內(nèi)用于幫助監(jiān)控網(wǎng)絡(luò)和跟蹤各種基礎(chǔ)設(shè)施。它的主動監(jiān)控功能可以檢測它負(fù)責(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ù)字做各種精度的運(yùn)算。缺點是沒有直接的...詳情>>

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)訪問,隨機(jī)訪問效率高,鏈表需要通過指針遍歷,訪問效率低。數(shù)組在分配...詳情>>

2023-10-11 05:43:25
快速通道