最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：
确定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。适合使用Dijkstra算法。
确定終點的最短路徑問題 - 與确定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與确定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的确定起點的問題。
确定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
全局最短路徑問題 - 求圖中所有的最短路徑。适合使用Floyd-Warshall算法。
用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最常用的路徑算法有：
Dijkstra算法
A*算法
Bellman-Ford算法
SPFA算法（Bellman-Ford算法的改進版本）
Floyd-Warshall算法
Johnson算法
Bi-Direction BFS算法
以上說明的是基本最短路問題，這裡要介紹的是帶有約束條件的最短路問題，例如：
最多走10步
有必須要經過的點、邊
有不能經過的點、邊
解決方法其實隻需要一個思路：拆點構圖，即點附狀态。約束條件有幾種可能的組合方式，就有幾種狀态。例如，最多走5步，有兩個必須經過的點，有兩個必須經過的邊，（先不考慮不能經過），那麼狀态數就是，6*3*3=54，即每個點有54種狀态。
以Dijkstra為例先來複習下Dijkstra算法，其僞代碼如下：
考慮上述拆點構圖我們需要做什麼呢？首先在描述距離的數組d要增加維度，例如d[n][54]。這樣，我們的以确定最優路徑集合S，未确定最優集合Q，就不能再是單純的點集，而應該是(點 狀态)集。其次在11到14行，以确定最優點優化其他點是，應當根據約束條件計算出被優化點的狀态是什麼，再去更新該狀态的點。同樣previous數組也應記錄的是，s1狀态點p1的前一點是s0狀态的點p0。
最後，考慮不能經過的點、邊，估計你早有思路，就是把該點、邊從你的圖結構中直接抹去。
OK，到此為止，闡述完畢。
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
