在最短路徑問題中，給定一個帶權重的有向圖G=(V,E)和權重函數w：E→R，該權重函數將每條邊映射到實數值的權重上。圖中一條路徑p=[v0,v1,???,vk]的權重w(p)是構成該路徑的所有邊的權重之和。定義從結點u到結點v的最短路徑權重δ=(u,v)，從結點u到結點v的最短路徑則定義為任何一條權重w(p)= δ=(u,v)的從u到v的路徑p。 最短路徑存在幾個變體：
單目的地最短路徑問題：找到從每個結點v到給定目的地結點t的最短路徑。如果將圖的每一條邊的方向反過來，就可以將整個問題轉換為單源最短路徑問題。單結點對最短路徑問題：找到從給定結點u到給定結點v的最短路徑。所有結點對最短路徑問題：對于每個結點u和v，找到從結點u到結點v的最短路徑。最短路徑算法通常依賴最短路徑的一個重要性質：兩個結點之間的一條最短路徑包含著其它的最短路徑。在某些單源最短路徑問題中可能包括權重為負值的邊。如果從結點s到結點v的某條路徑上存在權重為負值的環路，則定義δ=(u,v)=-∞。
在通常情況下，不但需要計算出最短路徑權重，還需要計算出最短路徑上的結點。給定圖G=(V,E)，對于每個結點v，維持一個前驅結點v.π，該前去結點可能是另一個結點或者NIL。最短路徑算法將對每個結點的π屬性進行設置，這樣，將從結點v開始的前驅結點鏈反轉過來，就是從s到v的一條最短路徑。給定結點v，且v.π≠NIL，PRINT_PAT(G,s,v)打印出的就是從結點s到結點v 的一條最短路徑。 但是，在運行最短路徑算法的過程中，π值并不一定能給出最短路徑。定義結點集Vπ為圖G中的前驅結點不為NIL的結點的集合，再加上源結點s，即Vπ={v∈V:v.π≠NIL}∪{s}。有向邊集合Eπ是由Vπ中的結點的π值所誘導的邊的集合，即Eπ={(v.π,v) ∈E:v∈Vπ-{s}}。 單源最短路徑算法所生成的π值具有如下性質：在算法終止時，Gπ是一棵“最短路徑樹”。非形式化的說，最短路徑樹是一棵具有根結點的樹，該樹包括了從源結點s到每個可以從s到達的結點的一條最短路徑。設G=(V,E)是帶權重的有向圖，其權重函數為w：E→R，假定G不包含從s可以到達的權重為負值的環路。一棵根結點為s的最短路徑樹是一個有向子圖G’=(V’,E’)，滿足：
V’是圖G中從源結點s可以到達的所有結點的集合。G’形成一棵根結點為s的樹。對于所有的結點v∈V’，圖G’中從結點s到v的唯一簡單路徑是圖G中從結點s到結點v的一條最短路徑。需要指出的是，最短路徑不一定是唯一的，最短路徑樹葉不一定是唯一的。
對于每個結點v來說，為一個屬性v.d用來記錄從源結點s到結點v的最短路徑權重的上界，稱v.d為s到v的最短路徑估計。使用如下的算法來對最短路徑估計和前驅結點進行初始化：
INITIALIZE_SINGLE_SOURCE(G, s)for each vertex v ∈ G.V v.d = ∞ v.π = NILs.d = 0對一條邊(u,v)的松弛過程為：將從結點s到u之間的最短巨鹿加上結點u和v之間的權重，并與當前的s到v的最短路徑估計進行比較，如果前者更小，則對v.d和v.π進行更新。
RELAX(u,v,w)if v.d > u.d + w(u,v) v.d = u.d + w(u,v) v.π = u最短路徑和松弛操作的一些性質如下：
三角不等性質：對于任何邊(u,v) ∈E，有δ(s,v)≤δ(s,u)+w(u,v)。上界性質：對于所有的結點v∈V，有v.d≥δ(s,v)。一旦v.d的取值達到δ(s,v)，其值將不再變化。非路徑性質：如果從結點s到結點v之間不存在路徑，則總是有v.d=δ(s,v)=∞。收斂性質：對于某些結點u,v∈V，如果s是圖G中的一條最短路徑，并且在對邊（u,v）進行松弛前的任意時間有u.d=δ(s,u)，則在之后的所有時間有v.d=δ(s,v)。路徑松弛性質：如果p=(v0,v1,???,vk)是從源結點s=v0到結點vk的一條最短路徑，并且我們對p中的邊所進行松弛的次序為(v0,v1),(v1,v2),???,(v(k-1),vk)，則vk.d=δ(s,vk)。前驅子圖性質：對于所有的結點v∈V，一旦v.d=δ(s,v)，則前驅子圖是一棵根結點為s的最短路徑樹。Bellman-Ford算法解決的是一般情況下的單源最短路徑問題，邊的權重可以為負值。給定帶權重的有向圖G=(V,E)和權重函數w:E→R，Bellman-Ford算法返回一個布爾值，以表明是否存在一個從源結點可以到達的權重為負值的環路。如果存在這樣的一個環路，算法將告訴我們不存在解決方案。如果沒有這種環路存在，算法將給出最短路徑和它們的權重。 Bellman-Ford算法通過對邊進行松弛操作來漸近的降低從源結點s到每個節點v的最短路徑的估計值v.d，知道該估計值與實際的最短路徑權重δ(s,v)相同時為止。該算法返回TRUE值當且僅當輸入圖不包含可以從源結點到達的權重為負值的環路。
BELLMAN_FORD(G, w, s)INITIALIZE_SINGLE_SOURCE(G, s)for i = 1 to |G.V – 1| for each edge(u,v) ∈G.E RELAX(u, v, w)for each edge(u,v) ∈ G.E if v.d > u.d + w(u,v) return FALSEreturn TRUE 一個運用Bellman-Ford算法的過程示例如下圖所示。 
Dijkstra算法解決的是帶權重的有向圖上單源最短路徑問題，該算法要求所有邊的權重都為非負值。 Dijkstra算法在運行過程中維持的關鍵信息是一組結點集合S。從源結點s到該集合中每個結點之間的最短路徑已經被找到。算法重復從結點集V-S中選擇最短路徑估計最小的結點u，將u加入到集合S，然后對所有從u出發的邊進行松弛。使用一個最小優先隊列Q來保存集合，每個結點的關鍵值為其d值。
DIJKSTRA(G, w, s)INITIALIZE_SINGLE_SOURCE(G, s)S = NULLQ = G.Vwhile Q ≠ NULL u = EXTRACT_MIN(Q) S = S ∪ {u} for each vertex v ∈ G.Adj[u] RELAX(u, v, w) 一個執行該算法的過程示例如下圖所示。 
根據結點的拓撲排序次序來對帶權重的有向無環圖G=(V,E)進行邊的松弛操作，便可以計算出從單個源結點到所有結點之間的最短路徑。在有向無環圖中，即使存在權重為負值的邊，但因為沒有權重為負值的環路，最短路徑都是存在的。 首先對有向無環圖進行拓撲排序，確定結點之間的一個線性次序。如果有向無環圖包含從結點u到結點v的一條路徑，則v在拓撲排序的次序中位于結點v的前面。只需要按照拓撲排序的次序對結點進行一遍處理即可。每次對一個結點進行處理時，對從該結點出發的所有的邊進行松弛操作。
DAG_SHORTEST_PATHS(G, w, s)topologically sort the vertices of GINITIALIZE_SINGLE_SOURCE(G, s)for each vertex u, taken in topologically sorted order for each vertex v ∈ G.Adj[u] RELAX(u, v, w) 一個執行該算法的過程示例如下圖所示。 
新聞熱點
疑難解答
