徹底弄懂最短路徑問(wèn)題(參考版)
2025-03-28 01:52本頁(yè)面
【正文】 整理該篇博文的時(shí)候，一哥們發(fā)布網(wǎng)站到我們?nèi)海W(wǎng)站很精美，一牛神(acmol)使用fork炸彈，結(jié)果服務(wù)器立馬掛啦，更改后又掛啦，目測(cè)目前無(wú)限掛中。：每次從隊(duì)列中取出一個(gè)元素，并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個(gè)相鄰的點(diǎn)松弛成功，則將其入隊(duì)。 用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)。 return 0。 print_path(i)。 ++i) //每個(gè)點(diǎn)最短路 { printf(%d\n, dis[i])。 } if(Bellman_Ford()) for(int i = 1。edge[i].v, amp。 ++i) { scanf(%d%d%d, amp。 for(int i = 1。original)。nodenum, amp。 } if(root == pre[root]) printf(%d\n, root)。}void print_path(int root) //打印最短路的路徑（反向）{ while(root != pre[root]) //前驅(qū) { printf(%d, root)。 break。 i = edgenum。 } bool flag = 1。 ++j) if(dis[edge[j].v] dis[edge[j].u] + edge[j].cost) //松弛（順序一定不能反~） { dis[edge[j].v] = dis[edge[j].u] + edge[j].cost。 ++i) for(int j = 1。 for(int i = 1。 i = nodenum。int dis[N], pre[N]。}Edge。 //點(diǎn)，邊，起點(diǎn)typedef struct Edge //邊{ int u, v。 上代碼(參考了牛帥的博客)includeiostreamincludecstdiousing namespace std。 問(wèn)題：BellmanFord算法是否一定要循環(huán)n1次么？未必！其實(shí)只要在某次循環(huán)過(guò)程中，考慮每條邊后，都沒(méi)能改變當(dāng)前源點(diǎn)到所有頂點(diǎn)的最短路徑長(zhǎng)度，那么BellmanFord算法就可以提前結(jié)束了(開(kāi)篇提出的小優(yōu)化就是這個(gè))。參考了《圖論》。 如果有負(fù)權(quán)回路，那么第 |v|1 遍松弛操作仍然會(huì)成功，這時(shí)，負(fù)權(quán)回路上的頂點(diǎn)不會(huì)收斂。如果沒(méi)有負(fù)權(quán)回路，由于最短路徑樹(shù)的高度最多只能是|v|1，所以最多經(jīng)過(guò)|v|1遍松弛操作后，所有從s可達(dá)的頂點(diǎn)必將求出最短距離。（但是，每次還要判斷松弛，這里浪費(fèi)了大量的時(shí)間，這就是BellmanFord算法效率底下的原因，也正是SPFA優(yōu)化的所在）。因?yàn)樽疃搪窂阶疃嘀话瑋v|1條邊，所以，只需要循環(huán)|v|1 次。在對(duì)每條邊進(jìn)行1遍松弛的時(shí)候，生成了從s出發(fā)，層次至多為1的那些樹(shù)枝。其次，從源點(diǎn)s可達(dá)的所有頂點(diǎn)如果 存在最短路徑，則這些最短路徑構(gòu)成一個(gè)以s為根的最短路徑樹(shù)。描述性證明：(這個(gè)解釋很好)如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在d[v]中 差分約束系統(tǒng)(至今貌似只看過(guò)一道題)無(wú)向圖(無(wú)向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖) (從源點(diǎn)s到其它所有頂點(diǎn)v)Bellman算法在求解過(guò)程中，每次循環(huán)都要修改所有頂點(diǎn)的dist[ ]，也就是說(shuō)源點(diǎn)到各頂點(diǎn)最短路徑長(zhǎng)度一直要到Bellman算法結(jié)束才確定下來(lái)。 Dijkstra算法和Bellman算法思想有很大的區(qū)別：Dijkstra算法在求解過(guò)程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改 dist k [u] = mi
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1