狄克斯特拉算法.doc

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

1、狄克斯特拉算法目錄簡介算法依據(jù)算法的步驟應(yīng)用舉例編輯本段簡介　　狄克斯特拉算法亦即最短路徑搜索法，是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉（Dijkstra）于1959年提出，它被公認(rèn)為是最好的路徑搜索法之一。編輯本段算法依據(jù)　　????若從S點(diǎn)到T點(diǎn)有一條最短的路徑，則該路徑上的任何點(diǎn)到S的距離都是最短的。如上圖，A到C的最短路徑為A——E——C，可以看出來其路徑上的一點(diǎn)如E到C的最短距離也在A——E——C這條路徑上?！　τ谶@種很簡單的圖我們可以通過窮舉比較法很容易得到最短路徑。但是對于大規(guī)模的網(wǎng)絡(luò)圖，比如大城市的道

2、路網(wǎng)絡(luò)。這樣的話我們就很難一眼看出來最短路徑了。這時(shí)要用計(jì)算機(jī)根據(jù)狄克斯特拉算法計(jì)算最短路徑了。編輯本段算法的步驟　　1、狄克斯特拉算法將所有的頂點(diǎn)分為S,T兩類：S用來存放已知最短路徑的頂點(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?！　傞_始的S只有起始點(diǎn)一個(gè)，隨著算法的繼續(xù)，首先將起始點(diǎn)相鄰的點(diǎn)歸入到S，知道最后一點(diǎn)——目標(biāo)點(diǎn)歸入S。　　2、在起始點(diǎn)與相鄰點(diǎn)的路徑中選

3、擇一個(gè)最短的，然后將這個(gè)相鄰點(diǎn)設(shè)為起始點(diǎn)，重復(fù)上一步（注意，不能回退到第一個(gè)起始點(diǎn)，只能遞接下去）。直到所有的點(diǎn)都?xì)w為S為止?！　?、用公式表示如下　　另d（x，y）表示點(diǎn)x到y(tǒng)的距離，D（x）表示x到起始點(diǎn)的距離?！　ζ鹗键c(diǎn)S做標(biāo)記，且對所有起始點(diǎn)D（x）為無窮大。對所有為做標(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)過y。編輯本段應(yīng)用舉例　　如上圖，通過狄克斯特拉算法求出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è)步驟。來計(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)過D再到B的距離d(D,B)+D(D)相比，如D(B)比較小，則舍棄D點(diǎn)，路徑將不經(jīng)過D點(diǎn)。這是理解算法的關(guān)鍵。　　同理得D(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)舍去?！　?、對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、對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