求助关于Dijkstra算法问题 如下图 关于Dijkstra算法的小问题！
\u6709\u4e00\u4e2a\u5173\u4e8eDijkstra\u7b97\u6cd5\u7684\u7591\u95ee\uff0c\u6c42\u5927\u795e\u8be6\u7ec6\u89e3\u7b54\uff0c\u8c22\u8c22\uff01\uff01\uff01\u5982\u56fe\u6240\u793a\uff0c\u8def\u7531\u5668R2\u548cR3\u5230\u7f51\u7edcN\u4f60\u6ca1\u6709\u770b\u89c1\u4ed6\u4eec\u7684\u4ee3\u4ef7\u4e0d\u540c\u5417\uff1a\u4eceR2-N3-R3\u662f2+2=4\uff0c\u800cR2-N2-R3\u662f1+1=2\uff0c\u80af\u5b9a\u662f\u8d70\u4ee3\u4ef7\u5c0f\u7684\u8def\u7ebf\u4e86\u3002
\u4f60\u518d\u597d\u597d\u770b\u770b\u7b97\u6cd5\uff0c\u5b83\u5e76\u4e0d\u662f\u6bcf\u6b21\u9009\u53d6\u4e00\u6761\u6700\u5c0f\u4ee3\u4ef7\u7684\u8def\u5f84\u6269\u5c55\uff0c\u800c\u662f\u8981\u7b97\u4e0a\u5f53\u524d\u8282\u70b9\u7684\u4ee3\u4ef7\u7684\u3002\u4eces\u5230c\u7684\u4ee3\u4ef7\u4e3a3\uff0c\u56e0\u6b64\u4e0d\u4f1a\u9009\u62e9c\u5230e\u8fd9\u6761\u8def\u5f84\uff0c\u800c\u662f\u9009\u62e9s\u5230e\u3002
这个应该是看以怎样的顺序进行查找来决定，例如您表示A到各点的距离的数组顺序是A、B、C、D、E、F若您通过顺序查找来获取当前最小距离的结点，则会先C后D，若您反序查找则会是先D后C，这个对最终的求得的结果没有影响。
最先添加的分别是E和B没错。
当存在A->C和A->E->D时，需要注意的是，题目要求的最短路径是从A开始，所以到达D的距离是2+6=8，而不是6，所以这里应该新增的是C而不是D。
绛旓細Dijkstra绠楁硶鏄敱鑽峰叞璁＄畻鏈虹瀛﹀鐙勫厠鏂壒鎷夛紙Dijkstra锛変簬1959骞存彁鍑虹殑锛屽洜姝ゅ張鍙媱鍏嬫柉鐗规媺绠楁硶銆傛槸浠庝竴涓《鐐瑰埌鍏朵綑鍚勯《鐐圭殑鏈鐭矾寰勭畻娉曪紝瑙ｅ喅鐨勬槸鏈夊悜鍥句腑鏈鐭矾寰勯棶棰樸傚叾鍩烘湰鍘熺悊鏄細姣忔鏂版墿灞曚竴涓窛绂绘渶鐭殑鐐癸紝鏇存柊涓庡叾鐩搁偦鐨勭偣鐨勮窛绂汇傚綋鎵鏈夎竟鏉冮兘涓烘鏃讹紝鐢变簬涓嶄細瀛樺湪涓涓窛绂绘洿鐭殑娌℃墿灞...
绛旓細鏈鐭矾寰勯棶棰樻槸鍥捐鐮旂┒涓竴涓粡鍏哥畻娉曢棶棰橈紝鏃ㄥ湪瀵绘壘鍥句腑涓よ妭鐐规垨鍗曚釜鑺傜偣鍒板叾浠栬妭鐐逛箣闂寸殑鏈鐭矾寰勩傛牴鎹棶棰樼殑涓嶅悓锛岀畻娉曠殑鍏蜂綋褰㈠紡鍖呮嫭锛氬父鐢ㄧ殑鏈鐭矾寰勭畻娉曞寘鎷細Dijkstra绠楁硶锛孉 绠楁硶锛孊ellman-Ford绠楁硶锛孲PFA绠楁硶锛圔ellman-Ford绠楁硶鐨勬敼杩涚増鏈級锛孎loyd-Warshall绠楁硶锛孞ohnson绠楁硶浠ュ強Bi-direction BFS...
绛旓細[闂鍒嗘瀽]瀵逛簬涓涓惈鏈塶涓《鐐瑰拰e鏉¤竟鐨勫浘鏉ヨ锛屼粠鏌愪竴涓《鐐筕i鍒板叾浣欎换涓椤剁偣Vj鐨勬渶鐭矾寰勶紝鍙兘鏄畠浠箣闂寸殑杈癸紙Vi锛孷j锛夛紝涔熷彲鑳芥槸缁忚繃k涓腑闂撮《鐐瑰拰k+1鏉¤竟鎵褰㈡垚鐨勮矾寰(1鈮鈮-2)銆備笅闈㈢粰鍑鸿В鍐宠繖涓棶棰樼殑Dijkstra绠楁硶鎬濇兂銆傝鍥綠鐢ㄩ偦鎺ョ煩闃电殑鏂瑰紡瀛樺偍鍦℅A涓紝GA[i,j]=maxint琛ㄧずVi...
绛旓細Dijkstra锛 杩鏂壒鎷 锛绠楁硶鏄敤鏉ヨВ鍐冲崟婧愭渶鐭矾寰勭殑绠楁硶锛岃姹傝矾寰勬潈鍊奸潪璐熸暟銆傝绠楁硶鍒╃敤浜嗘繁搴︿紭鍏堟悳绱㈠拰璐績鐨勭畻娉曘備笅闈㈡槸涓涓湁鏉冨浘锛屾眰浠嶢鍒板悇涓妭鐐圭殑鏈鐭矾寰勩傜1姝ワ細浠嶢鐐瑰嚭鍙戯紝鍒ゆ柇姣忎釜鐐瑰埌A鐐圭殑璺緞锛堝鏋滆鐐逛笉鑳界洿杩濧鐐瑰垯璺濈鍊间负鏃犵┓澶э紝濡傛灉璇ョ偣鑳藉拰A鐩磋繛鍒欐槸褰撳墠鐨勬潈鍊硷級锛...
绛旓細鎬濊矾灏辨槸杩欐牱锛屽線鍚庡氨鏄ぇ鍚屽皬寮備簡 绠楁硶缁撴潫 锛堝浘鐗囨潵婧愪簬缃戠粶锛Dijkstra绠楁硶淇濊瘉鑳芥壘鍒颁竴鏉′粠鍒濆鐐瑰埌鐩爣鐐圭殑鏈鐭矾寰勶紝鍙鎵鏈夌殑杈归兘鏈変竴涓潪璐熺殑浠ｄ环鍊笺傚湪涓婂浘涓紝绮夌孩鑹茬殑缁撶偣鏄垵濮嬬粨鐐癸紝钃濊壊鐨勬槸鐩爣鐐癸紝鑰岀被鑿卞舰鐨勬湁鑹插尯鍩熷垯鏄疍ijkstra绠楁硶鎵弿杩囩殑鍖哄煙銆傞鑹叉渶娣＄殑鍖哄煙鏄偅浜涚鍒濆鐐规渶杩...
绛旓細dijkstra绠楁硶鐢ㄤ簬姹傝В鍗曟簮鏈鐭矾闂锛屽彧鑳芥眰瑙ｆ鏉冨浘锛屽浘涓湁璐熻竟姹傚嚭鏉ョ殑缁撴灉浼氭湁闂銆傜畻娉曠殑鎬濇兂灏辨槸鍏堢‘瀹氫竴涓捣鐐癸紙婧愮偣锛夛紝鐒跺悗瀵绘壘杩欎釜鐐瑰埌鍏朵粬鎵鏈夌偣鐨勮窛绂绘渶灏忓硷紝鎵惧埌涓鏉¤窛绂绘渶鐭殑绾胯矾銆傜涓娆℃煡璇㈣繖鏉¤矾寰勪竴瀹氭槸鍙湁杩欎袱涓偣鐨勶紝纭畾浜嗚繖涓偣锛屽氨鏍囪涓涓嬶紝璇存槑杩欎釜宸茬粡鏄渶鐭殑浜嗭紝鎺...
绛旓細琛2--4鐨勫垵濮嬪寲瀵筺涓《鐐硅繘琛岋紝鏄剧劧鏄疧锛坣锛5--6琛孫锛1锛7琛宯涓《鐐瑰叆闃熷垪O锛坣锛 8琛--14琛岋紝浠8琛屽彲浠ョ湅鍑鸿繘琛屼簡n閬嶅惊鐜紝姣忛亶鍦ㄧ涔濊璋冪敤涓娆xtractMin杩囩▼锛孍xtractMin杩囩▼闇瑕佹悳瀵婚偦鎺ヨ〃锛屾瘡涓娆￠渶瑕佹悳瀵绘暣涓暟缁勶紝鎵浠ヤ竴娆℃搷浣滄椂闂存槸O(n);11琛屽埌14琛屽鑺傜偣u鐨勯偦鎺ヨ〃涓殑杈硅繘琛屾鏌...
绛旓細鏈夊繀瑕侊紝鍥犱负 1銆佸鏋滀緷娆″鏌愪釜椤剁偣杩愮敤Dijkstra绠楁硶锛屽垯涓嶧loyd绠楁硶鐩告瘮锛屽緢澶氳矾寰勫拰缁撴灉璁＄畻鏄噸澶嶇殑锛岃櫧鐒跺鏉傚害鐩稿悓锛屼絾鏄繍绠楅噺宸簡寰堝锛2銆佹洿涓洪噸瑕佺殑鏄細Dijkstra绠楁硶浣跨敤鐨勫墠鎻愭槸鍥句腑璺緞闀垮害蹇呴』澶т簬绛変簬0锛涗絾鏄疐loyd绠楁硶鍒欎粎浠呰姹傛病鏈夋诲拰灏忎簬0鐨勭幆璺氨鍙互浜 鍥犳Floyd 绠楁硶搴旂敤鑼冨洿姣擠ijkstra...
绛旓細閫夊彇缁撶偣V1 S={V1(0),V2(20),V3(50),V4(30),V5(鈭),V6(鈭),V7(鈭)}閫夊彇缁撶偣V2 S={V1(0),V2(20),V3(45),V4(30),V5(鈭),V6(90),V7(鈭)}閫夊彇缁撶偣V4 S={V1(0),V2(20),V3(45),V4(30),V5(85),V6(90),V7(鈭)}閫夊彇缁撶偣V3 S={V1(0),V2(20),V3(45),...
绛旓細Dijkstra绠楁硶鐨勫叿浣撴楠わ細Dijkstra绠楁硶鍙堢О涓哄崟婧愭渶鐭矾寰勶紝鎵璋撳崟婧愭槸鍦ㄤ竴涓湁鍚戝浘涓紝浠庝竴涓《鐐瑰嚭鍙戯紝姹傝椤剁偣鑷虫墍鏈夊彲鍒拌揪椤剁偣鐨勬渶鐭矾寰勯棶棰樸傝G=锛圴锛孍锛夋槸涓涓湁鍚戝浘锛孷琛ㄧず椤剁偣锛孍琛ㄧず杈广傚畠鐨勬瘡涓鏉¤竟锛坕锛宩锛夊睘浜嶦锛岄兘鏈変竴涓潪璐熸潈W锛圛,j锛夛紝鍦℅涓寚瀹氫竴涓粨鐐箆0锛岃姹傛妸浠巚0...
