圖論算法（課堂PPT）

1、ACM/ICPC程序設(shè)計(jì)程序設(shè)計(jì)簡(jiǎn)單算法簡(jiǎn)單算法圖論圖論-算法算法圖的遍歷圖的遍歷BFS(廣搜廣搜)DFS(深搜深搜)最小生成樹最小生成樹PrimKruskal最短路徑最短路徑Bellman-FordDijkstraFloyd-WarshallnBFS練習(xí)練習(xí)nDFS練習(xí)練習(xí)nPrim練習(xí)練習(xí)nKruskal練習(xí)練習(xí)nBellman-Ford練習(xí)練習(xí)nDijkstra練習(xí)練習(xí)nFloyd-Warshall練習(xí)練習(xí)圖的遍歷圖的遍歷n遍歷要訪問到圖中的遍歷要訪問到圖中的每一個(gè)每一個(gè)頂點(diǎn)。頂點(diǎn)。nBFS (Breadth-First Search)nDFS (Depth-First Search)B

2、FS思想思想 遍歷篇遍歷篇n1.從圖中某頂點(diǎn)從圖中某頂點(diǎn)v0出發(fā)，在訪問了出發(fā)，在訪問了v0之后，搜索之后，搜索v0的的(所有未被訪問的所有未被訪問的)鄰接頂點(diǎn)鄰接頂點(diǎn)v1.v2n2.依次從這些鄰接頂點(diǎn)出發(fā)，廣搜圖中其它頂點(diǎn)，依次從這些鄰接頂點(diǎn)出發(fā)，廣搜圖中其它頂點(diǎn)，直至圖中所有已被訪問的頂點(diǎn)的鄰接頂點(diǎn)都被訪問直至圖中所有已被訪問的頂點(diǎn)的鄰接頂點(diǎn)都被訪問到。到。n3.若此時(shí)圖中還有未被訪問到的頂點(diǎn)，則再選擇其若此時(shí)圖中還有未被訪問到的頂點(diǎn)，則再選擇其中之一作為中之一作為v0重復(fù)上述過程。直到圖中所有頂點(diǎn)均重復(fù)上述過程。直到圖中所有頂點(diǎn)均被訪問到。被訪問到。/搜索過程沒有回溯，是一種犧牲空間換取

3、時(shí)間的方搜索過程沒有回溯，是一種犧牲空間換取時(shí)間的方法。時(shí)間復(fù)雜度：法。時(shí)間復(fù)雜度：O(V+E)BFS程序基本結(jié)構(gòu)程序基本結(jié)構(gòu)定義一個(gè)隊(duì)列定義一個(gè)隊(duì)列;起始點(diǎn)加入隊(duì)列起始點(diǎn)加入隊(duì)列;while(隊(duì)列不空隊(duì)列不空) 取出隊(duì)頭結(jié)點(diǎn)取出隊(duì)頭結(jié)點(diǎn); 若它是所求的目標(biāo)狀態(tài)若它是所求的目標(biāo)狀態(tài),跳出循環(huán)跳出循環(huán); 否則，從它擴(kuò)展出子結(jié)點(diǎn)否則，從它擴(kuò)展出子結(jié)點(diǎn),全都添加到隊(duì)尾全都添加到隊(duì)尾;若循環(huán)中找到目標(biāo)若循環(huán)中找到目標(biāo),輸出結(jié)果輸出結(jié)果;否則輸出無(wú)解否則輸出無(wú)解;BFS示例：示例：DFS思想思想 遍歷篇遍歷篇n1.將圖將圖G中每個(gè)頂點(diǎn)標(biāo)記為未被訪問，選取一個(gè)頂中每個(gè)頂點(diǎn)標(biāo)記為未被訪問，選取一個(gè)頂點(diǎn)點(diǎn)v作

