數(shù)理與信息工程學(xué)院(編輯修改稿)
2025-07-22 07:24 本頁面
【文章內(nèi)容簡介】 Dijkstra 的一種改進算法 ,克服了原算法的不足之處 ,能夠快速地求出一個頂點到其它各頂點的所有最短路徑。算法與實例為了敘述方便 ,首先引入以下記號并作相應(yīng)的約定：(1)A表示圖G的鄰接矩陣；(2)S表示已找到從出發(fā)的最短路徑的終點集合；(3)向量D的每個分量 D[i]表示從始點到每個終點的最短路徑的長度；(4) Succ(u)表示 u的后繼結(jié)點組成的集合。設(shè)簡單加權(quán)圖 G= V , E,W (無向圖或有向圖) , 則求頂點到其它各頂點的所有最短路徑的算法描述如下：(1)初始化 S 及 D。(2)選取,使得 ,令。(3)修改從出發(fā)到集合上任一結(jié)點可達的最短路徑長度。如果 D[j] + A[j][k] D[k],則修改 D[k]為：D[k] = D[j] + A[j][k]。(4)重復(fù)操作(2) 、(3) 共 n 1 次,求得從到其余各
法律信息相關(guān)推薦
鄂ICP備17016276號-1