最短路徑四大算法
回答
愛(ài)揚(yáng)教育
2022-08-15
- 相關(guān)推薦
最短路徑算法從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑叫做最短路徑。解決最短路的問(wèn)題有以下算法，Dijkstra算法，Bellman-Ford算法，F(xiàn)loyd算法和SPFA算法等。
擴(kuò)展資料
bellman-ford可以用于邊權(quán)為負(fù)的圖中，圖里有負(fù)環(huán)也可以，如果有負(fù)環(huán)，算法會(huì)檢測(cè)出負(fù)環(huán)。
時(shí)間復(fù)雜度O（VE）;
dijkstra只能用于邊權(quán)都為正的圖中。
時(shí)間復(fù)雜度O（n2）；
spfa是個(gè)bellman-ford的優(yōu)化算法，本質(zhì)是bellman-ford，所以適用性和bellman-ford一樣。（用隊(duì)列和鄰接表優(yōu)化）。
時(shí)間復(fù)雜度O（KE）;
floyd可以用于有負(fù)權(quán)的圖中，即使有負(fù)環(huán)，算法也可以檢測(cè)出來(lái),可以求任意點(diǎn)的最短路徑，有向圖和無(wú)向圖的最小環(huán)和最大環(huán)。
時(shí)間復(fù)雜度O（n3）；
任何題目中都要注意的有四點(diǎn)事項(xiàng)：圖是有向圖還是無(wú)向圖、是否有負(fù)權(quán)邊，是否有重邊，頂點(diǎn)到自身的可達(dá)性。