《NOIP圖的基礎(chǔ)算法》PPT課件

1、NOIP 圖的常用算法簡(jiǎn)介 石門中學(xué)江濤 2009.10.41精選PPT目 錄圖的表示鄰接矩陣、鄰接鏈表、圖的遍歷最小生成樹算法 Prim算法、Kruskal算法最短路徑算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法2精選PPT目 錄圖的表示鄰接矩陣、鄰接鏈表、圖的遍歷最小生成樹算法 Prim算法、Kruskal算法最短路徑算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法3精選PPT頂點(diǎn)給點(diǎn)編號(hào)為連續(xù)的整數(shù)把頂點(diǎn)存放在數(shù)組中邊鄰接矩陣布爾值(或邊權(quán)值) -TRUE 有邊FALSE 無邊空間復(fù)雜度O(|V|2)圖的表示-鄰

2、接矩陣4精選PPT邊鄰接鏈表每一個(gè)頂點(diǎn)有一個(gè)所有與之相鄰的鏈表每一條邊2 個(gè)（對(duì)無向圖）要在兩個(gè)頂點(diǎn)的鏈表中都加入空間復(fù)雜度O(|E|) 對(duì)稀疏圖這種方式比較好圖的表示-鄰接鏈表5精選PPT 圖的鄰接鏈表的Pascal和C+實(shí)現(xiàn) 具體參見NOIP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)ppt圖的表示-C/P語言程序?qū)崿F(xiàn)6精選PPT圖的深度優(yōu)先(Depth-First)遍歷:鄰接鏈表、C+圖的表示-圖的遍歷/圖的一般結(jié)構(gòu) struct graph_node ; struct AdjList int id; AdjList *next; ; int n_nodes,S_index=0; graph_node nodes ma

3、xN ; int visited maxN ; AdjList *adj maxN ;標(biāo)識(shí)項(xiàng)點(diǎn)有沒有訪問過每個(gè)頂點(diǎn)都有鄰接鏈表鄰接鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)7精選PPT圖的深度優(yōu)先(Depth-First)遍歷:鄰接鏈表、C+圖的表示-圖的遍歷置每個(gè)點(diǎn)標(biāo)識(shí)為“未訪問”從所有未被訪問的點(diǎn)k出發(fā)，調(diào)用DFS(k)void search( ) int k; for(k=0;kn_nodes;k+) visitedk = 0; for(k=0;knext) if ( !visitedj-id ) DFS( j-id ); 8精選PPT圖的深度優(yōu)先(Depth-First)遍歷:鄰接鏈表、Pascal圖的表示-

4、圖的遍歷/圖的一般結(jié)構(gòu) type graph_node=record end; type AdjList=record id :integer; next :AdjList; end; var n_nodes,S_i:integer; nodes:array1.maxN of graph_node; visited:array1.maxNof integer; adj:array1.maxN of AdjList;標(biāo)識(shí)項(xiàng)點(diǎn)有沒有訪問過每個(gè)頂點(diǎn)都有鄰接鏈表鄰接鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)9精選PPT圖的深度優(yōu)先(Depth-First)遍歷:鄰接鏈表、Pascal圖的表示-圖的遍歷置每個(gè)點(diǎn)標(biāo)識(shí)為“未訪問”

5、從所有未被訪問的點(diǎn)k出發(fā)，調(diào)用DFS(k)procedure search( ); begin k :integer; for k:=1 to n_nodes do visitedk:= 0; for k:=1 to n_nodes do if visitedk0 then DFS( k ); end;置被訪問節(jié)點(diǎn)的“時(shí)間”-次序訪問k的所有相鄰的節(jié)點(diǎn) procedure DFS(k:integer);begin /從k出發(fā)搜索 var j:AdjList ;begin inc(S_i);visitedk:=S_i; j:=adjk; while (jNULL) do begin if vis

