|
|
|
Floyd绠楁硶
閫傜敤鎯呭喌锛
姹備换鎰忎袱鐐归棿鐨勬渶鐭矾锛屼笉鑳藉鐞嗚礋鏉冨洖璺紙璐熸潈鐜)锛屽彲澶勭悊璐熸潈杈广
鏃堕棿澶嶆潅搴︼細O(N^3)
绠楁硶鎬濇兂锛
濡傛灉瑕佷袱鐐筧,b闂寸殑璺▼鍙樼煭锛屽氨闇瑕佸紩鍏ユ柊鐨勯《鐐筴1锛宬2,鈥︹n锛屼娇a鈥>k1鈥>k2鈥>鈥︹︹>kn鈥>b鏇寸煭銆傚嵆瀵筧鍜宐涔嬮棿鎵鏈夌殑鍏朵粬鐐硅繘琛屾澗寮涖
DP锛氱姸鎬佺姸鎬佽浆绉绘柟绋嬶細d[k][j] = min(d[k-1][j], d[k-1][k]+d[k-1][k][j])
鍒╃敤婊氬姩鏁扮粍浼樺寲锛歛[j]=min(a[j],a[k]+a[k][j])銆愬姩鎬佽鍒掞細0/1鑳屽寘闂銆
鐩稿叧鏂囩珷锛歨ttps://blog.csdn.net/qq_40507857/article/details/80657007
鏍稿績浠ｇ爜锛
for(int k = 1; k <=n; k++)
for(int i = 1; i <=n; i++)
for(int j = 1; j <=n; j++)
a[j]=min(a[j],a[k]+a[k][j])锛
Dijkstra绠楁硶
閫傜敤鎯呭喌锛
姹備粠涓涓《鐐瑰埌鍏朵綑鍚勯《鐐圭殑鏈鐭矾寰勭畻娉曪紝涓嶈兘澶勭悊璐熸潈杈广
鏃堕棿澶嶆潅搴︼細O(N^2)
鍒╃敤鍫嗕紭鍖栵紱鍦ㄨ竟鏁癕灏戜簬N^2鐨勭█鐤忓浘鏉ヨ锛屽彲浠ョ敤閭绘帴琛ㄤ唬鏇块偦鎺ョ煩闃点傚彲浼樺寲涓篛((M+N)logN)銆
绠楁硶鎬濇兂锛
绫讳技BFS+璐績銆傞氳繃杈规潵鏉惧紱1鍙烽《鐐瑰埌鍏朵綑鍚勭偣鐨勮窛绂汇傞夋嫨绂昏捣鐐规渶杩戠殑涓涓偣锛屾墿鏁ｅ嚭鍘汇
閫夋嫨璺濈1鍙烽《鐐规渶杩戠殑涓涓《鐐逛綔涓虹‘瀹氱殑闀垮害锛堝洜涓鸿竟鏉冨奸潪璐燂紝鎵浠ヨ窛绂1鍙烽《鐐硅窛绂绘渶鐭嵆鎰忓懗鐫涓嶅彲鑳介氳繃鍏朵粬鐨勭偣涓浆鏉ョ缉鐭窛绂汇
鐒跺悗璁ㄨ浠庡凡閫夌殑鐐筰鍒板叾浠栫偣j鐨勮窛绂绘槸鍚﹁兘澶熸洿鐭紝鍗砫is[j]=min(dis[j],dis+a[j])銆
濡傛灉book鏁扮粍鐨勫煎叏涓1锛屽垯1鍙风偣鍒版墍鏈夌殑鐐圭殑璺濈纭畾锛屽嵆1鍙风偣鍒版墍鏈夌偣鐨勬渶鐭窛绂荤‘瀹氥
鏍稿績浠ｇ爜锛堜吉浠ｇ爜锛夛細
for(i=1;i<=n;i++)
{
min1=maxn;
閬嶅巻book鏁扮粍锛屽鎵捐窛绂1鍙烽《鐐硅窛绂绘渶鐭偣锛岃繘琛屾爣璁帮細u=j锛
book=1;
閬嶅巻姝ょ偣鍒板叾浠栫偣鐨勮窛绂伙紝鏉惧紱杈癸細dis[v]=min(dis[v],dis+a[v]);
}
浼樺寲锛
鍫嗕紭鍖栵紙priority_queue锛塐((M+N)logN)
鐢ㄥ爢姣忔寮瑰嚭鏈灏忓兼潵浠ｆ浛姣忚疆杩涜鐨勬渶鐭竟鏌ユ壘銆傚爢鐢ㄥ皬鏍瑰爢锛屽彲浠ヤ繚璇佹瘡娆″湪鍫嗛《鐨勫厓绱犳槸鏈灏忕殑銆
Ford绠楁硶
閫傜敤鎯呭喌锛
鍙互瑙ｅ喅甯﹁礋鏉冭竟鐨勫浘锛屽彲浠ュ垽鏂槸鍚﹀瓨鍦ㄨ礋鏉冨洖璺紙璐熸潈鐜級銆
鏃堕棿澶嶆潅搴︼細O(NM)
浼樺寲锛氬彲浠ョ敤check鏉ュ垽鏂璬is鏁扮粍鍦ㄦ湰杞惊鐜腑鏄惁鍙戠敓鍙樺寲銆傚鏋渄is鏁扮粍娌℃湁鍙戠敓鍙樺寲锛屽嵆鎵姹傚凡缁忔槸鏈鐭矾寰勶紝鍗冲彲璺冲嚭寰幆銆
绠楁硶鎬濇兂锛
瀵规墍鏈夌殑杈硅繘琛宯-1娆℃澗寮涙搷浣溿
杩涜k娆℃澗寮涘悗锛屾垜浠彲浠ュ緱鍒1鍙风偣鏈澶氱粡杩噆鏉¤竟鍒板叾浣欑偣鐨勬渶鐭窛绂汇
鑳藉惁閫氳繃u->v(鏉冨间负w)鐨勮竟浣1鍙烽《鐐瑰埌v鐨勮窛绂荤缉鐭紝鍗筹細dis[v]=min(dis[v],dis[u]+w)銆
瀵逛簬姝ｆ潈鍥炶矾锛屽幓鎺夌殑璇濓紝鎴戜滑鑲畾鍙互寰楀埌鏇寸煭鐨勮窛绂汇
瀵逛簬璐熸潈鍥炶矾锛屾瘡寰幆涓娆￠兘浼氬緱鍒版洿鐭殑璺濈銆傛墍浠ユ垜浠彲浠ラ氳繃杩涜n-1娆″惊鐜箣鍚庯紝鑳戒笉鑳界户缁澗寮涙潵鍒ゆ柇鍥句腑鏄惁瀛樺湪璐熸潈鍥炶矾銆
鏍稿績浠ｇ爜锛
for(k=1;k<=n-1;k++)
for(i=1;i<=m;i++)
dis[v]=min(dis[v],dis[u]+w);
SPFA绠楁硶锛團ord绠楁硶鐨勯槦鍒椾紭鍖栵級
閫傜敤鎯呭喌锛
鍚孎ord绠楁硶銆
鏃堕棿澶嶆潅搴︼細鏈鍧忔儏鍐礝(NM)
绠楁硶鎬濇兂锛
鍙栧嚭闃熼锛屽鍏跺嚭杈硅繘琛屾澗寮涙搷浣滐紝灏嗘渶鐭矾寰勮兘澶熷彂鐢熸敼鍙樼殑鐐规斁鍏ラ槦灏俱傜敤鏁扮粍book鏍囪瘑褰撳墠閭ｄ簺鐐瑰凡鍦ㄩ槦鍒椾腑銆
褰㈠紡涓婃湁浜涚被浼间簬BFS銆
鏍稿績浠ｇ爜锛
鐢ㄩ偦鎺ヨ〃瀛樺浘锛涢槦鍒楁搷浣溿 |
|
发表于 2023-8-26 21:47:06