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