圖論旅行商ppt課件(編輯修改稿)
2025-06-02 23:19 本頁面
【文章內(nèi)容簡介】 當(dāng) vi在 S中時 d(i)是 v1到 vi的最短路的長度。 13 Dijkstra 算法 ： 1) 讓 d(1):=0, S:={1}, k:=1, E:=Φ。 d(i)=w1i, i = 2, 3, …,n. ( 若圖中邊 (vi,vj)不存在，則記 wij =∞) 2) 在 S以外的所有點中找標(biāo)號最小的點： d(k0)=min {d(j): vj不在 S中 } 。 3) S:=S∪ {k0},k:= k0, E:=E∪ {ek0}(為取到值 d(k0)的邊 ),并修改與 vk0相鄰的點的標(biāo)號： d(j):=min {d(j), d(k)+wkj}, j?S. 若 |S|=n，則終止迭代；否則回到第 2步。 (注意理解 j?S時標(biāo)號 d(j)的含義 ) 14 對本算法的理解及算法正確性的證明： (實線表示圖中 一條邊 ，虛線表示若干條邊組成的 一條路 ) v1 S vk0 S 15 例 求 v1到其它各點的最短路。 v1 v6 v3 v5 v4 v2 7 3 1 6 4 5 3 7 2 1 令 d(v1)=0, 則 (紅點集合表示 S): vi v1 v2 v3 v4 v5 v6 d(vi) 0 6 1 8 3 8 vi v1 v2 v3 v4 v5 v6 d(vi) 0 7 1 ∞ ∞ ∞ vi v1 v2 v3 v4 v5 v6 d(vi) 0 6 1 8 3 7 vi v1 v2 v3 v4 v5 v6 d(vi) 0 6 1 8 3 8 vi v1 v2 v3 v4 v5 v6 d(vi) 0 7 1 ∞ 3 8 16 3. 權(quán)均為 1時最短路問題的求解 因為是正權(quán)圖，故可直接采用 Dijkstra方法。但此時情況特殊， Dijkstra算法可以簡化： 每輪迭代有一批結(jié)點標(biāo)號相同，讓它們都進(jìn)入 S；修改它們的全部直接后繼結(jié)點的標(biāo)號（均相等），故下一次讓這一批結(jié)點全部進(jìn)入 S； … 。 總之， 每輪讓一批結(jié)點進(jìn)入 S后，其全部直接后繼結(jié)點將成為下一輪進(jìn)入 S的全部結(jié)點。反復(fù)這一操作，直到 |S|=n為止。 17 v1 v6 v3 v5 v4 v2 1 1 1 1 1 1 1 1 1 1 例 求 v1到其它各點的最短路。 令 d(v1)=0, 則 (紅點集合表示 S): vi v1 v2 v3 v4 v5 v6 d(vi) 0 1 1 ∞ ∞ ∞ vi v1 v2 v3 v4 v5 v6 d(vi) 0 1 1 2 2 2 vi v1 v2 v3 v4 v5 v6 d(vi) 0 1 1 2 2 2 18 2. 權(quán)有負(fù)數(shù)時最短路問題的求解 —— Ford 算法 權(quán)有負(fù)數(shù)時 Dijkstra算法失效。 ( 為什么
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1