圖論的基本算法(編輯修改稿)
2024-10-27 15:10 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ray[1..maxn] of integer。 ?根結(jié)點(diǎn) root滿足 father[root] := root ?查找： while father[p] p do p := father[p]。 ……? ?合并： if height(p1) height(p2) then father[p1] := p2 Kruskal算法框架 把所有邊按照權(quán)值從小到大排序?yàn)?e1,e2,… 初始化 n個(gè)集合， Si={i} size := 0。 for i:=1 to m do if ei的兩個(gè)端點(diǎn) u, v不在同一個(gè)集合 then begin 合并 Su和 Sv inc(size)。 if size = n – 1 then break。 end。 ? 最壞情況循環(huán)執(zhí)行 m次，判斷約 O(1) ? 如果輸入已經(jīng)排序好，則總時(shí)間復(fù)雜度為 O(m)，否則為O(mlogm) 最短路問題 ? 問題描述：給加權(quán)圖 G ?SSSP：求給定起點(diǎn) s到其他所有點(diǎn)的最短路 ?APSP：求每?jī)蓪?duì)點(diǎn)的最短路 ? 算法 ?標(biāo)號(hào)設(shè)定類： dijkstra ?標(biāo)號(hào)修正類： bellmanford ?動(dòng)態(tài)規(guī)劃類： floydwarshall ?變形與應(yīng)用舉例 SSSP (Dijkstra算法 ) ? 核心思想：按路徑遞增的次序產(chǎn)生最短路徑的算法 1)找到圖中最短的路徑，設(shè)為（ v,vj） ,將 j設(shè)為已標(biāo)號(hào)的點(diǎn) 2)找下一條次短的路徑，假設(shè)終點(diǎn)為 k,將 k設(shè)為已標(biāo)號(hào)的點(diǎn) ,那么要么是（ v,vk）要么是（ v,vj,vk） ,若經(jīng)過 vj ,將 j設(shè)為已檢查的點(diǎn) ,放入集合 . 3)以次短路徑出發(fā)找第三短的路徑 ,類似第二步的方法 . 4)按上述方法一直到所有的頂點(diǎn)被檢查過 ,則從 v到其他頂點(diǎn)的最短路徑求出 . PROC short_DIJ(da:adjmatrix。v0:vtxptr) var dist:array[vtxptr] of weighttype。 {存儲(chǔ)路徑長(zhǎng)度 } path:array[vtxptr] of set。 {存儲(chǔ)路徑 } for i:=1 to vxtmun do [dist[i]:=[v0,i]。 if dist[i]max then path[i]:=[v0]+[i] else path[i]:=[]。 s:=[v0]。 {s存儲(chǔ)被標(biāo)號(hào)的頂點(diǎn) } for k:=1 to vtxnum1 do [ wm:=max。 j:=v0。 for i:=1 to vtxnum do if not (i in s) and (dist[i]wm) then [ j:=i。wm:=dist[i] ] s:=s+[j] for i:=1 to vtxnum do if not (i in s) and (dist[j]+[j,i]wm then [ dist[i]:=dist[j]+[j,i]。 path[i]:=path[j]+path[i] ] ] endP Car的旅行路線 ? 又到暑假了，住在城市 A的 Car想和朋友一起去城市 B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場(chǎng)，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市中兩個(gè)機(jī)場(chǎng)之間有一條筆直的高速鐵路，第 i個(gè)城市中高速鐵路的單位里程價(jià)格為 Ti，任意兩個(gè)不同城市的機(jī)場(chǎng)之間均有航線，所有航線單位里程的價(jià)格均為 t。 ? 那么 Car應(yīng)如何安排到城市 B的路線才能盡可能的節(jié)省花費(fèi)昵？她發(fā)現(xiàn)這并不是一個(gè)簡(jiǎn)單的問題，于是她來(lái)向你請(qǐng)教。 約束條件 輸入 ? 第一行為一個(gè)正整數(shù) n(0≤n≤10)，表示有 n組測(cè)試數(shù)據(jù)。 每組的第一行有四個(gè)正整數(shù) s， t， A， B。 ? s（ 0＜ S≤100）表示城市的個(gè)數(shù)， t表示飛機(jī)單位里程的價(jià)格， A， B分別為城市 A， B的序號(hào)，（ 1≤A， B≤S）。 接下來(lái)有 s行，其中第 i行均有 7個(gè)正整數(shù) xi1， yi1， xi2，yi2， xi3， yi3， Ti，這當(dāng)中的 (xi1， yi1)， (xi2， yi2)， (xi3，yi3)分別是第 I個(gè)城市中任意三個(gè)機(jī)場(chǎng)的坐標(biāo)， Ti為第 i個(gè)城市高速鐵路單位里程的價(jià)格。 輸出 共有 n行，每行一個(gè)數(shù)據(jù)對(duì)應(yīng)測(cè)試數(shù)據(jù)。 分析 計(jì)算兩點(diǎn)間的歐氏距離 計(jì)算每個(gè)機(jī)場(chǎng)的坐標(biāo)序列 使用 Dijkstra算法計(jì)算最小費(fèi)用 SSSP：權(quán)非負(fù)的情形 ? 求 1到所有點(diǎn)的距離 ? d[1] = 0 ? d[2] = 3, d[4] = 4 ? d[2] = 3. 為什么？ ?每次固定 d的最小值 ? 標(biāo)號(hào)設(shè)定！ ? 怎樣取最小值？堆！ ? 名稱： dijkstra ?和 Prim算法很類似 ? Prim: 邊最小值 ? dijkstra: d最小值 ? 中間結(jié)果：最短路樹！ ?時(shí)間復(fù)雜度 O((m+n)logm) 12433432一個(gè)例子 ? 給出一個(gè)帶權(quán)無(wú)向圖 G ?邊權(quán)為 1…1 00
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1