問題11 最短路徑

?

圖的最短路徑問題是一個圖的基本問題。最短路徑問題的應用很廣。

?

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

?

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

?

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

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

?

【作者感受】

求解圖的最短路徑問題的有效算法值得學習，因為圖的最短路徑應用非常廣泛。

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

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

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

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

?

學習本章，對算法邏輯、程序和數(shù)據(jù)結構、數(shù)學知識都涉獵，有一點難度，但是難度還好。

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

?

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