6、itedj.id0 then DFS(j.id); j:=j.next;end; end;10精選PPT圖的寬度優(yōu)先(Breadth-First)遍歷:鄰接鏈表、C+圖的表示-圖的遍歷/圖的一般結(jié)構(gòu) struct graph_node ; struct AdjList int id; AdjList *next; ; int n_nodes,S_index=0; graph_node nodes maxN ; int visited maxN ; AdjList *adj maxN ;標(biāo)識(shí)項(xiàng)點(diǎn)有沒有訪問過每個(gè)頂點(diǎn)都有鄰接鏈表鄰接鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)11精選PPT圖的寬度優(yōu)先(Breadth-Fi

7、rst)遍歷:鄰接鏈表、C+圖的表示-圖的遍歷置每個(gè)點(diǎn)標(biāo)識(shí)為“未訪問”從所有未被訪問的點(diǎn)k出發(fā)，調(diào)用BFS(k)void search( ) int k; for(k=0;kn_nodes;k+) visitedk = 0; for(k=0;kn_nodes;k+) if ( !visitedk ) BFS( k ); 12精選PPT圖的寬度優(yōu)先(Breadth-First)遍歷:鄰接鏈表、C+圖的表示-圖的遍歷int q maxN ;void BFS( int k ) int front,back; q0=k; front=back=0; for(;fronnext) if ( !visit

8、edj-id ) q+back=j-id; visitedj-id=+S_index; BFS用的隊(duì)列，一般全局Front=back,隊(duì)列不空訪問k的所有相鄰的節(jié)點(diǎn) 13精選PPT圖的寬度優(yōu)先(Breadth-First)遍歷實(shí)例示意:圖的表示-圖的遍歷14精選PPT目 錄圖的表示鄰接矩陣、鄰接鏈表、圖的遍歷最小生成樹算法 Prim算法、Kruskal算法最短路徑算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法15精選PPT圖的遍歷:鄰接鏈表時(shí)間復(fù)雜度分析每一個(gè)頂點(diǎn)訪問一次每條邊訪問兩次無向圖每條邊出現(xiàn)在兩個(gè)鏈表中O(|V| + |E|) O(|V|2) 對(duì)

9、 稠密圖 |E| |V|2 O(|V|) 對(duì) 稀疏圖 |E| |V| 對(duì)稀疏圖鄰接鏈表的效果非常好！ 圖的表示-圖的遍歷16精選PPT生成樹：一個(gè)|V|個(gè)點(diǎn)的圖，取其中|V|-1條邊，并連接所有的頂點(diǎn)，則組成原圖的一個(gè)生成樹。屬性：|v|-1條邊、連通、無環(huán)。最小生成樹：加權(quán)圖的最小生成樹是一棵生成樹，其所有邊的權(quán)值之和不會(huì)大于其它任何生成樹。簡(jiǎn)單講：找出連接所有點(diǎn)的最低成本路線最小生成樹(MST)-定義紅邊連接了所有頂點(diǎn),所以構(gòu)成一棵生成樹權(quán)和=1+2+4+4+7+8+917精選PPT局域網(wǎng)(net)RQNOJ 某局域網(wǎng)內(nèi)有n(n=100)臺(tái)計(jì)算機(jī)，由于建網(wǎng)時(shí)工作人員的疏忽，現(xiàn)在網(wǎng)內(nèi)存在回路

10、，造成網(wǎng)絡(luò)卡的現(xiàn)象。 我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無網(wǎng)線連接。現(xiàn)在我們需要除去一些連線，使得網(wǎng)絡(luò)中沒有回路，并且被除去網(wǎng)線的f(i,j)最大，請(qǐng)求出這個(gè)最大值。最小生成樹(MST)-實(shí)例一18精選PPT環(huán)屬性：一棵生成樹上，增加一條邊e，再刪除e所在環(huán)上的最大邊，會(huì)得到另一棵“更好”的生成樹(如果e不是最大邊)最小生成樹(MST)-算法原理9419精選PPT剪切屬性：在圖中，剪切將頂點(diǎn)劃分成兩個(gè)不相交集合。交叉邊為地些頂點(diǎn)在兩個(gè)不同集合的邊。對(duì)于任何一個(gè)剪切，各條最小的交叉邊

11、都屬于某個(gè)MST，且每個(gè)MST中都包含一條最小交叉邊。最小生成樹(MST)-算法原理74920精選PPT最小邊原則：圖中權(quán)值最小的邊(如果唯一的話)一定在最小生成樹上。唯一性：一棵生成樹上，如果各邊的權(quán)都不相同，則最小生成樹是唯一的。反之不然。思考：怎樣圖G判斷只有一個(gè)MST？最小生成樹(MST)-算法原理21精選PPT算法描述1：MST_Prim(G, r) (1)將G剪切成兩個(gè)集合A、B，A中只有一個(gè)點(diǎn)r (2)取最小權(quán)的交叉邊(x,y)，xB, yB (3)將y加入A (4)如果已經(jīng)加了n-1條邊，結(jié)束。否則，轉(zhuǎn) (3)算法證明： 根據(jù)剪切屬性 圖(?)最小生成樹(MST)-Prim算法

