2021-09-29來(lái)源：海文考研
考研報(bào)名時(shí)間 自動(dòng)化考研 考研報(bào)名費(fèi) 工程造價(jià)考研 成人考研
計(jì)算機(jī)的競(jìng)爭(zhēng)度逐年加大，報(bào)考學(xué)生越來(lái)越多，對(duì)于打算報(bào)考2022考研計(jì)算機(jī)的考生們來(lái)說復(fù)習(xí)是難點(diǎn)，大家復(fù)習(xí)也需要講究方法，掌握一定的技巧。下面海文考研老師整理了計(jì)算機(jī)考點(diǎn)：帶權(quán)圖的最短路徑算法及應(yīng)用，供大家參考。
迪杰斯特拉(Dijkstra)算法求單源最短路徑，算法思想：
設(shè)S為最短距離已確定的頂點(diǎn)集(看作紅點(diǎn)集)，V-S是最短距離尚未確定的頂點(diǎn)集(看作藍(lán)點(diǎn)集)。
1.初始化：初始化時(shí)，只有源點(diǎn)s的最短距離是已知的(SD(s)=0)，故紅點(diǎn)集S={s}，藍(lán)點(diǎn)集為空。
2.重復(fù)以下工作，按路徑長(zhǎng)度遞增次序產(chǎn)生各頂點(diǎn)最短路徑，在當(dāng)前藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn)來(lái)擴(kuò)充紅點(diǎn)集，以*證算法按路徑長(zhǎng)度遞增的次序產(chǎn)生各頂點(diǎn)的最短路徑。當(dāng)藍(lán)點(diǎn)集中僅剩下最短距離為∞的藍(lán)點(diǎn)，或者所有藍(lán)點(diǎn)已擴(kuò)充到紅點(diǎn)集時(shí)，s到所有頂點(diǎn)的最短路徑就求出來(lái)了。
注意：①若從源點(diǎn)到藍(lán)點(diǎn)的路徑不存在，則可假設(shè)該藍(lán)點(diǎn)的最短路徑是一條長(zhǎng)度為無(wú)窮大的虛擬路徑。②從源點(diǎn)s到終點(diǎn)v的最短路徑簡(jiǎn)稱為v的最短路徑;s到v的最短路徑長(zhǎng)度簡(jiǎn)稱為v的最短距離，并記為SD(v)。
(注：本文來(lái)自網(wǎng)絡(luò) ，如有侵權(quán)，請(qǐng)聯(lián)系刪除)
(內(nèi)容來(lái)源于網(wǎng)絡(luò)，由海文考研收集整理，侵權(quán)必刪！)
