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），直到遍歷完所有頂點
