源碼學院-算法與數(shù)據(jù)結構最短路徑

最短路徑最短路徑介紹Dijkstra算法Bellman

Ford算法最短路徑問題最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。（有向帶權圖）問題解法邊上權值非負情形的單源最短路徑問題（s->圖上其他節(jié)點的最短路徑）Dijkstra算法邊上權值為任意值的單源最短路徑問題Bellman

Ford算法所有頂點之間的最短路徑（動態(tài)規(guī)劃O(n^3))Floyd算法最短路徑相關數(shù)據(jù)結構目標：找出從s節(jié)點到其他所有節(jié)點的最短路徑.路徑：s到所有節(jié)點的最短路徑樹(SPT)必定存在可以用2個數(shù)組來表示SPT:distTo[v]:s到v的最短路徑,100edgeTo[v]：s到v的最短路徑上的最后一條邊vswxsxwvS->

X->W

->V邊松馳-Edge

Relax的高鐵是沒有開通：700）到西安的距離：800）

->1500到

的最短距離（高鐵）2000）松馳邊：e=v->w

（西安到distTo[v]:s到v的已知最短路徑（distTo[w]:s到w的已知最短路徑（edgeTo[w]:s到w如果邊e=v→w

給更新distTo[w]和最短路徑-最優(yōu)性性質對于有向帶權圖G,

distTo[]表示s到各節(jié)點的路徑，有：distTo[s]

=0

對于其他各個節(jié)點，distTo[v]表示某條從s到v的路徑長度（對于不可達的節(jié)點，該值為無窮大）distTo[v]是最短路徑，當且僅當：對于任意一條v到w的邊e，都滿足：distTo[w]

≤

distTo[v]

+e.weight()最短路徑通用算法算法SP(G，s)：distTo[s]初始化為

0對于其他各個節(jié)點，distTo[v]初始化為無窮大重復如下操作：松馳G中的任意邊，直到不存在有效邊為止實現(xiàn)：怎么樣選擇邊來松馳？Dijkstra's

algorithm

(nonnegative

weights)Bellman-Ford

algorithm

(no

negative

cycles)最短路徑介紹Dijkstra算法Bellman

Ford算法Dijkstra算法Dijkstra算法求解從頂點v0出發(fā)到其它各頂點最短路徑。按路徑?度遞增的次序產(chǎn)?最短路徑，該算法假設所有邊的權都?于等于零。邊上權值非負情形的單源最短路徑問題問題的提法：給定一個帶權有向圖D與源點v，求從v

到D中其它頂點的最短路徑。限定各邊上的權值大于或等于0。為求得這些最短路徑,Dijkstra提出按路徑長度的遞增次序,

逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。Dijkstra逐步求解的過程43210150200

10030

1060源點終點最短路徑

路徑長度v0v1(v0,v1)10v2v3(v0,v3)(v0,v1,v2)

(v0,v3,v2),60,5030v4(v0,v4)(v0,v3,v4)

(v0,v3,v2

,v4)100,90,604210150200

10030

10603distTo[0]

=

0distTo[1]

=

10distTo[2]=

50distTo[3]

=

30distTo[4]

=

90第1步是選擇0節(jié)點，對它的所出邊進行松弛第2步是選擇1節(jié)點，對它的所出邊進行松弛第3步是選擇3節(jié)點，對它的所出邊進行松弛。。。42100

10015030

10603001

2

3

410

50

30

6034220引入輔助數(shù)組dist。它的每一個分量dist[i]表示當前找到的從源點

v0到終點

vi

的最短路徑的長度。初始狀態(tài)：若從源點v0到頂點vi

有邊,則dist[i]為該邊上的權值；若從源點v0到頂點

vi

無邊,則dist[i]為

。假設

S

是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0

出發(fā)，中間只經(jīng)過

S

中的頂點便可到達的那些頂點vx

(vxV-S

)的路徑中的一條。每次求得一條最短路徑后,其終點vk加入集合S，然后對所有的vi

V-S，修改其dist[i]值。Dijkstra算法可描述如下：①初始化：S

←{v0

};dist[j]

←

Edge[0][j], j

=

1,2,

…,

n-1;//n為圖中頂點個數(shù)②求出最短路徑的長度：dist[k]←min{dist[i]},

i

V-S

;

//s->k就是最短距離S

←

S

U

{

k

};③修改：dist[i]

←

min{

dist[i],

dist[k]

+

Edge[k][i]

},對于每一個

i

V-S

;④判斷：若S=V,則算法結束，否則轉②。Dijkstra算法中各輔助數(shù)組的最終結果短路徑的方法:舉頂點4為例edgeTo[4]

=

2

edgeTo[2]

=

3edgeTo[3]=0，反過來排列，得到路徑0,3,2,4，這就是源點0到終點4的最短路徑。0101502203010100

從表中

