問題11 最短路徑

?

圖的最短路徑問題是一個(gè)圖的基本問題。最短路徑問題的應(yīng)用很廣。

?

圖的最短路徑問題不是一個(gè)問題，而是一個(gè)問題集合。本書在介紹算法時(shí)，沒有明確給出具體的問題描述，讀者要注意，不要混淆了。

?

本章在介紹問題求解時(shí)，按照算法基本思想—算法描述—算法運(yùn)行示例—算法分析這4個(gè)步驟展開介紹?！咀髡吒惺?，這個(gè)4個(gè)步驟是學(xué)習(xí)各種算法的標(biāo)準(zhǔn)步驟，對(duì)學(xué)習(xí)者各方面能力的訓(xùn)練都有幫助，還可以加上，代碼實(shí)現(xiàn)，就更完整】

?

本章首先介紹了一個(gè)基于廣度優(yōu)先搜索（BFS）算法求解算法【建議先了解DFS和BFS】。

然后介紹了在數(shù)據(jù)結(jié)構(gòu)、算法教材中最常見的經(jīng)典算法Dijkstra算法（這是圖靈獎(jiǎng)獲得者Dijkstra發(fā)明的算法）。這里就不詳細(xì)介紹了，推薦自讀。

?

【作者感受】

求解圖的最短路徑問題的有效算法值得學(xué)習(xí)，因?yàn)閳D的最短路徑應(yīng)用非常廣泛。

圖的最短路徑有很多（圖的）特色性質(zhì)，有興趣的讀者可以在圖論中學(xué)習(xí)。

針對(duì)圖的最短路徑問題，可以采用很多種算法設(shè)計(jì)策略（如貪心、動(dòng)態(tài)規(guī)劃等）。不同的算法可能展現(xiàn)出不同的優(yōu)勢(shì)，更好地適應(yīng)不同的輸入數(shù)據(jù)（圖）；同時(shí)，學(xué)習(xí)不同的算法，分析不同算法的性能（效率和適用性），可以加深對(duì)最短路徑問題的理解，訓(xùn)練讀者的算法思維。

要高效實(shí)現(xiàn)最短路徑算法的實(shí)際運(yùn)行時(shí)間，需要一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的支持（空間換時(shí)間）。

證明最短路徑算法的正確性，需要用到圖論的一些知識(shí)，還會(huì)用到歸納法或反證法，需要一定的數(shù)學(xué)基礎(chǔ)。

?

學(xué)習(xí)本章，對(duì)算法邏輯、程序和數(shù)據(jù)結(jié)構(gòu)、數(shù)學(xué)知識(shí)都涉獵，有一點(diǎn)難度，但是難度還好。

所以，最短路徑算法是數(shù)據(jù)結(jié)構(gòu)、算法教材中必有的內(nèi)容。

?

而且，最短路徑問題中，直至目前為止，求解單點(diǎn)到單點(diǎn)的最短路徑在理論上沒有發(fā)現(xiàn)比求解單點(diǎn)到其他各點(diǎn)最短路徑更優(yōu)的算法。然而，在大規(guī)模圖中，如何針對(duì)特定的問題或需求，設(shè)計(jì)出實(shí)際有效（運(yùn)行時(shí)間滿足應(yīng)用需求）的求解最短路徑程序也是蠻有意義的。