12、22精選PPT算法要點(diǎn)： 每次求最小權(quán)交叉邊時(shí)，如果都重新計(jì)算，則顯然要枚舉(x,y)- xA ,yB。O(n2)時(shí)間復(fù)雜度。 其實(shí)每次A中只是增加一個(gè)新頂點(diǎn)v，最多有交叉邊(v,y)，修改量只有與v有邊的頂點(diǎn)，為O(n)。 只需記錄下B中的每個(gè)元素y與A所有元素中最小權(quán)邊，則求最小值最多為O(n)-有時(shí)可以用“堆”優(yōu)化。 最小生成樹(MST)-Prim算法23精選PPT算法描述2：MST_Prim(G, r) /從任意點(diǎn)r出發(fā)，生長(zhǎng)成一MST for i=1 to n do disi / 初始化每點(diǎn)到A集合的最小值 inAi false /設(shè)頂點(diǎn)不在A中disr 0 /將r設(shè)為0（或- ），

13、準(zhǔn)備取出for i=1 to n do v get-min() /取dis?中最小的值c和頂點(diǎn)v, inA v true /v放入A中 sum sum+c /c加入MST的總和中 updata( v ) /枚舉交叉邊(v,B),改進(jìn)dis 最小生成樹(MST)-Prim算法24精選PPT算法描述3：MST_Kruskal(G) (1)將G所有條邊按權(quán)從小到大排序；圖mst開始為空 (2)從小到大次序取邊(x,y) (3)若加入邊(x,y)，mst就有環(huán)，則放棄此邊，轉(zhuǎn)(2) (4)將邊(x,y)加入mst，如果已經(jīng)加了n-1條邊，結(jié)束。否則，轉(zhuǎn) (2)算法證明： 根據(jù)剪切屬性 圖(?)最小生成

14、樹(MST)-Kruskal算法25精選PPT算法要點(diǎn)： Kruskal算法的最難點(diǎn)在于怎樣判斷加入邊(x,y)后是否形成了環(huán)。問題可化為： 判斷邊(x,y)的兩個(gè)頂點(diǎn)x,y在圖（實(shí)際是森林）mst中最否已經(jīng)連通。如果已經(jīng)連通，加入邊將形成環(huán)；否則，不形成環(huán)。 并查集： 連通點(diǎn)集之類問題，有高效算法-并查集。最小生成樹(MST)- Kruskal算法26精選PPT并查集： 并查集詳細(xì)內(nèi)容可參見有關(guān)文章。下面是Pascal段：/初始化，使每個(gè)集合只一個(gè)元素。 for i:=1 to n do f i :=i;/查找x所在類的“根”-代表，并壓縮路徑function find_set(x:long

15、int):longint; begin if fxx then fx:=find_set(fx); exit(fx);end;/合并兩個(gè)集合。x,y為兩集合的“根”procedure union(x,y:longint); begin fx:=y;end;最小生成樹(MST)- Kruskal算法27精選PPT并查集： 并查集詳細(xì)內(nèi)容可參見有關(guān)文章。下面是C+片段：/初始化，使每個(gè)集合只一個(gè)元素。 for (i=1;i = n ; i+) f i = i;/查找x所在類的“根”-代表，并壓縮路徑int find_set ( int x) if (fx != x) fx = find_set(

16、fx ); return (fx);/合并兩個(gè)集合。x,y為兩集合的“根”void union(int x,y ) fx = y;最小生成樹(MST)- Kruskal算法28精選PPT算法描述4：MST_Kruskal(G) for i=1 to n do fi i; /初始化并查集 sort( e, e+m); /邊按大小排序c 0; /取邊的計(jì)數(shù)器for i=1 to m do /從小到大取邊 v find_set( ei.v ); /左端點(diǎn)所在連通塊“根” u find_set( ei.u ); /右端點(diǎn)所在連通塊“根” if(v != u) /如果不在同一連通塊 union(v,u)