源點0到終點v的最4603序號頂點1頂點2頂點3頂點4Dist10-,60,503060edgeTo0302Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點40----0----0012340----索引堆：Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點40----0----1012340----索引堆：Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點40----0----1012340----索引堆：33010Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點401060301000----01234010-30100索引堆：031003041Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點401060301000----3012340106030100索引堆：1423010060Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點40105030900----201234010503090索引堆：34Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點40105030600----401234010503060索引堆：2作業(yè)：基于數(shù)組、堆實現(xiàn)Dijkstra算法Dijkstra示例01015022030101004603頂點0頂點1頂點2頂點3頂點40105030600----01234010503060索引堆：4最短路徑介紹Dijkstra算法Bellman

Ford算法Bellman-Ford算法解決含負權邊的帶權有向圖的單源最短路徑問題不能處理帶負權環(huán)的圖(因可以來回走一條負權邊)限制條件:要求圖中不能包含權值總和為負值回路(負權值回路)，如下圖所示。1246-190230->3:

20->1->2->3:

10->1->2->3->0:

-7Bellman-Ford算法思想構造一個最短路徑長度數(shù)組序列dist

1

[u],dist

2

[u],…,dist

n-1[u]

（u=0,1…n-1,n為點數(shù))dist

1

[u]為從源點s到終點u的最多經(jīng)過1次relax的最短路徑長度，并有dist

1

[u]=adj[s][u]；dist

2

[u]為從源點s最多經(jīng)過兩次relax到達終點u的最短路徑長度；dist

3

[u]為從源點s出發(fā)最多經(jīng)過不構成負權值回路的三次relax到達終點u的最短路徑長度；......dist

n-1

[u]為從源點s出發(fā)最多經(jīng)過不構成負權值回路的n-1次relax到達終點u的最短路徑長度；算法的最終目的是計算出distn-1

[u]，為源點v到頂點u的最短路徑長度。dist

k

[u]的計算設已經(jīng)求出

distk-1

[u],u=0,1,…,n-1，即從源點s經(jīng)過最多不構成負權值回路的k-1次relax到達終點u的最短路徑的長度遞推公式(求頂點u到源點s的最短路徑)：dist

1

[u]

=adj[s][u]；dist

k

[u]=

min{

dist

k-1

[u],

min{

dist

k-1

[j]

+

adj[j][u]

}

},j=0,1,…,n-1,j≠uBellman-Ford算法算法SP(G，s)：distTo[s]初始化為0對于其他各個節(jié)點，distTo[v]初始化為無窮大重復V-1次：依次松馳G中的各條邊Bellman-Ford算法010150230-101004603邊：0->10->30->41->22->43->23->4頂點0

頂點1

頂點2

頂點3

頂點40----0----頂點0頂點1頂點2頂點3頂點401060，5030100，5000->11->2,

3->20->30->4,

2->4頂點0頂點1頂點2頂點3頂點401050304000->13->20->32->4頂點0頂點1頂點2頂點3頂點401050304000->13->20->32->4頂點0頂點1頂點2頂點3頂點401050304000->13->20->32->420Bellman-Ford算法010150230-101004603頂點0頂點1頂點2頂點3頂點40----0----頂點0頂點1頂點2頂點3頂點40103010000->10->30->420隊列：0隊列：1,

3,

4頂點0頂點1頂點2頂點3頂點4010603010000->11->20->30->4隊列：3,

4,

2頂點0頂點1頂點2頂點3頂點401060,5030100,9000->11->2,3->20->30->4,3->4隊列：4,

2頂點0頂點1頂點2頂點3頂點401060,5030100,9000->11->2,3->20->30->4,3->4隊列：2Bellman-Ford算法010150230-10100460320頂點0頂點1頂點2頂點3頂點401060,5030100,9000->11->2,3->20->30->4,3->4隊列：2頂點0頂點1頂點2頂點3頂點401060,5030100,90,4000->11->2,3->20->30->4,3->4,2->4隊列：4頂點0頂點1頂點2頂點3頂點401060,50304000->13->20->32->4隊列：基于隊列的BellmenFord算法怎么來判斷有負環(huán)的？Dijkstra算法與Bellman-Ford算法的區(qū)別Dijkstra算法和Bellman算法思想有很大的區(qū)別：Dijkstra算法在求解過程中，源點到集合S內(nèi)各頂點的最短路徑一旦求出，則之后不變了，修改的僅僅是源點到S外各頂點的最短路徑長度。Bellman-Ford算法在求解過程中，每次循環(huán)都要修改所有頂點的

distTo[]，也就是說源點到各頂點最短路徑長度一直要到算法結束才確定下來。其他最短路徑算法：所有頂點之間的最短路徑Floyd問題的提法：已知一個各邊權值均大于0的帶權有向圖，對每一對頂點

vi

vj，要求求出vi與vj之間的最短路徑和最短路徑長度。

Floyd算法的基本思想：O(V^3)，動態(tài)規(guī)劃定義一個n階方陣序列：A(-1),

A(0),

…,

A(n-1).其中

A(-1)

[i][j]

=Edge[i][j