4、為搜索起點(diǎn)，標(biāo)記其為已訪問作為搜索起點(diǎn)，標(biāo)記其為已訪問n2.遞歸地深搜遞歸地深搜v的每個(gè)未被訪問過的鄰接頂點(diǎn)，直到的每個(gè)未被訪問過的鄰接頂點(diǎn)，直到從從v出發(fā)所有可達(dá)的頂點(diǎn)都已被訪問過。出發(fā)所有可達(dá)的頂點(diǎn)都已被訪問過。n3.若此時(shí)圖中還有未被訪問到的頂點(diǎn)，則再選擇其若此時(shí)圖中還有未被訪問到的頂點(diǎn)，則再選擇其中之一作為中之一作為v重復(fù)上述過程。直到圖中所有頂點(diǎn)均被重復(fù)上述過程。直到圖中所有頂點(diǎn)均被訪問到。訪問到。 /時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(V+E)DFS程序基本結(jié)構(gòu)程序基本結(jié)構(gòu)void DFS(int step)for(i=0; iMax_Elements; i+)if(子結(jié)點(diǎn)符合條件子結(jié)點(diǎn)符

5、合條件)新子結(jié)點(diǎn)入棧；新子結(jié)點(diǎn)入棧；if(是目標(biāo)結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn))輸出輸出elseDFS(step+1); 子結(jié)點(diǎn)出棧子結(jié)點(diǎn)出棧DFS示例示例最小生成樹最小生成樹(Minimum Spanning Tree)nG(V,E)是無(wú)向連通賦權(quán)圖，是無(wú)向連通賦權(quán)圖，G(V,E)是包含是包含G中所中所有頂點(diǎn)的樹，且樹中各邊權(quán)總和最小，則有頂點(diǎn)的樹，且樹中各邊權(quán)總和最小，則G是最小是最小生成樹生成樹(可能不唯一可能不唯一)n容易想到，用容易想到，用貪心貪心策略。策略。PrimKruskalPrim思想思想 最小生成樹篇最小生成樹篇1.從從V中任取一結(jié)點(diǎn)放入中任取一結(jié)點(diǎn)放入V；2.在所有的端點(diǎn)分別在在所有的端

6、點(diǎn)分別在(V-V)和和V中的邊中，選一條中的邊中，選一條權(quán)最小的加入權(quán)最小的加入E；3.將邊將邊E在在(V-V)中的頂點(diǎn)從中的頂點(diǎn)從V中取出放入中取出放入V；4.重復(fù)步驟重復(fù)步驟23，直到，直到V與與V相等為止。相等為止。/該算法步步為營(yíng)，每步生成的結(jié)果均為最終結(jié)果的該算法步步為營(yíng)，每步生成的結(jié)果均為最終結(jié)果的一部分。它每次從連接一部分。它每次從連接V與與(V-V)的邊中選最小邊，的邊中選最小邊，所選出的不一定是所有尚未選出的屬于最小生成樹所選出的不一定是所有尚未選出的屬于最小生成樹的邊中的最小者。時(shí)間復(fù)雜度：的邊中的最小者。時(shí)間復(fù)雜度：O(ElgV)Prime程序基本結(jié)構(gòu)程序基本結(jié)構(gòu)void

7、 Prim() int i,j,k,min,lowcostvex,closestvex;for(i=2;i=n;i+) lowcosti=c1i;/第第1個(gè)點(diǎn)到其他點(diǎn)的代價(jià)個(gè)點(diǎn)到其他點(diǎn)的代價(jià)closesti=1;/初始時(shí)，所有點(diǎn)的起點(diǎn)都是點(diǎn)初始時(shí)，所有點(diǎn)的起點(diǎn)都是點(diǎn)1 for(i=2;i=n;i+) min=maxcost;/maxcost一個(gè)很大的數(shù)一個(gè)很大的數(shù)for(j=2;j=n;j+)if(closestj&lowcostj0) min=lowcostj;/在在v中找到最小的代價(jià)點(diǎn)中找到最小的代價(jià)點(diǎn)kk=j;closestk=0;/k歸入歸入u中中for(j=2;j=n;j+)

8、if(closestj&ckj0) lowcostj=ckj;/以以k點(diǎn)為起點(diǎn)進(jìn)行新一輪的代價(jià)計(jì)算點(diǎn)為起點(diǎn)進(jìn)行新一輪的代價(jià)計(jì)算,更新更新lowcost和和closestclosestj=k;無(wú)向連通圖無(wú)向連通圖,初始時(shí)初始時(shí)u只包只包含含1個(gè)點(diǎn)，后一步步將個(gè)點(diǎn)，后一步步將v中中的點(diǎn)添加到的點(diǎn)添加到u中來。中來。用用closesti=0表示表示i點(diǎn)在點(diǎn)在u集合中集合中, lowcosti當(dāng)前當(dāng)前起點(diǎn)到起點(diǎn)到i點(diǎn)的最小代價(jià)點(diǎn)的最小代價(jià)cij 頂點(diǎn)頂點(diǎn)i到到j(luò)的權(quán)的權(quán)(i到到j(luò)無(wú)邊，則令無(wú)邊，則令cij=-1)，共有共有n個(gè)頂點(diǎn)個(gè)頂點(diǎn) (該模板中，該模板中，頂點(diǎn)從頂點(diǎn)從1開始計(jì)開始計(jì))Pri

