貪心算法ppt課件(2)-資料下載頁
2025-05-12 13:28本頁面
【正文】 22/5/31 30 給定一個帶權(quán)有向圖 G=(V,E),其中每條邊的權(quán)是一個非負(fù)實數(shù) 。 另外 ,還給定 V中的一個頂點 ， 稱為源 。 現(xiàn)在我們要計算從源到所有其他各頂點的最短路長度 。 這里路的長度是指路上各邊權(quán)之和 。 這個問題通常稱為單源最短路徑問題 。 Dijkstra于 1959年提出了解決此問題的一般算法 ， 此算法可按邊的權(quán)值由小到大的次序 ， 通過 貪婪選擇 ， 逐步得到由給定源點到圖的其余各點間的最短路徑 。 其基本作法是 ， 設(shè)置一個頂點集合 S， 一個頂點屬于集合 S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知 。 初始時 ， S中僅含有源點 。 設(shè) vi是 G的某一個頂點 ， 我們把從源點到 vi且中間只經(jīng)過 S中頂點的路稱為從源點到 vi的路徑 ， 并用數(shù)組 dist來記錄當(dāng)前 S中每個頂點所對應(yīng)的最短路徑長度 。 1．單源最短路徑 2022/5/31 31 Dijkstra算法每次從 VS中取出具有最短路徑長度的頂點 vi， 將 vi添加到 S中，同時檢查 vi添加到 S中后，源點到 VS中各頂點的距離是否可以通過源點到 vi的 路徑而縮短，如果縮短則對數(shù)組 dist作必要的修改。一旦 S包含了所有 V中頂點， dist就記錄了從源到所有其他頂點之間的最短路徑長度。 例如下圖所示 距離矩陣 2022/5/31 32 現(xiàn)以頂點 6為源點，求到其他各頂點的最短路徑長度。 2022/5/31 33 2022/5/31 34 例如，對右圖中的有向圖，應(yīng)用 Dijkstra算法計算從源頂點 1到其他頂點間最短路徑的過程列在下頁的表中。 2022/5/31 35 迭代 S u dist[2] dist[3] dist[4] dist[5] 初始 {1} 10 maxint 30 100 1 {1,2} 2 10 60 30 100 2 {1,2,4} 4 10 50 30 90 3 {1,2,4,3} 3 10 50 30 60 4 {1,2,4,3,5} 5 10 50 30 60 Dijkstra算法的迭代過程： Dijkstra算法最短路徑的計算復(fù)雜性是 O(n^2),其中 n是圖的頂點個數(shù)。 2022/5/31 36 已知一個各邊權(quán)值均大于零的有向圖 ， 對每一對i≠j ， 要求求出 vi與 vj兩點之間最短路徑的長度 。因為是有向圖 ， 一般從 vi到 vj和從 vj到 vi的長度并不相同 ， 要分別得出 。 故對有 n個頂點的圖共有 n(n1)條路徑長度待求 。 解決此問題的一個辦法是 ， 輪流以每個頂點為源點 ， 重復(fù)按上述的狄克斯特拉算法運算 n次 ， 即得到要求的 n(n1)條路徑 。 2．求每一對頂點之間的最短路徑 2022/5/31 37 如圖所示，要從 A0點鋪設(shè)一條管道到 A6點，中間必須經(jīng)過 5個中間站，第一站可以在 A1， B1兩地中任選一個，類似地，第二、三、四、五站可供選擇的地點分別是： {A2， B2， C2， D2}， {A3，B3， C3}， {A4， B4， C4}， {A5， B5}。 連接兩地間管道的距離（或造價）用連線上的數(shù)字表示，要求選一條從 A0到 A6的鋪管線路，使總距離最短（或總造價最小〕。 3．點對間最短路徑實例 2022/5/31 38 上述問題的距離矩陣為 ： 2022/5/31 39 2022/5/31 40
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1