考研報名時間 自動化考研 考研報名費 工程造價考研 成人考研

計算機的競爭度逐年加大，報考學(xué)生越來越多，對于打算報考2022考研計算機的考生們來說復(fù)習(xí)是難點，大家復(fù)習(xí)也需要講究方法，掌握一定的技巧。下面海文考研老師整理了計算機考點：帶權(quán)圖的最短路徑算法及應(yīng)用，供大家參考。

迪杰斯特拉(Dijkstra)算法求單源最短路徑，算法思想：

設(shè)S為最短距離已確定的頂點集(看作紅點集)，V-S是最短距離尚未確定的頂點集(看作藍(lán)點集)。

1.初始化：初始化時，只有源點s的最短距離是已知的(SD(s)=0)，故紅點集S={s}，藍(lán)點集為空。

2.重復(fù)以下工作，按路徑長度遞增次序產(chǎn)生各頂點最短路徑，在當(dāng)前藍(lán)點集中選擇一個最短距離最小的藍(lán)點來擴充紅點集，以*證算法按路徑長度遞增的次序產(chǎn)生各頂點的最短路徑。當(dāng)藍(lán)點集中僅剩下最短距離為∞的藍(lán)點，或者所有藍(lán)點已擴充到紅點集時，s到所有頂點的最短路徑就求出來了。

注意：①若從源點到藍(lán)點的路徑不存在，則可假設(shè)該藍(lán)點的最短路徑是一條長度為無窮大的虛擬路徑。②從源點s到終點v的最短路徑簡稱為v的最短路徑;s到v的最短路徑長度簡稱為v的最短距離，并記為SD(v)。

(注：本文來自網(wǎng)絡(luò) ，如有侵權(quán)，請聯(lián)系刪除)

計算機

(內(nèi)容來源于網(wǎng)絡(luò)，由海文考研收集整理，侵權(quán)必刪！)

上一篇： 2022計算機考研之各類排序算法的特點及比較

下一篇： 2023金融碩士考研輔導(dǎo)之存款擔(dān)保制度