計算機的競爭度逐年加大,報考學生越來越多,對於打算報考2022考研計算機的考生們來說複習是難點。下面小編整理了2022計算機考研作業系統基礎考點:帶權圖的最短路徑算法及應用,一起來看看吧。
帶權圖的最短路徑算法及應用
迪傑斯特拉(Dijkstra)算法求單源最短路徑,算法思想:
設S為最短距離已確定的頂點集(看作紅點集),V-S是最短距離尚未確定的頂點集(看作藍點集)。
1.初始化:初始化時,只有源點s的最短距離是已知的(SD(s)=0),故紅點集S=s,藍點集為空。
2.重複以下工作,按路徑長度遞增次序產生各頂點最短路徑,在當前藍點集中選擇一個最短距離最小的藍點來擴充紅點集,以保證算法按路徑長度遞增的次序產生各頂點的最短路徑。當藍點集中僅剩下最短距離為&infin的藍點,或者所有藍點已擴充到紅點集時,s到所有頂點的最短路徑就求出來了。
注意:①若從源點到藍點的路徑不存在,則可假設該藍點的最短路徑是一條長度為無窮大的虛擬路徑。②從源點s到終點v的最短路徑簡稱為v的最短路徑s到v的最短路徑長度簡稱為v的最短距離,並記為SD(v)。
帶權圖的最短路徑算法及應用
迪傑斯特拉(Dijkstra)算法求單源最短路徑,算法思想:
設S為最短距離已確定的頂點集(看作紅點集),V-S是最短距離尚未確定的頂點集(看作藍點集)。
1.初始化:初始化時,只有源點s的最短距離是已知的(SD(s)=0),故紅點集S=s,藍點集為空。
2.重複以下工作,按路徑長度遞增次序產生各頂點最短路徑,在當前藍點集中選擇一個最短距離最小的藍點來擴充紅點集,以保證算法按路徑長度遞增的次序產生各頂點的最短路徑。當藍點集中僅剩下最短距離為&infin的藍點,或者所有藍點已擴充到紅點集時,s到所有頂點的最短路徑就求出來了。
注意:①若從源點到藍點的路徑不存在,則可假設該藍點的最短路徑是一條長度為無窮大的虛擬路徑。②從源點s到終點v的最短路徑簡稱為v的最短路徑s到v的最短路徑長度簡稱為v的最短距離,並記為SD(v)。
收藏