短路問題ppt課件(編輯修改稿)
2025-05-28 22:13 本頁面
【文章內(nèi)容簡介】 頭來看看標(biāo)號法好不好 .回想一下標(biāo)號法的各輪計(jì)算，可以看出，它只包含兩種運(yùn)算：加法與比較大小 (比較大小也需要花費(fèi)時間，所以也要考慮 ).加法用于計(jì)算 k(i,j)，每計(jì)算一個 k(i,j)進(jìn)行一次加法，而且每一條弧最多只計(jì)算一次 .因此 ,如果圖中有 m條弧，那么至多進(jìn)行 m次加法 .對于一個有 n個頂點(diǎn)的簡單有向圖來說，最多有 n(n1)條弧 (假設(shè)從每一個頂點(diǎn) vi出發(fā)，都有 n1條弧指向其他的 n1個頂點(diǎn) )，因此，最多進(jìn)行 n(n1)次加法，放寬一點(diǎn)，也可以說，至多進(jìn)行 n2次加法 . 另外，在每一輪計(jì)算中，在找使 k(i,j)達(dá)到最小的弧 c,d時，要用到比較大小的運(yùn)算，一般說來，要從 s個數(shù)中把最小的數(shù)找出來，要進(jìn)行 s1次比較 (例如有四個數(shù) a1,a2,a3,a4，那么可以先拿 a1與 a2比，然后拿這兩個數(shù)中小的數(shù)與 a3比，再拿小的數(shù)與 a4比，比三次就能知道哪個數(shù)最小了 ).那么在每一輪的步驟 1中，一般會選出幾條弧呢？算得寬一些，至多 n2條吧 (事實(shí)上要少得多 )，因此至多進(jìn)行n2次比較，整個計(jì)算的輪數(shù)不會超過 n，因此，總起來說，至多進(jìn)行 n3次比較大小的運(yùn)算 . 通過上面的估計(jì)，可以得出這樣的結(jié)論：把標(biāo)號法用在一個 n個頂點(diǎn)的圖上，至多進(jìn)行 n2次加法和 n3次比較大小 .因此，可以說，標(biāo)號法是一種好的、有效的計(jì)算方法 . 問題： 給定簡單權(quán)圖 G = (V, E)，并設(shè) G 有 n個頂點(diǎn)，求 G中點(diǎn) u0到其它各點(diǎn)的最短路 . Dijkstra算法 (Edmonds, 1965) (2) 若 i = n1，則停；否則令 = V \Si , iS iSiS 對每個 v∈ ，令 l(v) = min {l(v)， l(ui) + w(uiv)} (1) 置 l(u0) = 0；對所有 v∈ V \{u0}，令 l(v) = ∞； S0 = {u0}， i = 0. 167。 求無向圖上的最短路的方法 并用 ui+1記達(dá)到最小值的某點(diǎn) .置 S i+1= Si∪ {u i+1}， i = i+1（表示賦值語句，以后的算法中相同），轉(zhuǎn)（ 2） . 終止后， u0 到 v 的距離由 l(v) 的終值給出 . )} ( { min v l i S v ? (3) 計(jì)算 說明： （ 1） 算法中 w(uiv) 表示邊 uiv 的權(quán)； （ 2） 若只想確定 u0到某頂點(diǎn) v0的距離， 則當(dāng)某 uj 等于 v0 時即停； （ 3） 算法稍加改進(jìn)可同時得出 u0到其它點(diǎn)的最短路 . 例 3 求圖 G 中 u0 到其它點(diǎn)的距離 . u0 7 4 2 1 5 5 8 1 3 G : 解 u0 7 4 2 1 5 5 8 1 3 ∞ ∞ ∞ ∞ ∞ （ a）初始標(biāo)號 u0 7 4 2 1 5 5 8 1 3 2 ∞ 4 ∞ 7 （ b）用與 u0關(guān)聯(lián)的邊的權(quán) 2,4,7分別更新與 u0相鄰的三個點(diǎn)的標(biāo)號 。 （ c）取小圓點(diǎn)中標(biāo)號最小者得 u1； u0 7 4 2 1 5 5 8 1 3 2 ∞ 4 ∞ 7 u1 （ d） 對與 u1相鄰的小圓點(diǎn)， 用 l (u1) + w (u1v) = 2+1 = 3 更新標(biāo)號 4； 2+5=7 更新兩個 ∞； u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 （ e）取小圓點(diǎn)中標(biāo)號 最小者得 u2. u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 u2 u4 u0 7 4 2 1 5 5 8 1 3 2 7 3 4 6 （ h） u1 u2 0 u3 u5 u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 u2 4 （ f） u0 7 4 2 1 5 5 8 1 3 2 7 3 6 u1 u2 （ g） u0 7 4 2 1 5 5 8 1 3 2 7 3 4 6 u1 u2 u3 167。 圖的距離表 在生產(chǎn)實(shí)踐中，往往需要求出一個圖的任意兩個頂點(diǎn)之間的最短路 .例如，一個鐵路局在編制他所屬的各個車站之間的運(yùn)輸里程表時，就會遇到這類問題．另外，對于不少圖論中的極值問題，往往在計(jì)算前首先必須把圖中任意兩個頂點(diǎn)之間的最短路及最短路的長度都求出來 . 要把一個圖的任意兩個頂點(diǎn)之間的最短路都求出來 ,并不困難 .例如 ,在有向圖上 ,用前面講的方法 ,計(jì)算一次就可以把從 v1到所有頂點(diǎn)的有向路都求出來了 ,接著從 v2出發(fā)，就是一開始令 v2為已標(biāo)號點(diǎn)，并且令 v2的標(biāo)號 b(2)=0，又可以把從 v2到其它各點(diǎn)的最短路求出來， …… ，這樣連續(xù)算 n次，就可以把從任意一個頂點(diǎn)到另一個頂點(diǎn)的最短路都求出來了 .對于無向圖也可以用相似的方法來解決． 以下圖為例：這個圖有 6個頂點(diǎn)，在圖 (a)到 (f)中分別畫了以為起點(diǎn)的計(jì)算結(jié)果 . v1 2 v3 v2 v4 v5 v6 3 8 5 3 4 4 4 3 7 6 圖 v1 [2] v3 v2 v4 v5 v6 [10] 3 0 [3] [6] [7] [10] 2 [15] [8] (a)起點(diǎn) v1 8 10 7 圖 v1 [5] v3 v2 v4 v5 v6 [11] 4 5 [4] [8] 0 [12] [6] (b)起點(diǎn) v2 6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1