1。 肯定不能用dijkstra算法，這是因?yàn)?#xff0c;Dijkstra算法的大致思想是每次選擇距離源點(diǎn)最近的結(jié)點(diǎn)加入，然后更新其它結(jié)點(diǎn)到源點(diǎn)的距離，直到所有點(diǎn)都被加入為止。當(dāng)每次選擇最短的路改為每次選擇最長(zhǎng)路的時(shí)候，出現(xiàn)了一個(gè)問(wèn)題，那就是不能保證現(xiàn)在加入的結(jié)點(diǎn)以后是否會(huì)被更新而使得到源點(diǎn)的距離變得更長(zhǎng)，而這個(gè)點(diǎn)一旦被選中將不再會(huì)被更新。例如這次加入結(jié)點(diǎn)u，最長(zhǎng)路為10，下次有可能加入一個(gè)結(jié)點(diǎn)v，使得u通過(guò)v到源點(diǎn)的距離大于10，但由于u在之前已經(jīng)被加入到集合中，無(wú)法再更新，導(dǎo)致結(jié)果是不正確的。

?? ? 如果取反用dijkstra求最短路徑呢，記住，dijkstra不能計(jì)算有負(fù)邊的情況。。。

2.

可以用 ? Bellman-Ford ? 算法求最長(zhǎng)路徑，只要把圖中的邊權(quán)改為原來(lái)的相反數(shù)即可。也可以用Floyd-Warshall ? 算法求每對(duì)節(jié)點(diǎn)之間的最長(zhǎng)路經(jīng)，因?yàn)樽铋L(zhǎng)路徑也滿(mǎn)足最優(yōu)子結(jié)構(gòu)性質(zhì)，而Floyd算法的實(shí)質(zhì)就是動(dòng)態(tài)規(guī)劃。但是，如果圖中含有回路，Floyd算法并不能判斷出其中含有回路，且會(huì)求出一個(gè)錯(cuò)誤的解；而B(niǎo)ellman-Ford算法則可以判斷出圖中是否含有回路。

3. 如果是有向無(wú)環(huán)圖，先拓?fù)渑判?#xff0c;再用動(dòng)態(tài)規(guī)劃求解。

總結(jié)

以上是生活随笔為你收集整理的图的最长路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。