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

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 負權形成環路的圖為什么不能用弗洛伊德算法求任意兩點之間的最短路徑?

負權形成環路的圖為什么不能用弗洛伊德算法求任意兩點之間的最短路徑?

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

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

負權形成環路的圖,任意兩點間可能沒有最短路徑。例如負權環C,點A,B是C上的點,A可以在C中轉上任意圈后再沿C到B,這條路徑權值可以任意小。而Floyd算法可以給出網絡中任意兩個節點之間的最短路徑。

Floyd算法的基本思想

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

1是直接從A到B;2是從A經過若干個節點到B。

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

Floyd算法與Dijkstra算法的不同

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

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

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

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

延伸閱讀:

二、最短路徑問題(SPP)

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

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

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

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

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

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

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

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

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

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

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

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

3)圖中是否存在負環路(權重之和為負數)。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT