考研復習重點解析：圖的應用(編輯修改稿)
2025-04-04 07:04 本頁面
【文章內(nèi)容簡介】 [j]=∞（計算機上用一個允許的最大值代替）。S為已經(jīng)找到的從Vs出發(fā)的最短路徑的終點集合，它初始化為空集。那么，從Vs出發(fā)到圖上其余各頂點（終點）Vi可能達到的最短路徑長度的初值為：D[i]=deges[s][i] Vi∈V ?。?）選擇Vj，使得D[j]=Min{D[i]|Vi∈VS}，Vj就是當前求得的一條從Vs出發(fā)的最短路徑的終點。令S=S∪{Vj} ?。?）修改從Vs出發(fā)到集合VS上任一頂點Vk可達的最短路徑長度。如果D[j]+edges[j][k]D[k]則修改D[k]為D[k]=D[j]+edges[j][k] 重復操作(2)(3)共n1次。由此求得從Vs到圖上其余各頂點的最短路徑。 2．Floyd算法 Floyd算法的核心思想是通過一個圖的權值
環(huán)評公示相關推薦
鄂ICP備17016276號-1