2021-09-29來源:海文考研
計(jì)算機(jī)的競爭度逐年加大,報考學(xué)生越來越多,對于打算報考2022考研計(jì)算機(jī)的考生們來說復(fù)習(xí)是難點(diǎn)。下面海文考研老師整理了2022計(jì)算機(jī)考研操作系統(tǒng)基礎(chǔ)考點(diǎn):帶權(quán)圖的最短路徑算法及應(yīng)用,一起來看看吧。
帶權(quán)圖的最短路徑算法及應(yīng)用
迪杰斯特拉(Dijkstra)算法求單源最短路徑,算法思想:
設(shè)S為最短距離已確定的頂點(diǎn)集(看作紅點(diǎn)集),V-S是最短距離尚未確定的頂點(diǎn)集(看作藍(lán)點(diǎn)集)。
1.初始化:初始化時,只有源點(diǎn)s的最短距離是已知的(SD(s)=0),故紅點(diǎn)集S=s,藍(lán)點(diǎn)集為空。
2.重復(fù)以下工作,按路徑長度遞增次序產(chǎn)生各頂點(diǎn)最短路徑,在當(dāng)前藍(lán)點(diǎn)集中選擇一個最短距離最小的藍(lán)點(diǎn)來擴(kuò)充紅點(diǎn)集,以*證算法按路徑長度遞增的次序產(chǎn)生各頂點(diǎn)的最短路徑。當(dāng)藍(lán)點(diǎn)集中僅剩下最短距離為&infin的藍(lán)點(diǎn),或者所有藍(lán)點(diǎn)已擴(kuò)充到紅點(diǎn)集時,s到所有頂點(diǎn)的最短路徑就求出來了。
注意:①若從源點(diǎn)到藍(lán)點(diǎn)的路徑不存在,則可假設(shè)該藍(lán)點(diǎn)的最短路徑是一條長度為無窮大的虛擬路徑。②從源點(diǎn)s到終點(diǎn)v的最短路徑簡稱為v的最短路徑s到v的最短路徑長度簡稱為v的最短距離,并記為SD(v)。
(注:本文來自網(wǎng)絡(luò),如有侵權(quán),請聯(lián)系刪除)
(內(nèi)容來源于網(wǎng)絡(luò),由海文考研收集整理,侵權(quán)必刪!)