9、m示例：示例：V V2 2V V0 0V V3 3V V5 5V V4 4V V1 1V V2 2V V0 0V V3 3V V5 5V V4 4V V1 11U=v0U=v0,v2U=v0,v2,v5U=v0,v2,v5,v3U=v0,v2,v5,v3,v1U=v0,v2,v5,v3,v1,v4V V3 3V V4 4V V1 141V V0 0V V2 2V V5 5V V4 4V V1 1214V V0 0V V2 2V V5 5V V3 3V V4 41425V V2 2V V0 0V V5 5V V1 1V V3 335124V V2 2V V1 1V V0 0V V5 5V V3

10、3V V4 4Kruskal思想：思想： 最小生成樹篇最小生成樹篇1.將邊按邊樹由小到大排序。將邊按邊樹由小到大排序。2.每次加最小邊每次加最小邊 & 不構(gòu)成回路。不構(gòu)成回路。3.加進(jìn)了加進(jìn)了n-1條邊就得到了最小生成樹條邊就得到了最小生成樹/Kruskal算法并不保證每步生成的結(jié)果是連通的算法并不保證每步生成的結(jié)果是連通的（中間結(jié)果可能不是樹）。（中間結(jié)果可能不是樹）。Kruskal程序基本結(jié)構(gòu)：程序基本結(jié)構(gòu)：n優(yōu)先隊(duì)列優(yōu)先隊(duì)列+并查集并查集Kruscal 示例：示例： 實(shí)例的執(zhí)行過程實(shí)例的執(zhí)行過程12435661655563421、初始連通分量：、初始連通分量：1,2,3,4,5,

11、62、反復(fù)執(zhí)行添加、放棄動(dòng)作。、反復(fù)執(zhí)行添加、放棄動(dòng)作。條件：邊數(shù)不等于條件：邊數(shù)不等于 n-1時(shí)時(shí) 邊邊 動(dòng)作動(dòng)作連通分量連通分量 (1,3) 添加添加1,3,4,5,6,2 (4,6) 添加添加1,3,4, 6,2,5 (2,5) 添加添加1,3,4, 6,2,5 (3,6) 添加添加1,3,4, 6,2,5 (1,4) 放棄放棄因構(gòu)成回路因構(gòu)成回路 (3,4) 放棄放棄因構(gòu)成回路因構(gòu)成回路 (2,3) 添加添加1,3,4,5,6,21243561534255算法實(shí)現(xiàn)要點(diǎn): 用并查集的相關(guān)操作：實(shí)現(xiàn)集合的并；判斷新邊的兩端點(diǎn)是否處于同一集合，來確定是否構(gòu)成回路。Dijkstra思想：思想：

12、 最短路徑篇最短路徑篇Dijkstra程序基本結(jié)構(gòu)：程序基本結(jié)構(gòu)：nvoid disktra(int v)/原點(diǎn)是原點(diǎn)是v nbool smaxn; register int i,j,k;nfor(i=1;i=n;i+)ndisti = cvi;nsi = 0; / i不在集合不在集合S中中nif(disti=manint)/v to i沒有邊沒有邊nprevi = 0;nelsenprevi = v; nnsv = 1; distv = 0;nfor(i=1;in;i+)nint temp = manint, u = v;nfor(j=1;j=n;j+)nif(!sj&distj&a

13、mp;distjtemp)nu = j;ntemp = distj;nnsu = 1;nfor(j=1;j=n;j+)nif(!sj&cujmanint)nint newdist = distu + cuj;nif(newdist distj)ndistj = newdist;nprevj = u;nnnn結(jié)點(diǎn)從結(jié)點(diǎn)從1開始計(jì)，開始計(jì)，maxn為最大結(jié)點(diǎn)數(shù)為最大結(jié)點(diǎn)數(shù),n為結(jié)點(diǎn)數(shù)，為結(jié)點(diǎn)數(shù)，manint是無(wú)窮大是無(wú)窮大, cij i到到j(luò)的的權(quán)，權(quán)，pre記錄父結(jié)點(diǎn)記錄父結(jié)點(diǎn),disti源點(diǎn)到源點(diǎn)到i的最短的最短路徑，路徑，s表示左邊的集合表示左邊的集合const int maxn =

