本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。

dijkstra算法（單源最短路徑）

                                                       dijkstra算法（單源最短路徑）

      單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。

一.最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)

   該性質(zhì)描述為：如果P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j(luò)的最短路徑，k和s是這條路徑上的一個中間頂點，那么P(k,s)必定是從k到s的最短路徑。下面證明該性質(zhì)的正確性。

   假設(shè)P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j(luò)的最短路徑，則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)

  本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。