17、; /合并兩連通塊 sum += gvu; /加入這條邊的權(quán) if (+c = n-1) break; /if 取了n-1條邊，結(jié)束最小生成樹(MST)-Kruskal算法29精選PPT時(shí)間復(fù)雜度分析Prim算法普通的方法 O(|V|2) Prim算法中用“堆”方法 O(|E|+|V|)*log|V|) -對(duì)稀疏圖較好Kruskal算法 O(|E|*log|E| +|N|*A(|V|) -對(duì)稀疏圖較好最小生成樹(MST)-時(shí)間復(fù)雜度30精選PPT1、平面上有N(=3000)個(gè)點(diǎn)，求連通它們的最小生成樹，用什么算法比較好？2、要判斷一條邊是否可以在一棵MST上，怎樣做比較好？3、平面上有K個(gè)水源

18、（井），N個(gè)居民供水點(diǎn)，怎樣用最少的管道使這N個(gè)居民點(diǎn)都能用連接到水源。注：邊只能水源、居民點(diǎn)之間直接相連。最小生成樹(MST)-思考題31精選PPT maintain 有一個(gè)無向圖，有N個(gè)點(diǎn) ，有w條邊。但是一開始，所有的邊都是被破壞了的，即不可用。接下來每一天可以修復(fù)一條邊。注意：兩個(gè)點(diǎn)之間可能有多條邊。 現(xiàn)在的問題是：每一天修復(fù)完一條邊后，無向圖中的任意兩個(gè)結(jié)點(diǎn)都可以連通了嗎？如果還不可以輸出-1，如果可以了，你從已經(jīng)修復(fù)的邊中，選擇一些邊，使得這些邊的總長(zhǎng)度最小，輸出最小值。最小生成樹(MST)-實(shí)例二32精選PPT輸入格式：第一行: 兩個(gè)整數(shù)：N，W。 N (1=N=200) 、 W

19、 (1 = W e.c ，刪除邊x,加入邊e. M*N 1,200,000簡(jiǎn)化算法？ 由于每次只保留N-1條邊，每次重新做Kruskal算法：M*N*logN 9,600,000 大致可行。更可省略排序，用插入法即可： M*N*3 = disy 松馳 若在處理過程中，有兩點(diǎn)x、y出現(xiàn)不符合“三角形定理”，則可改進(jìn)一下松馳： if ( disx+lenxy =0,如果disv disx，則x永遠(yuǎn)不會(huì)松馳v，故v點(diǎn)確定下來。最短路徑-Dijkstra算法SXVdisvdisxA集合B集合40精選PPT第一步，初始化所有頂點(diǎn)距離置 源點(diǎn)置 0 最短路徑-Dijkstra算法41精選PPT第二步，取出

20、S，松馳相鄰點(diǎn)松馳S的相鄰頂點(diǎn)最短路徑-Dijkstra算法源點(diǎn)紅箭頭表示方案前趨點(diǎn)42精選PPTS放入A集合取最近的頂點(diǎn)x最短路徑-Dijkstra算法第三步43精選PPT由對(duì)u松馳由x對(duì)y松馳最短路徑-Dijkstra算法第四步44精選PPTA = s, x 選B中最近的點(diǎn)y最短路徑-Dijkstra算法第五步45精選PPTA = s, x, y 選B中最近點(diǎn) u最短路徑-Dijkstra算法第六步46精選PPTA = s, x, y, u 最后選擇 v最短路徑-Dijkstra算法第七步47精選PPTA = s, x, y, u 紅色箭頭記錄的是最短路徑的前趨點(diǎn)。 最短路徑-Dijkst

21、ra算法第八步48精選PPT算法描述2：SP_Dijkstra(G, s) /求單源s到其它點(diǎn)的最短距離 for i=1 to n do disi / 初始化每點(diǎn)到s距離 inAi false /設(shè)頂點(diǎn)不在A中diss 0 /將diss設(shè)為0，準(zhǔn)備取出for i=1 to n do v get-min() /取dis?中最小的值c和頂點(diǎn)v, inA v true /v放入A中 sum sum+c /c加入MST的總和中 updata( v ) /檢查(v,B),松馳dis? 最短路徑-Dijkstra算法與prim不相同點(diǎn)49精選PPTcooking Bessie喜歡為在外面的奶牛做晚餐，Be

22、ssie按響鈴給他們一個(gè)信號(hào)叫他們進(jìn)來就可以了。 晚餐將在T (1 = T = 1,000,000)毫秒完成，而且Bessie強(qiáng)調(diào)那些想吃她晚餐的奶牛必須準(zhǔn)時(shí)到。 這些牛在F (1 = F = 500)各不同的草地標(biāo)號(hào)為1F用P(1 = P = 10,000)個(gè)雙向的小路連接。 Bessie在第1個(gè)草地， 給出一頭牛走每一條小路所用的時(shí)間，問多少個(gè)草地上的奶牛可以在T毫秒內(nèi)到Bessie 所在的草地，假設(shè)多頭牛可以共享一條路。最短路徑-實(shí)例一50精選PPT 如果邊有負(fù)權(quán)的話，Dijkstra算法是錯(cuò)誤的。這里需要不斷迭代地做“松馳”，直到無“松馳”為止。算法描述3：SP_Bellman(G,

23、s) (1)初始化每點(diǎn)到s點(diǎn)的最短距離為 (2)取所有邊(x,y)，看x能否對(duì)y松馳。 (3)如果沒有任何松馳，則結(jié)束break。 (4)如果松馳次數(shù)N，轉(zhuǎn)(2) (5)否則，圖中有“負(fù)圈”。最短路徑-Bellman-ford算法51精選PPT算法說明：Bellman-ford算法N次迭代就可以判斷圖中是否有“負(fù)環(huán)”。取所有邊有兩種方法： (1)掃描每一點(diǎn)的鄰接鏈表 (2)用有序點(diǎn)對(duì)(x,y)記錄邊時(shí)，可直接取邊。但要請(qǐng)注意對(duì)無向圖，要注意(y,x)也要松馳。對(duì)于求s到某點(diǎn)t的最短距離，可能因?yàn)槠渌胤接小柏?fù)環(huán)”而出現(xiàn)問題，要預(yù)處理。最短路徑-Bellman-ford算法52精選PPT算法描述

24、4：SP_Bellman(G, s) /求單源s到其它點(diǎn)的最短距離 for i=1 to n do disi / 初始化每點(diǎn)到s距離diss 0 /將diss設(shè)為0for i=1 to n do /最多迭代n rel=false; /是否有松馳標(biāo)志 for 每條邊(x,y) /取圖的每一條邊 if( disx+lenxydisy) /不滿足三角形性質(zhì) disy=disx+lenxy; /松馳disy rel=true; if rel = false return 0; /沒有一次松馳，則結(jié)束return -1; /迭代了n次，有負(fù)圈 最短路徑- Bellman-ford算法53精選PPT蟲洞(

25、Wormholes) 在一個(gè)神秘島上，有N(1 = N = 500)個(gè)洞口，標(biāo)號(hào)1.N，它們之間有M (1 = M = 2500) 條通道相連。神秘的是另外還有W (1 = W = 200)條傳說中的時(shí)間蟲洞-當(dāng)?shù)竭_(dá)通道的另一端洞口時(shí)，竟然可以比進(jìn)入的時(shí)間要早！ 你當(dāng)然想進(jìn)行這樣的時(shí)間之旅，希望從一個(gè)洞口s出發(fā)，經(jīng)過幾個(gè)通道，在比出發(fā)早些時(shí)候的時(shí)間回到洞口s。也許還能碰到自己,hehe 根據(jù)給定的地圖，請(qǐng)判斷能否實(shí)現(xiàn)這樣的愿望。最短路徑-實(shí)例二54精選PPT輸入格式： 第一行：一個(gè)整數(shù) F (1 = F = 5)，表示共有F組數(shù)據(jù)。（多組數(shù)據(jù)測(cè)試）每組數(shù)據(jù)：第1行：三個(gè)整數(shù) N M W 第2至