14、 101, manint = 99999999;int cmaxnmaxn,prevmaxn,distmaxn,n;源 點(diǎn) 終 點(diǎn) 最 短 路 徑路 徑 長(zhǎng) 度 v0 v1(v0, v1)10 v2 (v0, v1, v2) (v0, v3, v2) 60 50 v3(v0, v3)30 v4(v0, v4)(v0, v3, v4) (v0, v3, v2, v4)100 90 60Bellman-Ford思想：思想： 最短路徑篇最短路徑篇n1.圖中無(wú)負(fù)回路圖中無(wú)負(fù)回路n2.最短路徑長(zhǎng)度數(shù)組序列最短路徑長(zhǎng)度數(shù)組序列 dist1u,distn-1u，其中其中distiu從從v到到u最多經(jīng)過最多經(jīng)

15、過i條邊條邊n3. dist1u = Edgev,u distku = min distk-1u, min distk-1j+Edgej,u /時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(VE)Bellman-Ford程序基本結(jié)構(gòu)：程序基本結(jié)構(gòu)：nvoid Bellman-Ford() nint i;nfor(i=1;i=n;i+) ndi=manint;npari=0;nnds=0;nfor(i=1;idu+w(u,v) ndv=du+w(u,v);nparv=u;nnnfor each edge(u,v)nif(dvdu+w(u,v)nreturn false;nreturn true;ns為起點(diǎn)，為起點(diǎn)

16、，di是是s到到i的最短路的最短路徑長(zhǎng)度，徑長(zhǎng)度，pari記錄記錄i結(jié)點(diǎn)的父結(jié)點(diǎn)的父節(jié)點(diǎn)節(jié)點(diǎn).如果不存在從如果不存在從s可達(dá)可達(dá)的負(fù)權(quán)環(huán)，返回的負(fù)權(quán)環(huán)，返回true.Floyd-Warshall思想：思想： 最短路徑篇最短路徑篇n定義一個(gè)定義一個(gè)nn的方陣序列的方陣序列 A0，A1，An，其中，其中Aki-1j-1表示從表示從vi到到vj允許允許k個(gè)頂點(diǎn)個(gè)頂點(diǎn)v0, v1,vk-1為中間頂為中間頂點(diǎn)的點(diǎn)的最短路徑長(zhǎng)度（最短路徑長(zhǎng)度（A0 是圖的鄰接矩陣）。是圖的鄰接矩陣）。A0ij表示表示從從vi到到vj不經(jīng)過任何中間頂點(diǎn)的最短路徑長(zhǎng)度。不經(jīng)過任何中間頂點(diǎn)的最短路徑長(zhǎng)度。Anij就是從就是從v

17、i到到vj的最短路徑長(zhǎng)度。的最短路徑長(zhǎng)度。A0ij=arcsij0in-1, 0jn-1Akij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn，加入第，加入第k個(gè)頂點(diǎn)個(gè)頂點(diǎn)vk-1為中間頂點(diǎn)。為中間頂點(diǎn)。n/時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(n3)Floyd-Warshall程序基本結(jié)構(gòu)：程序基本結(jié)構(gòu)：for(k=0;kn;k+)for(k=0;kn;k+) for(i=0;in;i+) for(i=0;in;i+) for( j=0;jn;j+) for( j=0;jdik+dkj) if (dijdik+dkj) dij=dik+dkj; dij=dik+dkj; ( ( dij=

18、Min(dij, dik+dkj)dij=Min(dij, dik+dkj) ) )Floyd示例：示例：n執(zhí)行執(zhí)行Floyd算法后算法后:0612 11 9410580714 960910 013 16 8722 01416 17 11 10 8307123459851068776183Exercisen Practice makes perfect!n The more, the better!BFS： zoj(1091)n國(guó)際象棋棋盤上有一個(gè)馬，要跳到指定目標(biāo)，最少跳幾步？國(guó)際象棋棋盤上有一個(gè)馬，要跳到指定目標(biāo)，最少跳幾步？ a b c d e f g h12345678h8a1輸入：a

19、1 h8輸出：To get from a1 to h8 takes 6 knight moves. 跳馬的規(guī)則跳馬的規(guī)則 a b c d e f g h12345678在23的矩形里：BFS： a b c d e f g h123456780 332 13 22 31 233 22 3332 33333332 33332例如：從a1到e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點(diǎn)里，結(jié)果就找到了。To get from a1 to e4 takes 3 knight moves. BFS：int main() for(;) if(!(cinc1) break; cind1c2d2; /輸入起點(diǎn)、終點(diǎn)。輸入起點(diǎn)

20、、終點(diǎn)。 for(int i=0;i8;i+) for(int j=0;j8;j+)mij=0;/所有點(diǎn)都標(biāo)記為所有點(diǎn)都標(biāo)記為“沒走沒走” proc(); return 0;#include #include using namespace std;int d82=1,2,1,-2,2,-1,2,1, -1,2,-1,-2,-2,-1,-2,1;int m88;/給走過的點(diǎn)標(biāo)記char c1,c2,d1,d2;void proc();void proc() int x,y,nx,ny,sx,sy,dx,dy,step=0; sx=c1-a;sy=d1-1; dx=c2-a;dy=d2-1; q

21、ueue tq; tq.push(sx);tq.push(sy);tq.push(step); msxsy=1; while (!tq.empty() x=tq.front(); tq.pop(); y=tq.front(); tq.pop(); step=tq.front(); tq.pop(); if(x = dx & y = dy)break; for(int i=0;i8;i+) nx=x+di0;ny=y+di1; if(nx= 8 | ny= 8 |mnxny) continue; tq.push(nx);tq.push(ny);tq.push(step+1); mnxny

22、=1; coutTo get from c1d1 to c2d2 takes step knight moves.endl;初始點(diǎn)入隊(duì)取出隊(duì)頭元素新點(diǎn)加入隊(duì)尾Knight Moves zoj(1091)程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)雙向雙向BFS a b c d e f g h1234567802 1221 2122211112012n從起點(diǎn)、終點(diǎn)同時(shí)開始從起點(diǎn)、終點(diǎn)同時(shí)開始雙向BFS,有效地提高了時(shí)空效率。從起點(diǎn)找2步能跳到的點(diǎn)從終點(diǎn)找1步能跳到的點(diǎn)DFS： pku2258n給無(wú)向圖，求此圖中的最長(zhǎng)路徑。要求路不能重復(fù)給無(wú)向圖，求此圖中的最長(zhǎng)路徑。要求路不能重復(fù)走，但節(jié)點(diǎn)可以重復(fù)地到達(dá)。如走，但節(jié)點(diǎn)可以重

23、復(fù)地到達(dá)。如輸入輸入輸出？輸出？n/best用來記錄最長(zhǎng)路徑的長(zhǎng)度，用來記錄最長(zhǎng)路徑的長(zhǎng)度，griji到到j(luò)的邊長(zhǎng)為的邊長(zhǎng)為1，以每一個(gè)結(jié)點(diǎn)為源點(diǎn)進(jìn)行深搜，以每一個(gè)結(jié)點(diǎn)為源點(diǎn)進(jìn)行深搜n#include #includenint gr2525,best,n,m;nvoid dfs(int p,int depth) /p為源點(diǎn)，為源點(diǎn)，depth為深度為深度 nint i;nbool flag=true;nfor(i=0;ibest)nbest=depth;nreturn;nnmain() int i,a,b;while(scanf(%d %d,&n,&m)!=EOF) if(n=

24、0&m=0) break;best=0; memset(gr,0,sizeof(gr);for(i=0;im;i+) scanf(%d %d,&a,&b);grab=grba=1;for(i=0;in & n) for(i=0;ixiyi; for(j=0;ji;j+) dij=dji=sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj); #include #include #include using namespace std;#define Min(a,b) (a)(b)?(b):(a)#define Max(a,b) (a)(b)?(

25、a):(b)double d201201;Prim: double lowcost200,min,answer; memset(lowcost,0,sizeof(lowcost); answer=d01; for(i=1;in;i+)/與集合鄰接的邊長(zhǎng)初始化，現(xiàn)在集合中只有一個(gè)點(diǎn)與集合鄰接的邊長(zhǎng)初始化，現(xiàn)在集合中只有一個(gè)點(diǎn)0 lowcosti=d0i; /初始化初始化lowcost answer=Min(answer,d0i); /同時(shí)找出最短邊同時(shí)找出最短邊 for(i=1;in;i+) min=1000000;j=-1; for(k=1;kn;k+) if(lowcostk!=0 &

26、; lowcostkmin)/找有最小邊權(quán)的鄰接點(diǎn)找有最小邊權(quán)的鄰接點(diǎn) min=lowcostk; j=k; answer=Max(answer,min); if(j=1)/當(dāng)集合加進(jìn)了點(diǎn)當(dāng)集合加進(jìn)了點(diǎn)1，可以結(jié)束，可以結(jié)束 break; Prim: lowcostj=0;/集合加進(jìn)點(diǎn)集合加進(jìn)點(diǎn)j for(k=1;kn;k+)/更新鄰接點(diǎn)邊權(quán)更新鄰接點(diǎn)邊權(quán) if(djklowcostk & lowcostk!=0) lowcostk=djk; printf(Scenario #%dn,T+); printf(Frog Distance = %.3lfnn,answer); return

27、 0;Kruscal: zju1942class Edge/邊類，記錄三個(gè)信息：端點(diǎn)、邊長(zhǎng)邊類，記錄三個(gè)信息：端點(diǎn)、邊長(zhǎng)public: int e,s; double dis; Edge() Edge(int a,int b,double c):e(a),s(b),dis(c)edge40000;/用一個(gè)數(shù)組保存邊用一個(gè)數(shù)組保存邊bool cmp(Edge e1,Edge e2) /排序時(shí)，需要比較邊的長(zhǎng)短排序時(shí)，需要比較邊的長(zhǎng)短 return e1.disn & n) L=0; for(i=0;ixiyi; for(j=0;ji;j+) edgeL+=Edge(i,j,sqrt(xi

28、-xj)*(xi-xj)+(yi-yj)*(yi-yj); sort(edge,edge+L,cmp); /標(biāo)準(zhǔn)庫(kù)的函數(shù)，對(duì)邊進(jìn)行從小到大排序標(biāo)準(zhǔn)庫(kù)的函數(shù)，對(duì)邊進(jìn)行從小到大排序#include #include #include #include using namespace std;Kruscal: for(i=0;in;i+) /并查集的初始化，剛開始，每個(gè)點(diǎn)自成集合。并查集的初始化，剛開始，每個(gè)點(diǎn)自成集合。 si=i; for(i=0;iL;i+) /從最小邊長(zhǎng)的邊開始，把邊兩端點(diǎn)所在集合合并起來從最小邊長(zhǎng)的邊開始，把邊兩端點(diǎn)所在集合合并起來 Unite(edgei.e,edgei.s

29、); if(Find(0) = Find(1)/當(dāng)當(dāng)0與與1處同一集合，當(dāng)前所加邊長(zhǎng)就是所求處同一集合，當(dāng)前所加邊長(zhǎng)就是所求 break; printf(Scenario #%dn,T+); printf(Frog Distance = %.3lfnn,edgei.dis); return 0;Bellman-Ford: HomeWorknvoid Initialize_Single_Source(int s)nnfor(i=1;idu+wuv)nndv=du+wuv;nPav=u;nnIts to examine whether there exits negative cycles in

30、G ,is exist - false ; no exist - true#include#define MAX 100int i,j,k,n,s;int dMAX,PaMAX,wMAXMAX;/d is an upper bound on the weight of a shortest path from source s to v Bellman-Ford:nbool Bellman_Ford(int s)nnInitialize_Single_Source(s);nfor(i=1;in;i+)nnfor(j=1;j=n;j+)n for(k=1;k=n;k+)nif(wjk!=6553

31、5)nRelax(j,k);nnfor(j=1;j=n;j+)n for(k=1;kdj+wjk ) n return false;nreturn true;nint main()scanf(%d,&n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&wij);scanf(%d,&s);/s=n;if(Bellman_Ford(s)printf(No negative cycles exits here .);else printf(There exits negative cycles !);printf(n);return 0;/*

32、565535 6 65535 7 6553565535 65535 5 8 -465535 -2 65535 65535 6553565535 65535 -3 65535 92 65535 7 65535 655351*/Dijkstra: pku2387nvoid Dijkstra(int n,int v)nnfor(int i=1;i=n;i+)nndisti=cvi;nsi=false;nif(disti=MAX) previ=0;nelse previ=v;nndistv=0;sv=true;nfor(i=1;in-1;i+)nnint temp=MAX;nint u=v;nfor(int j=1;j=n;j+)nif(!sj)&(distjtemp)nnu=j;temp=distj;nnsu=true;nfor(j=1;j=n;j+)nif(!sj)&(cujMAX)nnint newdist=distu+cuj;nif(newd