1、算法定義
Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。注意該算法要求圖中不存在負(fù)權(quán)邊。
2、算法描述
設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。
無向圖
3、算法演示：
（1）初始時，S只包含起點D；U包含除D外的其他頂點，且U中頂點的距離為“起點D到該頂點的距離”（例如，U中頂點A的距離為[D,A]的長度，然后D和A不相鄰，則A的距離為∞）
（2）從U中選出“距離最短的頂點K”，并將頂點K加入到S中；同時，從U中移除頂點K
（3）更新U中各個頂點到起點D的距離。之所以更新U中頂點的距離，是由于上一步中確定了K是求出最短路徑的頂點，從而可以利用K來更新其他頂點到起點D的距離（例如，[D,A]的距離可能大于[D,K]+[K,A]的距離）
（4）重復(fù)步驟（2）和（3），直到遍歷完所有頂點
算法演示
