最短路徑問題（迪傑斯特拉）算法

定義

所謂最短路徑問題是指：如果從圖中某一頂點（源點）到達另一頂點（終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權值總和（稱為路徑長度）達到最小。

Dijkstra（迪傑斯特拉）算法

他的算法思想是按路徑長度遞增的次序一步一步并入來求取，是貪心算法的一個應用，用來解決單源點到其餘頂點的最短路徑問題。

Dijkstra（迪傑斯特拉）算法示例：

第1步：初始化距離，其實指與D直接連接配接的點的距離。dis[c]代表D到C點的最短距離，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其餘為無窮大。設定集合S用來表示已經找到的最短路徑。此時，S={D}。現在得到D到各點距離{D(0)，C(3)，E（4），F（），G（），B（），A()}，其中代表未知數也可以說是無窮大，括号裡面的數值代表D點到該點的最短距離。

第2步：不考慮集合S中的值，因為dis[C]=3，是當中距離最短的，是以此時更新S，S={D,C}。接着我們看與C連接配接的點，分别有B，E，F，已經在集合S中的不看，dis[C-B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C-F]=9，dis[E]=dis[C]+dis[C-E]=3+5=8>4(初始化時的dis[E]=4)不更新。此時{D(0)，C(3)，E（4），F（9），G（），B（13），A()}。

第3步：在第2步中，E點的值4最小，更新S={D，C，E}，此時看與E點直接連接配接的點，分别有F，G。dis[F]=dis[E]+dis[E-F]=4+2=6（比原來的值小，得到更新），dis[G]=dis[E]+dis[E-G]=4+8=12（更新）。此時{D(0)，C(3)，E（4），F（6），G（12），B（13），A()}。

第4步：在第3步中，F點的值6最小，更新S={D，C，E，F}，此時看與F點直接連接配接的點，分别有B，A，G。dis[B]=dis[F]+dis[F-B]=6+7=13，dis[A]=dis[F]+dis[F-A]=6+16=22，dis[G]=dis[F]+dis[F-G]=6+9=15>12（不更新）。此時{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第5步：在第4步中，G點的值12最小，更新S={D，C，E，F，G}，此時看與G點直接連接配接的點，隻有A。dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第6步：在第5步中，B點的值13最小，更新S={D，C，E，F，G，B}，此時看與B點直接連接配接的點，隻有A。dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第7步：最後隻剩下A值，直接進入集合S={D，C，E，F，G，B，A}，此時所有的點都已經周遊結束，得到最終結果{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.