???????????????????????????????????????????? 最短路徑算法綜述????????????????????????????????????????????

更新中。。。。

1.單源最短路徑問(wèn)題

涵義：從給定的源頂點(diǎn)s到每個(gè)頂點(diǎn)v的最短路徑。

在弄清楚如何求算單源最短路徑問(wèn)題之前，必須弄掌握幾點(diǎn)知識(shí)。

?最短路徑的最優(yōu)子結(jié)構(gòu)?? 最短路徑算法通常依賴(lài)于一種性質(zhì)，也就是一條兩頂點(diǎn)之間的最短路徑包含路徑上其他的最短路徑。這種最優(yōu)子結(jié)構(gòu)性質(zhì)是動(dòng)態(tài)規(guī)劃和貪心算法是否適用的一個(gè)標(biāo)記。Dijkstra算法是一個(gè)貪心算法，而找出所有頂點(diǎn)對(duì)之間的最短路徑的Floyd_Warshall算法是一個(gè)動(dòng)態(tài)規(guī)劃算法。下面的引理更加準(zhǔn)確地陳述了最短路徑的最優(yōu)子結(jié)構(gòu)的性質(zhì)。

?引理1（最短路徑的子路徑是最短路徑） 證明略，請(qǐng)參考《算法導(dǎo)論》P358

?負(fù)權(quán)值邊：單源最短路徑的某些示例中，可能存在權(quán)值為負(fù)值的邊。但是不可能存在負(fù)權(quán)回路。Dijkstra不能處理負(fù)權(quán)值的圖，Bellman-Ford能處理。

?回路：最短路徑上不可能有回路。

?最短路徑的表示：已知圖G=（V,E）,對(duì)于每個(gè)頂點(diǎn)v∈V，設(shè)置其前驅(qū)（predecessor）頂點(diǎn)∏（v）為另一頂點(diǎn)或NIL。通過(guò)這種方法，就可以使用PRINT-PATH(G,s,v)函數(shù)來(lái)打印路徑。

松弛技術(shù)（relaxation）：對(duì)于每個(gè)頂點(diǎn)設(shè)置一個(gè)屬性的d[v]來(lái)描述從源點(diǎn)s到v的最短路徑上權(quán)值的上界。具體請(qǐng)參考《算法導(dǎo)論》P360

最短路徑以及松弛的性質(zhì)：三角不等式、上界性質(zhì)、無(wú)路徑性質(zhì)、收斂性質(zhì)、路徑松弛性質(zhì)、前驅(qū)子圖性質(zhì)等等。具體請(qǐng)參考《算法導(dǎo)論》P361

?問(wèn)題的3個(gè)變體：

?????? ?.單終點(diǎn)最短路徑

?????? ?.單對(duì)頂點(diǎn)最短路徑

?????? ?.每對(duì)頂點(diǎn)間最短路徑

2.Bellman-Ford算法分析與實(shí)現(xiàn)(C/C++)

http://www.wutianqi.com/?p=1912

3.Dijkstra算法分析與實(shí)現(xiàn)(C/C++)

?????http://www.cnblogs.com/panweishadow/p/3396001.html

4.SPFA(Shortest Path Faster Algorithm)算法分析與實(shí)現(xiàn)(C/C++)

????? http://www.wutianqi.com/?p=2285

???

???? 感謝Tanky Woo大神的博客，他的算法專(zhuān)題鏈接：http://www.wutianqi.com/sfzt.html

轉(zhuǎn)載于:https://www.cnblogs.com/panweishadow/p/3392778.html

總結(jié)

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

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