迪杰斯特拉算法
一、定义Dijkstra算法（迪杰斯特拉算法）是很有代表性的最短路径算法，用于计算一个结点到其他结点的最短路径。该算法指定一个点（源点）到其余各个结点的最短路径，因此也叫做单源最短路径算法。该算法是由荷兰计算机科学家Edsger W.Dijkstra于1959年发表。
Dijkstra算法是一种用于计算带权有向图中单源最短路径算法，不存在回溯的过程，因此它还不适用于带有负权重的情况。如果权值存在负数，那么被派生出来的可能是更短的路径，这就需要过程可以回溯，之前的路径需要被更短的路径替换掉，而Dijkstra算法是不能回溯的，它的每一步都是以当前最优选择为前提的。
Dijkstra算法的思想是广度优先搜索（BFS） 贪心策略。对于计算非加权图中的最短路径，也可使用BFS算法。Dijkstra算法是对BFS算法的推广，以起始点为中心向外层层扩展，并且每一次都选择最优的结点进行扩展，直到扩展到终点为止。Dijkstra算法可以划归为贪心算法，下一条路径都是由当前更短的路径派生出来的更长的路径。
Dijkstra算法在很多专业课程中都作为基本内容有详细的介绍，如数据结构、图论、运筹学等。
二、演示例子例子1
第1步，创建距离表。第1列是结点名称，第2列是从起点A到对应结点的已知最短距离。开始我们并不知道A到其它结点的最短距离是多少，默认初始距离是无穷大。如图2-1-1所示：
图2-1-1
第2步，遍历起点A的所有相邻结点，找到起点A的邻接结点B和C。从A到B的距离是5，从A到C的距离是2，刷新距离表中起点A到各结点的最短距离(绿色表示刷新)。如图2-1-2所示。
图2-1-2
第3步，从图2-1-2距离表中找到从A出发距离最短的点，也就是结点C（最小距离是2）。遍历结点C的所有相邻结点，找到结点C的相邻结点D和F（A已经遍历过，不需要考虑）。从C到D的距离是1，所以A到D的距离是A-C-D=2 1=3；从C到F的距离是8；从A到F的距离是A-C-F=2 8=10。然后刷新距离表(绿色表示刷新)。如图2-1-3所示：
图2-1-3
第4步，从图2-1-3距离表中找到从A出发距离最短的点（红色结点C已经遍历过，不需要考虑），也就是结点D（最小距离是3）。遍历结点D的所有相邻结点，找到相邻结点B、E和F（C已遍历过，不考虑）。从A-C-D-B的距离是3 1=4；从A-C-D-E的距离是3 1=4；从A-C-D-F的距离是3 2=5。刷新距离表中起点A到各结点的最短距离。如图2-1-4所示。
图2-1-4
第5步，从图2-1-4距离表中找到从A出发距离最短的点（红色结点C、D已经遍历过，不需要考虑），也就是结点B和E（最小距离是4）。遍历结点B的所有相邻结点，找到相邻结点E(D遍历过，不考虑),从A-C-D-B-E的距离为10，比当前A到E的最小距离4要大，不考虑。遍历结点E的所有相邻结点，找到相邻结点G、B(D遍历过，不考虑),从A-C-D-E-G的距离为4 7=11∞, 刷新距离表;A-C-D-E-B的距离4 6=104,不考虑。如图2-1-5所示。
图2-1-5
第6步，从图2-1-5距离表中找到从A出发距离最短的点（红色结点B、C、D、E已经遍历过，不需要考虑），也就是结点F（最小距离是5）。从A-C-D-F-G的距离为8, 比当前最小距离11要小，刷新距离表。如图2-1-6所示。
图2-1-6
就这样，除终点以外的全部结点都已经遍历完毕，距离表中存储的是从起点A到所有结点的最短距离。
例子2
图2-2-1是原始连通图。
图2-2-1
用Dijkstra算法找出以A为起点的单源最短路径步骤如下：
步骤
集合S
集合Q
1
选择A到集合S={A}
此时最短路径A-A=0
以A为中间点，查找相邻点
Q={B,C,D,E,F,G}
A--B=5
A-C=2
A-其它Q中结点=∞
发现A-C=2权值为最短
2
选择C到S={A,C}
此时最短路径A-A=0,A-C=2
以C为中间点，从A-C这条路径开始找
Q={B,D,E,F,G}
A-B=5(由第1步得到)
A-C-D=3
A-C-F=10
A-C-其它Q中结点=∞
在A到Q的结点中，发现A-C-D=3权值为最短
3
选择D到S={A,C,D}
此时最短路径A-A=0,A-C=2,A-C-D=3,
以D为中间点，从A-C-D这条路径开始找
Q={B,E,F,G}
A-C-D-B=4(比第1步的A-B=5要短，替换之)
A-C-D-E=4
A-C-D-F=5(比第2步的A-C-F=10要短，替换之)
A-C-D-G=∞
在A到Q的结点中，发现A-C-D-B=4或A-C-D-E=4权值为最短
4
选择B、E到S={A,C,D,B,E}
此时最短路径A-A=0,A-C=2,A-C-D=3,A-C-D-B=4,A-C-D-E=4,
以B、E为中间点，分别从A-C-D-B、从A-C-D-E路径开始找
Q={F,G}
A-C-D-E-G=11
A-C-D-F=5(从第3步获得)
在A到Q的结点中，发现A-C-D-F权值为最短
5
选择F到S={A,C,D,B,E,F}
此时最短路径A-A=0,A-C=2,A-C-D=3,A-C-D-B=4,A-C-D-E=4,A-C-D-F=5
以F为中间点，从,A-C-D-F这条路径开始找
Q={G}
A-C-D-F-G=8(比第4步的A-C-D-E-G=11要短，替换之)
6
选择G到S={A,C,D,B,E,F,G}
此时最短路径A-A=0,A-C=2,A-C-D=3,A-C-D-B=4,A-C-D-E=4,A-C-D-F=5,A-C-D-F-G=8
集合Q为空，查找完毕。
例子3
Dijkstra算法的执行过程：设初始集合S={s}, Q={t,y,x,z}. 源结点s为最左边的结点，每个结点中（圆圈中）的数值为该结点的最短路径的估计值（当前中间值）。黑色的结点属于集合S，白色的结点属于集合Q。每次从集合 S中选择最新加入的结点，分别计算并刷新与它直接相邻的结点的最短路径的估计值，然后从集合Q中选择最小估计值的结点，加入到集合S中。例如(b)中，集合Q中刷新后各结点的估计值为10，5，∞，∞，选择最小估计值为5的结点y，加入到集合S中, 接着计算并刷新结点y的相邻结点的最短路径的估计值。依次类推，直到集合Q中的所有结点全部加入到集合S中，算法结束。如图2-3-1所示。
图2-3-1
三、应用
一切能抽象成图或树的场景，如果要求最短路径，Dijkstra算法可考虑。比如，查找两个城市之间的最短路径；在地图中寻找两个地点之间的最短路径；在网络连接中为路由器寻找最短的传输路径等。
绛旓細瀹氫箟Dijkstra(杩澃鏂壒鎷)绠楁硶鏄吀鍨嬬殑鍗曟簮鏈鐭矾寰勭畻娉,鐢ㄤ簬璁＄畻涓涓妭鐐瑰埌鍏朵粬鎵鏈夎妭鐐圭殑鏈鐭矾寰銆備富瑕佺壒鐐规槸浠ヨ捣濮嬬偣涓轰腑蹇冨悜澶栧眰灞傛墿灞,鐩村埌鎵╁睍鍒扮粓鐐逛负姝侱ijkstra绠楁硶鏄緢鏈変唬琛ㄦх殑鏈鐭矾寰勭畻娉,鍦ㄥ緢澶氫笓涓氳绋嬩腑閮戒綔涓哄熀鏈唴瀹规湁璇︾粏鐨勪粙缁,濡傛暟鎹粨鏋,鍥捐,杩愮瀛︾瓑绛夈侱ijkstra涓鑸殑琛ㄨ堪閫氬父鏈変袱绉嶆柟寮,涓绉...
绛旓細Dijkstra杩澃鏂壒鎷夋槸涓绉嶅鐞嗗崟婧愮偣鐨勬渶鐭矾寰勭畻娉,灏辨槸璇存眰浠庢煇涓涓妭鐐瑰埌鍏朵粬鎵鏈夎妭鐐圭殑鏈鐭矾寰勫氨鏄疍ijkstra銆 璧勬枡鎷撳睍: 杩澃鏂壒鎷夌畻娉(Dijkstra)鏄敱鑽峰叞鏁拌厰璁＄畻鏈虹瀛﹀鐙勫厠鏂壒鎷変簬1959骞存彁鍑虹殑,鍥犳鍙堝彨鐙勫厠鏂壒鎷夌畻娉曘傛槸浠庝竴涓《鐐瑰埌鍏惰柉绾宠～浣欏悇椤剁偣鐨勬渶鐭矾寰勭畻娉,瑙ｅ喅鐨勬槸鏈夋潈鍥句腑鏈鐭矾寰勯棶棰樸
绛旓細1銆佺洰鐨勪笉鍚岋細杩澃鏂壒鎷夌畻娉曚富瑕佽В鍐冲崟婧愭渶鐭矾寰勯棶棰锛屽嵆浠庢寚瀹氱殑涓涓妭鐐瑰紑濮嬶紝鎵惧嚭鍥句腑浠庤妭鐐瑰埌鎵鏈夊叾浠栬妭鐐圭殑鏈鐭矾寰勶紝鑰屾櫘閲屽绠楁硶鍒欑敤浜庤В鍐虫渶灏忕敓鎴愭爲闂锛屽嵆鍦ㄨ繛閫氬浘涓夋嫨涓浜涜竟锛屼娇寰楄繖浜涜竟鏋勬垚鐨勫瓙鍥句粛鐒惰繛閫氾紝骞朵笖鎵鏈夎竟鐨勬潈閲嶄箣鍜屾渶灏忋2銆佹牳蹇冩濇兂涓嶅悓锛氳开鏉版柉鐗规媺绠楁硶姣忔浠庢湭琚闂繃鐨...
绛旓細杩澃鏂壒鎷夌畻娉曠敤鏉ヨВ鍐充粠椤剁偣v0鍑哄彂鍒板叾浣欓《鐐圭殑鏈鐭矾寰锛岃绠楁硶鎸夌収鏈鐭矾寰勯暱搴﹂掑鐨勯『搴忎骇鐢熸墍浠ユ渶鐭矾寰勩傚浜庡浘G=锛圴锛孍锛夛紝灏嗗浘涓殑椤剁偣鍒嗘垚涓ょ粍锛氱涓缁凷锛氬凡姹傚嚭鐨勬渶鐭矾寰勭殑缁堢偣闆嗗悎锛堝紑濮嬩负锝泇0}锛夈傜浜岀粍V-S锛氬皻鏈眰鍑烘渶鐭矾寰勭殑缁堢偣闆嗗悎锛堝紑濮嬩负V-{v0}鐨勫叏閮ㄧ粨鐐癸級銆傚爢浼樺寲 ...
绛旓細杩澃鏂壒鎷夌畻娉(Dijkstra)鏄敱鑽峰叞璁＄畻鏈虹瀛﹀ 鐙勫厠鏂壒鎷 浜1959 骞存彁鍑虹殑锛屽洜姝ゅ張鍙 鐙勫厠鏂壒鎷夌畻娉 銆傛槸浠庝竴涓《鐐瑰埌鍏朵綑鍚勯《鐐圭殑 鏈鐭矾寰 绠楁硶锛岃В鍐崇殑鏄湁鏉冨浘涓渶鐭矾寰勯棶棰樸傝开鏉版柉鐗规媺绠楁硶涓昏鐗圭偣鏄互璧峰鐐逛负涓績鍚戝灞傚眰鎵╁睍锛岀洿鍒版墿灞曞埌缁堢偣涓烘銆傛暡榛戞澘~杩涘叆姝ｉ 杩澃鏂壒鎷夌畻娉曟槸鐩墠 ...
绛旓細璐績鍜屽姩褰掍笉鏄簰鏂ョ殑锛岃屾槸鍖呭惈鐨勶紝璐績鏇村揩锛屼絾绾︽潫鏇村己锛岄傚簲鑼冨洿鏇村皬銆傚姩褰掑拰bfs鐨勫叧绯讳篃鏄竴鏍风殑銆傚睍寮涓鐐硅锛屽湪姹傝В鏈浼樺寲闂鏃讹紝鏈夊涓В銆傝屾眰瑙ｇ殑杩囩▼绫讳技涓涓爲锛屾垜浠О涔嬩负姹傝В鏍戙備竴鑸殑姹傝В鏍戠湡鐨勬槸涓妫垫爲锛屾墍浠ユ垜浠彧鑳界敤bfs鏉ユ悳绱紝椤跺鍓灊銆傛湁浜涚壒娈婄殑姹傝В鏍戯紝涓棿寰堝缁撶偣鏄...
绛旓細杩澃鏂壒鎷(Dijkstra)绠楁硶鏍稿績锛 鎸夌収璺緞闀垮害閫掑鐨勬搴忎骇鐢熸渶鐭矾寰勩傝开鏉版柉鐗规媺(Dijkstra)绠楁硶姝ラ锛氾紙姹傚浘涓璿0鍒皏8鐨勬渶鐭矾寰勶級骞堕潪涓涓嬪瓙姹傚嚭v0鍒皏8鐨勬渶鐭矾寰勶紝鑰屾槸 涓姝ヤ竴姝ユ眰鍑哄畠浠箣闂撮《鐐圭殑鏈鐭矾寰 锛岃繃杩囩▼涓兘鏄 鍩轰簬宸茬粡姹傚嚭鐨勬渶鐭矾寰勭殑鍩虹涓婏紝姹傚緱鏇磋繙椤剁偣鐨勬渶鐭矾寰勶紝鏈缁堝緱鍑烘簮...
绛旓細P绠楁硶鏄厛閫夊嚭涓涓偣鍔犲叆鐢熸垚鏍,鐒跺悗鎵惧拰杩欎釜鐢熸垚鏍戠浉杩炵殑杈逛腑鏈鐭殑涓鏉,鍔犲叆鐢熸垚鏍.鐩村埌鍏ㄩ儴鐐归兘琚寘鎷.閮芥槸璐績绠楁硶.鍖哄埆鏄,D绠楁硶瀹炵幇鏃朵笉闇瑕佽冭檻宸叉湁鐨勭敓鎴愭爲鏄粈涔堟牱瀛愮殑,浣嗘槸瑕佽冭檻涓鏉¤竟鐩歌繛鐨勪袱涓偣鏄笉鏄湪鍚屼竴涓繛閫氬潡涓,杩欑偣鍙互鐢ㄥ苟鏌ラ泦瀹炵幇.P绠楁硶涓嶉渶瑕佽冭檻鎵鏈夌殑杈,浣嗘槸闇瑕"鍔ㄦ...
绛旓細杩澃鏂壒鎷夌畻娉锛氶傜敤浜庢眰鍥句腑鏌愪竴鑺傜偣鍒板叾浠栨墍鏈夎妭鐐圭殑鏈鐭矾寰勩傛楠わ細1銆佸皢璧风偣鍔犲叆宸茶闂泦鍚堜腑锛2銆佸璧风偣鐨勬瘡涓湭琚闂繃鐨勯偦灞呰妭鐐癸紝鍒嗗埆璁＄畻鍒拌繖浜涢偦灞呰妭鐐圭殑鏈鐭矾寰勶紱3銆佸鏋滆繖浜涢偦灞呰妭鐐逛腑瀛樺湪宸茬粡琚闂繃鐨勮妭鐐癸紝鍒欏皢杩欎簺閭诲眳鑺傜偣鍔犲叆宸茶闂泦鍚堜腑锛4銆侀噸澶嶆楠2鍜3锛岀洿鍒版墍鏈夎妭鐐归兘琚亶鍘...
绛旓細璐績銆侱ijkstral鐨勫喅绛栨槸閫夊彇褰撳墠Dist涓渶灏忕殑鏉ユ洿鏂般傚洜涓轰笉浼氭湁鍏朵粬鐐圭殑Dist姣斿畠鏇村皬锛屼篃灏变笉鑳芥潵鏇存柊瀹冦傦紙涔熷氨鏄綋鍓嶈繖涓偣宸茬粡琚墍鏈夊彲鏇存柊瀹冪殑鐐规洿鏂板畬浜嗭級杩欎篃鏄疍ijkstral涓嶈兘姹傛渶闀胯矾鐨勫師鍥犮傚洜涓哄厛閫夊彇浜嗕竴鏉Ist鏈澶х殑锛屼笉鑳戒繚璇佷箣鍚庡氨娌℃湁鐐圭殑Dist鏇村ぇ銆