26、M+1行:每行三個(gè)整數(shù) (S, E, T),表示在S與E洞口之間有一個(gè)雙向通道，通過需要T(0 = T = 10,000) 秒。 第M+2至M+W+1行:每行三個(gè)整數(shù) (S, E, T),表示在S與E洞口之間有一個(gè)單向通道，從S到E可以回到之前T(0 = T = 10,000) 秒。輸出格式： 共1.F行，每行對(duì)應(yīng)一組數(shù)據(jù)，如果可以實(shí)現(xiàn)愿望輸出YES,否則輸出NO.最短路徑-實(shí)例二55精選PPT輸入樣例(wormhole.in):23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8最短路徑-實(shí)例二輸出樣例(wormhole.out):NOYES 1233

27、圖2481232413圖156精選PPT分析 首先，把無向邊改成兩個(gè)有向邊，這樣整個(gè)問題成在有向圖中求負(fù)環(huán)問題。 N*(M+W) = 500*（2500+200）0) do v qhead; /隊(duì)頭節(jié)點(diǎn)v for 每條邊(v,i) /與v相連的每一條邊 if( disv+lenvidisi) /不滿足三角形性質(zhì) disi disv+lenvi; /松馳disi if (visi = false) /不在隊(duì)列，則加入隊(duì)列 visi true; count+1; tail+1; qtail = i; visv false;head+1;count-1; /v出隊(duì)列最短路徑- SPFA算法59精選P

