算法合集之淺談最短徑路問(wèn)題中的分層思想(編輯修改稿)
2024-11-14 18:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 數(shù) 城市數(shù) n是不大于 100的正整數(shù) 道路數(shù) m是不大于 10000的正整數(shù) 每條道路的長(zhǎng)度是不大于 100的正整數(shù) 每條道路的通行稅是不大于 100的非負(fù)整數(shù)。 分析 — 圖 我們把城市看成節(jié)點(diǎn)，城市之間的道路看成邊。 本題與一般求最短路的問(wèn)題相比，不同之處在于邊上有費(fèi)用、距離兩個(gè)權(quán)值。 1 5 4 2 3 6 2， 3 2， 4 3， 2 4， 1 3， 3 2， 0 2， 1 分析 — 算法一 — 分層 把圖拆分成 k+1層，表示到達(dá)該層頂點(diǎn)所需的費(fèi)用分別為0到 k。 2， 3 2， 4 3， 2 4， 1 3， 3 2， 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1