迪杰斯特拉算法的基本思想.doc

《迪杰斯特拉算法的基本思想.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、迪杰斯特拉算法的基本思想算法的基本思想是：設(shè)置并逐步擴(kuò)充一個集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長度遞增的順序逐個以V-S中的頂點(diǎn)加到S中．直到S中包含全部頂點(diǎn)，而V-S為空。具體做法是：設(shè)源點(diǎn)為vl，則S中只包含頂點(diǎn)vl，令W＝V-S，則W中包含除v1外圖中所有頂點(diǎn)，vl對應(yīng)的距離值為0，W中頂點(diǎn)對應(yīng)的距離值是這樣規(guī)定的：若圖中有弧，則vj頂點(diǎn)的距離為此弧權(quán)值，否則為￥(一個很大的數(shù))，然后每次從W中的頂點(diǎn)中選—個其距離值為最小的頂點(diǎn)vm

2、加入到S中，每往S中加入一個頂點(diǎn)vm，就要對W中的各個頂點(diǎn)的距離值進(jìn)行一次修改。若加進(jìn)vm做中間頂點(diǎn)，使+的值小于值，則用+代替原來vj的距離，修改后再在W中選距離值最小的頂點(diǎn)加入到S中，如此進(jìn)行下去，直到S中包含了圖中所有頂點(diǎn)為止。下面以鄰接矩陣存儲來討論迪杰斯特拉算法的具體實(shí)現(xiàn)。為了找到從源點(diǎn)到其他頂點(diǎn)的最短路徑，引入兩個輔助數(shù)組dist[n],s[n],數(shù)組dist記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短距離，其初值為dist[i]=cost[v0][i],i

3、=2,...,n.其中v0表示源點(diǎn)。從S之外的頂點(diǎn)集合V-S中選出一個頂點(diǎn)w,使dist[w]的值最小。于是從源點(diǎn)到達(dá)w只通過S中的頂點(diǎn)，把w加入集合S中調(diào)整dist中記錄的從源點(diǎn)到V-S中每個頂點(diǎn)v的距離：從原來的dist[v]和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v],重復(fù)上述過程，直到S中包含V中其余各頂點(diǎn)的最短路徑。