28、PTSPFA算法的思考 對(duì)有向圖，s到t的最短路問題仍然有負(fù)環(huán)影響。無向圖呢？怎樣判斷圖上負(fù)環(huán)？ 最短路徑-SPFA算法60精選PPT求每對(duì)節(jié)點(diǎn)之間最短距離問題：例如，求一個(gè)圖的直徑，即所有最短路徑中最長(zhǎng)的。 如果多次調(diào)用單源最短路徑算法，效果并不好。特別是對(duì)有負(fù)邊的圖。如果無負(fù)環(huán)，則有簡(jiǎn)單的Floyd-warshell算法。這是動(dòng)態(tài)規(guī)劃算法。最短路徑-Floyd算法61精選PPT動(dòng)態(tài)規(guī)劃算法定義d i ,j , k 為路徑中間只允許經(jīng)過節(jié)點(diǎn)1k的情況下i到j(luò)的最短路距離它有兩種情況最短路經(jīng)過點(diǎn)k，di,j,k=di,k,k-1+dk,j,k-1最短路不經(jīng)過點(diǎn)k，di,j,k=di,j,k-1

29、 綜合起來，狀態(tài)轉(zhuǎn)移方程為 di,j,k=min di,k,k-1 + dk,j,k-1,di,j,k-1 邊界條件 di,j,0=lenij（不存在的邊權(quán)可為）最短路徑-Floyd算法62精選PPT算法描述6：SP_Floyd( G ) /求每對(duì)節(jié)點(diǎn)的最短距離 for i=1 to n do for j=1 to n do disi,j lenij; / 初始化邊界條件for k=1 to n do /K放在最外層，數(shù)組少一維 for i=1 to n do for j=1 to n do if( disi,k+diskjdisi,j) /狀態(tài)轉(zhuǎn)移 disi,j disik+diskj; 最

30、短路徑- Floyd算法63精選PPTFloyd算法的思考Floyd算法怎樣記錄下最短路徑？Floyd算法怎樣判斷負(fù)環(huán)？求圖中的最小環(huán)問題。最短路徑-Floyd算法64精選PPTDijkstra單源 非負(fù) O(|V|2) 對(duì)稠密圖好可用“堆”優(yōu)化 O(|E|*log|V|) 對(duì)稀疏圖較好Bellman-Ford單源 無負(fù)環(huán) O(|V|*|E|)可先用Dijkstra預(yù)處理優(yōu)化SPFA用更新隊(duì)列優(yōu)化,時(shí)間復(fù)雜度平均好，但不確定。Floyd全源 無負(fù)環(huán) O(|V|2)思考：有多源問題類嗎？ 如果邊權(quán)只有0,1(或0,1,2,3,4)，能否優(yōu)化算法？最短路徑-算法比較65精選PPT最短路徑-實(shí)例三b

31、utter 農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道N只奶牛會(huì)過來舔它，這樣就能做出能賣好價(jià)錢的超甜黃油。 農(nóng)夫John可以訓(xùn)練這些奶牛，讓它們?cè)诼牭解徛晻r(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。 農(nóng)夫John知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛所在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng)（他將把糖放在那）66精選PPT最短路徑-實(shí)例三輸入格式 第一行: 三個(gè)數(shù)，奶牛數(shù)N（1=N=500）, 牧場(chǎng)數(shù)P（2=P=800），牧場(chǎng)間道路數(shù)C (1=C=1450) 第二行到第N+1行:1 到 N 頭奶牛所在的牧場(chǎng)