資源描述：
《狄克斯特拉算法.doc》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、狄克斯特拉算法目錄簡(jiǎn)介算法依據(jù)算法的步驟應(yīng)用舉例編輯本段簡(jiǎn)介 狄克斯特拉算法亦即最短路徑搜索法，是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉（Dijkstra）于1959年提出，它被公認(rèn)為是最好的路徑搜索法之一。編輯本段算法依據(jù) ????若從S點(diǎn)到T點(diǎn)有一條最短的路徑，則該路徑上的任何點(diǎn)到S的距離都是最短的。如上圖，A到C的最短路徑為A——E——C，可以看出來(lái)其路徑上的一點(diǎn)如E到C的最短距離也在A——E——C這條路徑上?！ ?duì)于這種很簡(jiǎn)單的圖我們可以通過(guò)窮舉比較法很容易得到最短路徑。但是對(duì)于大規(guī)模的網(wǎng)絡(luò)圖，比如大城市的道
2、路網(wǎng)絡(luò)。這樣的話(huà)我們就很難一眼看出來(lái)最短路徑了。這時(shí)要用計(jì)算機(jī)根據(jù)狄克斯特拉算法計(jì)算最短路徑了。編輯本段算法的步驟 1、狄克斯特拉算法將所有的頂點(diǎn)分為S,T兩類(lèi)：S用來(lái)存放已知最短路徑的頂點(diǎn)。而T存放未知最短路徑的頂點(diǎn)。如果起始點(diǎn)（假設(shè)上圖的v1為起始點(diǎn)）到某個(gè)頂點(diǎn)（相鄰點(diǎn)）的最短距離已經(jīng)求出，比如A——B的距離。那么就把B歸入S，其余的不能直接算出最短距離的則要?dú)w入T?！ 傞_(kāi)始的S只有起始點(diǎn)一個(gè)，隨著算法的繼續(xù)，首先將起始點(diǎn)相鄰的點(diǎn)歸入到S，知道最后一點(diǎn)——目標(biāo)點(diǎn)歸入S?！ ?、在起始點(diǎn)與相鄰點(diǎn)的路徑中選
3、擇一個(gè)最短的，然后將這個(gè)相鄰點(diǎn)設(shè)為起始點(diǎn)，重復(fù)上一步（注意，不能回退到第一個(gè)起始點(diǎn)，只能遞接下去）。直到所有的點(diǎn)都?xì)w為S為止。 3、用公式表示如下 另d（x，y）表示點(diǎn)x到y(tǒng)的距離，D（x）表示x到起始點(diǎn)的距離。 對(duì)起始點(diǎn)S做標(biāo)記，且對(duì)所有起始點(diǎn)D（x）為無(wú)窮大。對(duì)所有為做標(biāo)記的點(diǎn)按以下公式計(jì)算距離 D(x)=min(D(X)d(x,y)+D(y)) 其中y是最后一個(gè)標(biāo)記的點(diǎn)。也就是與起始點(diǎn)的距離已知的那個(gè)點(diǎn)?！ ∩鲜鲞@個(gè)公式的表示，D(X)要和D（x，y）+D（y）相比，如果前者小，那么就將這個(gè)標(biāo)記
4、點(diǎn)y去掉。路徑直接為起始點(diǎn)到x。否則，路徑要經(jīng)過(guò)y。編輯本段應(yīng)用舉例 如上圖，通過(guò)狄克斯特拉算法求出v1到v7的最短距離 1、首先將A做為起始點(diǎn)進(jìn)行標(biāo)記。算出v1到相鄰各點(diǎn)的距離?！ (B)=4 D(C)=∞ D(D)=1 D(E)=2 最小值為D(D)=1，所以將D點(diǎn)做標(biāo)記。 2、因?yàn)镈(D)最小，所以將D進(jìn)行標(biāo)記，重復(fù)上個(gè)步驟。來(lái)計(jì)算D(B),D(C),D(E) D(B)=min(D(B),d(D,B)+D(D))=min(4,∞+1)=4 其中D(B)表示起始點(diǎn)A到B的距離。用這個(gè)距離
5、跟起始點(diǎn)A經(jīng)過(guò)D再到B的距離d(D,B)+D(D)相比，如D(B)比較小，則舍棄D點(diǎn)，路徑將不經(jīng)過(guò)D點(diǎn)。這是理解算法的關(guān)鍵?！ ⊥淼肈(C)=min(D(C),d(D,C)+D(D))=min(∞,9+1)=10 D(E)=min(D(E),d(D,E)+D(D))=min(2,2+1)=2 這里D（E）最小，所以取E點(diǎn)為標(biāo)記點(diǎn)。且因?yàn)槠鹗键c(diǎn)A到E的距離比A——D——E的短，所以將D點(diǎn)舍去?！ ?、對(duì)E做標(biāo)記，計(jì)算D(B),D(C) D(B)＝min(D(B),d(E,B)＋D(E))＝min(4,1＋
6、2)＝3 D(C)＝min(D(C),d(E,C)＋D(E))＝min(10,6＋2)＝8 最小值為D(B)＝3。去B為標(biāo)記點(diǎn)，且因?yàn)锳——E——B的距離比A——B的距離短，所以將E點(diǎn)保留。 4、對(duì)B作標(biāo)記，計(jì)算D(C) D(C)＝min(D(C),d(B,C)＋D(B))＝min(8,7＋3)＝8 因?yàn)镈(C)小于d(B,C)+D(B),所以將B點(diǎn)舍去?！ 【C上，路徑為A——E——C
