單源最短路徑，在現(xiàn)實中是很多應用的，是圖的經(jīng)典應用，比如在地圖中找出兩個點之間的最短距離、最小運費等。單源最短路徑的問題：已知圖G=(V,E)，找出給定源頂點s∈V到每個頂點v∈V的最短路徑。單源最短路徑衍生出的變體問題如下：

1）單終點最短路徑問題：找出從每個頂點v到指定終點t的最短路徑。這個是單源最短路徑的反向，把圖的每條邊反向，問題就變成單源最短路徑的問題；

2）單對頂點最短路徑問題：對于給定頂點u和v，找出從u到v的一條最短路徑。找出所有頂點的單源最短路徑，該問題自然得解。

3）每隊頂點間最短路徑問題：對于給定頂點u和v，找出從u到v的最短路徑。單獨討論

針對單源最短路徑問題，構建如下的數(shù)學模型來描述：

給定的帶權有向圖G=(V,E)，加權函數(shù)w:E->R為從邊到實型權值的映射。路徑p=<v₀,v₁,…,v_k>的權是指其組成邊的所有權值之和：

如果u到v存在一條路徑，則其最小權值的邊集合為最短路徑。

最短路徑算法具有動態(tài)規(guī)劃和貪心算法的最優(yōu)子結構性質：最短路徑的子路徑是最短路徑，即一條頂點間的最短路徑包含路徑上其他的最短路徑。

對圖求解最短路徑的問題，存在負權值邊和負權回路的情況。經(jīng)過負權值邊，權值會減小，而無限次經(jīng)過負權回路，權值會趨近-∞，所以一條最短路徑是不應該包含負權回路。在最短路徑算法總，Dijkstra算法假定圖的所有邊權值都非負；而Bellman-Ford算法，允許圖存在負權邊，但不能存在從源點可達的負權回路，該算法還能檢測出負權回路。

最短路徑之于一個圖的發(fā)現(xiàn)，其實是一棵有根的最短路徑樹，只要回溯每個頂點的父頂點即可。定義定點集V_π為G總所有具有非空前趨（存在負頂點）的頂點集合，再加上源點s。

V_π={v∈V:π[v]≠null}U{s}

有向邊集E_π是有V_π中的頂點π值導出的邊集：

E_π={(π[v],v)∈E:v∈V_π-{s}}

G_π(V_π,,E_π)就是最短路徑樹，s是根節(jié)點。

設圖G=(V,E)是帶權有向圖，其加權函數(shù)w:E->R，并假定G中不包含從源點s∈V可達的權值為負的回路，那么最短路徑是良定義 。以s為根的最短路徑樹是有向子圖G_π(V_π,,E_π)，其中V_π?V，E_π?E，那么：

1）V_π是G中從s可達的頂點集合；

2）G_π形成一顆以s為根的有根樹；

3）對所有v屬于V_π，G_π中從s到v的唯一簡單路徑是G中從s到v的最短路徑。

當然最短路徑并不是唯一的，最短路徑樹也是。

導論中給出松弛技術，就是表示緊縮上界的方法。對每個頂點v∈V，設置一個屬性d[v]，表示從源點s到v的最短路徑上權值的上界，稱為最短路徑估計。松弛操作，對每個頂點d[v]初始為∞，松弛一條邊(u,v)可以減小最短路徑估計的值d[v]，并更新v的前趨π[v]。

Relax_Func(){

??? if d[v]>d[u]+w(u,v)

????? then d[v]=d[u]+w(u,v)

?????????? π[v]=u

}

松弛操作，通俗地說，就是先設置d[v]最大，然后找出其邊權來更新d[v]和π[v]，從而不斷減小d[v]值，是算法的一種指示變量。

最短路徑和松弛操作是最短路徑算法的基礎，具有三角不等式、上界、無路徑、收斂、路徑松弛、前趨子圖六個性質。還有一個無窮運算的約定：

假定對任何實數(shù)a≠-∞，有a+∞=∞+a=∞，出現(xiàn)負權回路下，假定對任何實數(shù)a≠∞，有a+(-∞)= (-∞)+a=-∞。

1）Bellman-Ford算法

Bellman-Ford算法支持存在負權邊的情況下，解決單源最短路徑問題。輸入給定的帶權有向圖G=(V,E)，其源點為s，加權函數(shù)為w:E->R，執(zhí)行Bellman-Ford算法后輸出一個返回值，表明圖中是否存在著一個從源點可達的權為負的回路。如存在，則無解，否則將產(chǎn)生最短路徑及其權值。

簡單來說，Bellman-Ford算法的執(zhí)行結果將確認是否存在負權回路，如果沒有就會產(chǎn)生最短路徑及其權值。具體算法如下：

Func_Bellman-Ford(G,w,s){

??? Func_Initialize-single-source(G,s);//初始化每個頂點的d和π值

??? //開始進行松弛操作

??? for i=1 to |V(G)|-1

??????? do for each edge (u,v)∈E(G)

?????????? do Func_Relax(u,v,w)

???? for each edge(u,v) ∈E(G)

??????? do if d[v]>d[u]+w(u,v)? //已經(jīng)松弛操作了，如果還存在子頂點大于負頂點權值的情況，則存在負權回路

?????????? then return false? //存在負權回路，返回false

???? return true

}

