徹底弄懂最短路徑問(wèn)題-資料下載頁(yè)
2025-03-25 01:52本頁(yè)面
【正文】 條邊后，都沒(méi)能改變當(dāng)前源點(diǎn)到所有頂點(diǎn)的最短路徑長(zhǎng)度，那么BellmanFord算法就可以提前結(jié)束了(開(kāi)篇提出的小優(yōu)化就是這個(gè))。 上代碼(參考了牛帥的博客)includeiostreamincludecstdiousing namespace std。define MAX 0x3f3f3f3fdefine N 1010int nodenum, edgenum, original。 //點(diǎn)，邊，起點(diǎn)typedef struct Edge //邊{ int u, v。 int cost。}Edge。Edge edge[N]。int dis[N], pre[N]。bool Bellman_Ford(){ for(int i = 1。 i = nodenum。 ++i) //初始化 dis[i] = (i == original ? 0 : MAX)。 for(int i = 1。 i = nodenum 1。 ++i) for(int j = 1。 j = edgenum。 ++j) if(dis[edge[j].v] dis[edge[j].u] + edge[j].cost) //松弛（順序一定不能反~） { dis[edge[j].v] = dis[edge[j].u] + edge[j].cost。 pre[edge[j].v] = edge[j].u。 } bool flag = 1。 //判斷是否含有負(fù)權(quán)回路 for(int i = 1。 i = edgenum。 ++i) if(dis[edge[i].v] dis[edge[i].u] + edge[i].cost) { flag = 0。 break。 } return flag。}void print_path(int root) //打印最短路的路徑（反向）{ while(root != pre[root]) //前驅(qū) { printf(%d, root)。 root = pre[root]。 } if(root == pre[root]) printf(%d\n, root)。}int main(){ scanf(%d%d%d, amp。nodenum, amp。edgenum, amp。original)。 pre[original] = original。 for(int i = 1。 i = edgenum。 ++i) { scanf(%d%d%d, amp。edge[i].u, amp。edge[i].v, amp。edge[i].cost)。 } if(Bellman_Ford()) for(int i = 1。 i = nodenum。 ++i) //每個(gè)點(diǎn)最短路 { printf(%d\n, dis[i])。 printf(Path:)。 print_path(i)。 } else printf(have negative circle\n)。 return 0。} 用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)。初始時(shí)將源加入隊(duì)列。每次從隊(duì)列中取出一個(gè)元素，并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個(gè)相鄰的點(diǎn)松弛成功，則將其入隊(duì)。直到隊(duì)列為空時(shí)算法結(jié)束；這個(gè)算法，簡(jiǎn)單的說(shuō)就是隊(duì)列優(yōu)化的bellmanford，利用了每個(gè)點(diǎn)不會(huì)更新次數(shù)太多的特點(diǎn)發(fā)明的此算法(看我上面那個(gè)圖，只有相鄰點(diǎn)更新了，該點(diǎn)才有可能更新) 。代碼參見(jiàn)： 整理該篇博文的時(shí)候，一哥們發(fā)布網(wǎng)站到我們?nèi)?，網(wǎng)站很精美，一牛神(acmol)使用fork炸彈，結(jié)果服務(wù)器立馬掛啦，更改后又掛啦，目測(cè)目前無(wú)限掛中。作者：張朋飛出處：本文版權(quán)歸作者張朋飛所有，歡迎轉(zhuǎn)載和商用，但未經(jīng)作者同意必須保留此段聲明，且在文章頁(yè)面明顯位置給出原文連接，否則保留追究法律責(zé)任的權(quán)利.
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1