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