?

Func_Relax(u,v,w){

??? if d[v]>d[u]+w(u,v)

??????? then d[v]= d[u]+w(u,v)

???????????? π[v]=u

}

?

Func_Initialize-single-source(G,s){

?? ?for eachvertex v∈V[G]

??????? do d[v]=∞

?????????? π[v]=null

??? d[s]=0

}

Bellman-Ford算法的運行時間為O(VE)，主要是如何證明該算法執(zhí)行結果的正確性。算法導論中通過反證法和三角不等式證明了該算法可以正確計算出從源點出到所有頂點的最小路徑的權。

有興趣可以理解下證明過程，不過中心思想依然是說明不存在負權回路情況下從源點到所有頂點間的最小路徑權值。

在有向無回路情況下，按頂點的拓撲序列對某加權dag圖（有向無回路圖）G=(V,E)的邊進行松弛后，可以在⊙(V+E)時間內計算出單源最短路徑。Dag圖最短路徑總是存在的，即使圖中有權值為負的邊存在，也不可能存在負權回路。

有向無回路圖中的單源最短路徑算法開始對dag圖進行拓撲排序（運用DFS），獲得頂點的線性序列。如果從頂點u到v存在一條路徑，則在拓撲序列中u先于v；對頂點線性序列的每個頂點做松弛操作即獲得單源最短路徑。算法的典型應用是在PERT圖分析中確定關鍵路徑。關鍵路徑是通過dag的一條最長路徑，對應于執(zhí)行一個有序的工作序列的最長時間。關鍵路徑的權值是完成所有工作所需要時間的下限。理解下就是這個算法適合于序列圖。

2）Dijkstra算法

Dijkstra算法解決有向圖G=(V,E)上帶權的單源最短路徑問題，但要求所有邊的權值非負，即每條邊(u,v)∈E，有w(u,v)≥0。Dijkstra算法有一個頂點集合S，包含具有最短路徑的頂點。算法反復選擇具有最短路徑估計的頂點u∈V-S，將u加入S，對u的所有邊進行松弛操作。算法采用了最小優(yōu)先隊列Q來排序關鍵字為頂點的d值。最小優(yōu)先隊列操作有插入、抽取最小、刪除三個操作，不同數(shù)據(jù)結構實現(xiàn)由不同的時間性能：第一種數(shù)組結構，從1到|V|編好號的頂點，簡單將d[v]存入一個數(shù)組的第v項，插入和刪除操作都是O(1)，但搜索最小時間是O(V)；第二種二叉最小堆結構，時間性能有提升；第三種是斐波那契堆，時間性能也會有提升。Dijkstra算法和最小生成樹的Prim算法相似。下面看具體算法：

Func_Relax(u,v,w){

??? if d[v]>d[u]+w(u,v)

??????? then d[v]= d[u]+w(u,v)

???????????? π[v]=u

}

?

Func_Initialize-single-source(G,s){

?? ?for eachvertex v∈V[G]

??????? do d[v]=∞

?????????? π[v]=null

??? d[s]=0

}

Func_Dijkstra(G,w,s){

?? Func_Initialize-single-source(G,s)

?? S=?

?? Q=V[G] //包含所有頂點，最小優(yōu)先隊列插入

?? While Q≠?

?????? do u=Extract-Min(Q) //最小優(yōu)先隊列搜索最小值

??????? S=SU{u}

??????? for each vertex v∈Adj[u]//所有u的鄰接表中的頂點

??????????? do Func_Relax(u,v,w) //包含最小優(yōu)先隊列u出列

}

Dijkstra算法總是在V-S中選擇最輕或最近的頂點插入集合S中，是一種貪心策略。算法導論中證明了Dijkstra算法應用貪心策略可以得出最短路徑。證明過程采用的數(shù)學思路也很值得去細細品味，包括最短路徑的性質的證明：三角不等式、上界性質、無路徑性質、收斂性質、路徑松弛性質和前驅子圖性質（構建以s為根的最短路徑樹）。在算法中，樹和圖是有著緊密聯(lián)系。

3）差分約束系統(tǒng)與最短路徑

將計算機中的某類問題求解轉化成數(shù)學模型來求解，是一以貫之的。同樣的，將不包含負權回路的圖G=(V,E)求解單源最短路徑問題轉為線性規(guī)劃中的差分約束系統(tǒng)模型來求解，而Bellman-Ford算法實際就是一種線性規(guī)劃算法。

一般的線性規(guī)劃問題（linear-programmingproblem）中，給定一個mXn的矩陣A，一個m維向量b和一個n維向量c，找出由n個元素組成的向量x，在由Ax≤b所給出的m個約束條件下，使目標函

總結

以上是生活随笔為你收集整理的算法导论之单源最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。

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