1.迪杰斯特拉算法描述
迪杰斯特拉算法是基于LLDP（一種由IEEE802.1AB[11]定義的鏈路層發(fā)現(xiàn)協(xié)議）獲取信息，是一個(gè)從頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問(wèn)題。迪杰斯特拉算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。其中，算法描述如下：
- 將起始節(jié)點(diǎn)置于最短路徑樹(shù)的路徑（頂點(diǎn)）中。如果是進(jìn)行自律分散的路徑計(jì)算，則將自身置于路徑樹(shù)中，如果是通過(guò)openflow控制器進(jìn)行計(jì)算，則將關(guān)注的節(jié)點(diǎn)置于路徑樹(shù)中。
- 將與起始節(jié)點(diǎn)直接相連的所有節(jié)點(diǎn)作為未確定的路徑置于最短路徑樹(shù)中。
- 從未確定的路徑中，找出距離起始節(jié)點(diǎn)權(quán)值之和最小的路徑。
- 將與已確定節(jié)點(diǎn)直接相連作為未確定的路徑置于最短路徑樹(shù)中
- 計(jì)算與確定節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的權(quán)值之和，并比較新加入最短路徑樹(shù)的節(jié)點(diǎn)的權(quán)值之和，刪除權(quán)值之和較高、時(shí)間較長(zhǎng)的路徑。
- 重復(fù)3到5，直到未確定的路徑變?yōu)?為止。
2.算法原理
下圖1-1中有6個(gè)節(jié)點(diǎn)A-F，每個(gè)節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的權(quán)值已標(biāo)記在圖中，假設(shè)從A節(jié)點(diǎn)開(kāi)始計(jì)算路徑，則將A設(shè)為起始節(jié)點(diǎn)，即將A置于最短路徑樹(shù)的路徑中，之后將A所連接的節(jié)點(diǎn)B和C作為未確定路徑添加到最短路徑中。
迪杰斯特拉算法路徑計(jì)算1
因?yàn)閺腁到B的路徑已經(jīng)確定，則將B連接的節(jié)點(diǎn)作為未確定路徑添加到最短路徑樹(shù)中，A到C的直接路徑權(quán)值為200，A-B-C的權(quán)值之和為110，則比較后A-B-C路徑較優(yōu)，刪去A-B的路徑。迪杰斯特拉算法路徑計(jì)算2
由路徑計(jì)算1可確定A到C節(jié)點(diǎn)的最優(yōu)路徑，接下來(lái)，將C節(jié)點(diǎn)所連接的節(jié)點(diǎn)作為未確定路徑加入到路徑樹(shù)中，可知A-B-C-E的權(quán)值之和為120，A-B-E的路徑權(quán)值之和為210，比較后刪除B-E路徑。對(duì)于未確定節(jié)點(diǎn)D，可知A-B-D為最短路徑，進(jìn)而確定B-D的路徑，之后，將已確定的D節(jié)點(diǎn)上連接的F節(jié)點(diǎn)和E節(jié)點(diǎn)作為未確定路徑進(jìn)行添加。迪杰斯特拉算法路徑計(jì)算3
對(duì)于未確定路徑節(jié)點(diǎn)E由A-B-E為最短路徑，所以比較A-B-C-E與A-B-E,確定C-E為最短路徑，之后將未確定節(jié)點(diǎn)F作為未確定路徑進(jìn)行添加比較A-B-C-E-F與A-B-D-F的權(quán)值之和，確定最短路徑為E-F。最終，A對(duì)于所有節(jié)點(diǎn)的路徑均已確定。
3.代碼描述（Python）
def dijkstra_shortest_paths(graph,v0)
vnum=graph.vertex_num()
assert 0<=v0<vnum
paths=[None]*vnum
count=0
cands=PrioQueue([0,v0,v0])
while count<vnum and not cands.is_empty():
plen,u,vmin=cands.dequeue()
if paths[vmin]:
continue
paths[vmin]=(u,plen)
for v,w in graph.out_edges(vmin):
if not paths[v]:
cands.enqueue((plen+w,bmin,v))
count+=1
return paths
參考自數(shù)據(jù)結(jié)構(gòu)與算法（Python語(yǔ)言描述）
