第七章圖（Graphs)課件

第七章圖（Graphs),圖的基本概念圖的存儲(chǔ)表示圖的遍歷最小生成樹活動(dòng)網(wǎng)絡(luò)最短路徑,圖例,結(jié)點(diǎn),邊:(v2,v5),圖的構(gòu)成：結(jié)點(diǎn)集：V=v1,v2,v3,v4,v5,邊集：E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),圖例,有向邊V3：始點(diǎn)，v4:終點(diǎn),圖的構(gòu)成：結(jié)點(diǎn)集：V=v1,v2,v3,v4,有向邊集：E=,圖的概念,圖是由頂點(diǎn)(vertex)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph(V,E)其中V=x|x某個(gè)數(shù)據(jù)對(duì)象是頂點(diǎn)的有窮非空集合；E=|x,yV是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)的集合。,有向圖G1V1=v1,v2,v3,v4,E1=,無向圖G2V2=v1,v2,v3,v4,v5,E2=,或者E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(a)G1=(V1,E1),(b)G2=(V2,E2),圖的術(shù)語,v3鄰接到v4,v4的入度ID(v4)=1,v1的出度OD(v4)=1,性質(zhì):入度之和=出度之和=邊數(shù),結(jié)點(diǎn)的度數(shù):TD(v)=ID(v)+OD(v),v1和v4互為鄰接點(diǎn),v4的度數(shù)為2TD(v4)=2,度數(shù)之和=邊數(shù)的二倍（因?yàn)槊總€(gè)邊“貢獻(xiàn)”了兩個(gè)度數(shù)）,子圖設(shè)有兩個(gè)圖G(V,E)和G(V,E)。若VV且EE,則稱圖G是圖G的子圖。權(quán)某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。完全圖若有n個(gè)頂點(diǎn)的無向圖有n(n-1)/2條邊,則此圖為完全無向圖。有n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,則此圖為完全有向圖。,路徑:(1),(簡(jiǎn)單路徑)(2),(環(huán))(3),路徑:在圖G(V,E)中,若存在邊的序列(vi,vp1)、(vp1,vp2)、.、(vpm,vj)則稱頂點(diǎn)序列(vivp1vp2.vpmvj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。,路徑長(zhǎng)度非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和,簡(jiǎn)單路徑若路徑上各頂點(diǎn)v1,v2,.,vm均不互相重復(fù),則稱這樣的路徑為簡(jiǎn)單路徑?；芈啡袈窂缴系谝粋€(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。,連通圖與連通分量在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。,強(qiáng)連通圖在有向圖中,若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。,生成樹一個(gè)連通圖的生成樹是它的極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。,圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣,存儲(chǔ)原則:存儲(chǔ)結(jié)點(diǎn)集和邊集的信息.,（1）存儲(chǔ)結(jié)點(diǎn)集；（2）存儲(chǔ)邊集：存儲(chǔ)每?jī)蓚€(gè)結(jié)點(diǎn)是否有關(guān)系。,圖的存儲(chǔ)結(jié)構(gòu),有向圖的鄰接矩陣,帶權(quán)圖的鄰接矩陣,鄰接矩陣表示法,在圖的鄰接矩陣表示中:有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。,#defineMAX_VERTEX_NUM20/最大頂點(diǎn)個(gè)數(shù)typedefstructVertexTypevexsMAX_VERTEX_NUM；/頂點(diǎn)向量intarcsMAX_VERTEX_NUMMAX_VERTEX_NUM；/鄰接矩陣intvexnum，arcnum；/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph;,容易計(jì)算結(jié)點(diǎn)的度數(shù);容易判定兩個(gè)結(jié)點(diǎn)間是否有邊相連;容易判定結(jié)點(diǎn)之間是否有路徑相連(計(jì)算Am);對(duì)于有向圖，需要n個(gè)單元存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)，n*n個(gè)單元存儲(chǔ)鄰接矩陣；無向圖的鄰接矩陣是對(duì)稱的,可以壓縮存儲(chǔ);存儲(chǔ)量與結(jié)點(diǎn)數(shù)有關(guān),與邊數(shù)無關(guān);若邊數(shù)n2,則鄰接矩陣是稀疏矩陣;,鄰接表,每個(gè)結(jié)點(diǎn)拉出一個(gè)鄰接邊鏈表(以此結(jié)點(diǎn)為始點(diǎn)的所有鄰接點(diǎn)),所有結(jié)點(diǎn)存儲(chǔ)與一個(gè)表中,以A為始點(diǎn)的邊鏈,以A為終點(diǎn)的邊鏈,鄰接表,圖的鄰接表存儲(chǔ)表示,#defineMAX_VERTEX_NUM20typedefstructArcNode/單鏈表結(jié)點(diǎn)結(jié)構(gòu)intadjvex；/該弧所指向的頂點(diǎn)的位置structArcNode*nextarc；/指向下一條弧的指針I(yè)nfoType*info；/該弧相關(guān)信息的指針ArcNode；typedefstructVNode/頂點(diǎn)結(jié)構(gòu)VertexTypedata；/頂點(diǎn)信息ArcNode*firstarc;/指向第一條依附該頂點(diǎn)的弧的指針VNode，AdjListMAX_VERTEX_NUM,Typedefstruct/鄰接表結(jié)構(gòu)AdjListvertices；intvexnum，arcnum；/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph；,頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)；在有向圖中，第i個(gè)鏈表(出邊表)中的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)的出度;,鄰接表的特點(diǎn),求入度必須遍歷整個(gè)鄰接表:在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的入度。為了求入度的便利,可以建立逆鄰接表,即鏈表為入邊表;,設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則用鄰接表表示無向圖時(shí)，需要n個(gè)頂點(diǎn)結(jié)點(diǎn)，2e個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需n個(gè)頂點(diǎn)結(jié)點(diǎn)，e個(gè)邊結(jié)點(diǎn)。,鄰接表,(B,D)邊出現(xiàn)在D的邊鏈表中,(B,D)邊出現(xiàn)在B的邊鏈表中,如果以邊為處理對(duì)象,如刪除一個(gè)邊,則需掃描每個(gè)結(jié)點(diǎn)的邊表,找到同一條邊.,鄰接多重表,將鄰接表中代表同一個(gè)邊的結(jié)點(diǎn)合并;邊表合并為多重表;在鄰接多重表中，每一條邊只有一個(gè)邊結(jié)點(diǎn),為有關(guān)邊的處理提供了方便。,邊結(jié)點(diǎn)結(jié)構(gòu)：,mark:記錄是否處理過的標(biāo)記;ivex,jvex:該邊的兩頂點(diǎn)位置;ilink:指向下一條依附于頂點(diǎn)ivex的邊；jlink:指向下一條依附于頂點(diǎn)jvex的邊。,markivexjverxilinkjlink,typedefemnuunvisited，visitedVisited；typedefstructEBoxVisitedmark；/訪問標(biāo)記intivex，jvex；/該邊依附的兩個(gè)頂點(diǎn)的位置structEBox*ilink，*jlink；/分別指向依附這兩個(gè)頂點(diǎn)的下一條邊InfoType*info；/該邊信息指針EBox；,markivexjverxilinkjlink,data:存放與該頂點(diǎn)相關(guān)的信息，firstedge:指示第一條依附于該頂點(diǎn)的邊的指針,頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)：,datafirstedge,typedefstructVexBoxVertexTypedata；EBox*firstedge/指向第一條依附該頂點(diǎn)的邊VexBox；,typedefstructVexBoxadjmulistMAX_VERTEX_NUM；intvexnum，edgenum；/無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)AMLGraph;,圖的抽象數(shù)據(jù)類型,ADTGraph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R=VRVR=|v，wV且P(v，w)，謂詞P(v，w)定義了弧的意義或信息,基本操作P：CreateGraph(/使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù)for(v=0；v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G，w)；/對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS,每個(gè)結(jié)點(diǎn)最多調(diào)用一次,每個(gè)結(jié)點(diǎn)一次,循環(huán)工作量：尋找結(jié)點(diǎn)v的鄰接點(diǎn),時(shí)間復(fù)雜度：訪問每個(gè)結(jié)點(diǎn)的時(shí)間：O(n);尋找每個(gè)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)工作量;設(shè)圖中有n個(gè)頂點(diǎn)，e條邊。如果用鄰接表表示圖，沿Firstedgelink鏈可以找到某個(gè)頂點(diǎn)v的所有鄰接頂點(diǎn)w。無向圖有2e個(gè)邊結(jié)點(diǎn)，有向圖有e個(gè)邊，所以掃描邊的時(shí)間為O(e);時(shí)間復(fù)雜度為O(n)+O(e)=O(n+e);如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n)+O(n2)=O(n2).,廣度優(yōu)先遍歷,基本思想訪問v1;訪問v1的鄰接點(diǎn)w1,w2,wm;依次訪問w1,w2,的未被訪問的鄰接點(diǎn)，如此進(jìn)行下去，直至訪問完所有結(jié)點(diǎn)。,算法的實(shí)現(xiàn)需要設(shè)置一個(gè)數(shù)組visited標(biāo)記結(jié)點(diǎn)是否訪問過；設(shè)置一個(gè)隊(duì)列紀(jì)錄當(dāng)前層訪問的結(jié)點(diǎn)以備訪問下一層結(jié)點(diǎn)。,取一個(gè)結(jié)點(diǎn)未訪問結(jié)點(diǎn)v,訪問v，標(biāo)記，入隊(duì)；（訪問v的所有鄰接點(diǎn)）：取隊(duì)頭元素，每次取v的下一個(gè)未訪問的鄰接點(diǎn)訪問，標(biāo)記并入隊(duì)；重復(fù)2,直至隊(duì)列空；如果圖中仍然有未訪問的結(jié)點(diǎn)，重復(fù)1，直至所有結(jié)點(diǎn)均已標(biāo)記為訪問過。,基本思想訪問v1;訪問v1的鄰接點(diǎn)w1,w2,wm;依次訪問w1,w2,的未被訪問的鄰接點(diǎn)，如此進(jìn)行下去，直至訪問完所有結(jié)點(diǎn)。,voidBFSTraverse(GraphG，Status(*Visit)(intv)/按廣度優(yōu)先非遞歸遍歷圖G。/使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。for(v=0；vG.vexnum；+v)visitedv=FALSE；InitQueue(Q)；/置空的輔助隊(duì)列Q,for(v=0；vG.vexnum；+v)if(!visitedv)/v尚未訪問visitedv=TRUE；visit(v)；EnQueue(Q，v)；/v入隊(duì)列while(!QueueEmpty(Q)DeQueue(Q，u)/隊(duì)頭元素出隊(duì)并置為ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!Visitedw)/w為u的尚未訪問的鄰接頂點(diǎn)visitedw=TRUE;Visit(w);EnQueue(Q,w);/if/while/if/BFSTraverse,復(fù)雜度與深度優(yōu)先相同,圖的連通性,對(duì)于連通的無向圖，從一個(gè)結(jié)點(diǎn)出發(fā)可以訪問所有結(jié)點(diǎn)；結(jié)點(diǎn)與遍歷時(shí)通過的邊構(gòu)成圖的生成樹；,深度優(yōu)先生成樹,廣度優(yōu)先生成樹,對(duì)于不連通的無向圖，則需從多個(gè)頂點(diǎn)出發(fā)訪問；結(jié)點(diǎn)與遍歷時(shí)經(jīng)過的邊構(gòu)成生成樹林。,深度優(yōu)先生成森林,voidDFSTraverse(GraphG，Status(*visit)(intv)visitFunc=Visit;for(v=0；vlchild=p；first=FALSE；elseq-nextsibling=p；q=p；DFSTree(G,w,q)；/if/DFSTree,T,p,q,最小生成樹,問題：設(shè)在n個(gè)城市間建立通信網(wǎng)絡(luò)，要求建設(shè)費(fèi)用盡可能低。,模型：n個(gè)結(jié)點(diǎn)的圖，結(jié)點(diǎn)連線的權(quán)表示建設(shè)兩點(diǎn)間通信線路的費(fèi)用。在此網(wǎng)絡(luò)的生成樹中找出建設(shè)費(fèi)用最小的生成樹。,最小生成樹,設(shè)G是一個(gè)帶權(quán)的無向圖（網(wǎng)絡(luò)），則G的生成樹可能有多個(gè)，生成樹各邊的權(quán)之和稱為生成樹的權(quán)。網(wǎng)絡(luò)G的具有最小權(quán)的生成樹稱為G的最小生成樹。,模型：n個(gè)結(jié)點(diǎn)的圖，結(jié)點(diǎn)連線的權(quán)表示建設(shè)兩點(diǎn)間通信線路的費(fèi)用。求此網(wǎng)絡(luò)的最小生成樹。,應(yīng)用：設(shè)在n個(gè)城市間建立通信網(wǎng)絡(luò)，要求建設(shè)費(fèi)用盡可能低。,Prim算法,假設(shè)N=(V，E)是連通網(wǎng)，T=(U,TE)表示下列算法構(gòu)造的N上最小生成樹。算法從U=u0(u0V)，TE=開始;重復(fù)執(zhí)行下述操作,直至U=V為止：在所有uU，vV-U的邊(u，v)E中找一條權(quán)最小的邊(u，v)，將v并入U(xiǎn)，同時(shí)邊(u，v)并入集合TE。,設(shè)N有n個(gè)結(jié)點(diǎn).則算法結(jié)束時(shí),T中必有n個(gè)結(jié)點(diǎn),n-1條邊.在2中,如果有相同權(quán)的邊,可任選一條,故最小生成樹不唯一.,例:求下圖的最小生成樹,初始狀態(tài):U=v0,循環(huán):對(duì)于每個(gè)結(jié)點(diǎn)viU，在vi與U中所有結(jié)點(diǎn)的鄰接邊中找出權(quán)最小的邊ei=(vi,uk),并在這些邊ei中求出權(quán)最小的邊,設(shè)為(vi,uk).將uk并入U(xiǎn),(vi,uk)并入構(gòu)造中的生成樹。,MST性質(zhì),定理:假設(shè)N=(V，E)是一個(gè)連通網(wǎng),T=(U,TE)是正在構(gòu)造的生成樹,若(u，v)是一條端點(diǎn)分別在U和V-U,并具有最小權(quán)值的邊，則必存在一棵包含T和邊(u，v)的最小生成樹。,證明:用反證法.設(shè)任何包含T的最小生成樹均不包含邊e=(u,v).設(shè)T是一顆這樣的樹.將e加到T中必然得到一條回路:u,w1,wk,v,u其中必然存在邊e=(wp,wp+1),wpU,wp+1U去掉邊e后打開回路,又形成一顆生成樹T,因?yàn)閃(e)=W(e),故T是一顆包含T和e的最小生成樹.矛盾!,Prim算法的實(shí)現(xiàn),需要設(shè)置一個(gè)數(shù)組closedge,紀(jì)錄當(dāng)前每個(gè)結(jié)點(diǎn)viU到達(dá)U的最小權(quán)邊(vi,uk)的信息,即closedegei為(uk,minimumW(vi,uk)|ukU)structVertexTypeadjvex；VRTypelowcost；closedgeMAX_VERTEX_NUM,初始狀態(tài):U=v0closedge0=(v0,0);/0表示相應(yīng)結(jié)點(diǎn)屬于Uclosedgei=(v0,W(vi,v0),在closedge中選擇最小權(quán)的邊。假設(shè)vkU是closedge中具有最小權(quán)邊的結(jié)點(diǎn),則置closedgeklowcost=0,即將vk并入U(xiǎn)修改closedge:對(duì)于vjU,只需考慮可能出現(xiàn)的新邊(vj,vk)是否具有更小的權(quán)closedgej=minclosedgej.lowcost,W(vj,vk),循環(huán)：,voidMiniSpanTree_PRIM(MGraphG，VertexTypeu)/用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，/輸出T的各條邊。假設(shè)用鄰接矩陣存儲(chǔ)G.k=LocateVex(G，u)；for(j=0；j0)邊printf(closedgek.adjvex,G.vexsk);/輸出生成樹的邊closedgek.lowcost=0;/第k個(gè)頂點(diǎn)并入U(xiǎn)集for(j=0;jG.vexnum;+j)if(G.acrskj.adjclosedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree,時(shí)間復(fù)雜度：O(n)+O(n2)=O(n2),Kruskal算法,假設(shè)連通網(wǎng)N=(V，E)，使用Kruskal構(gòu)造最小生成樹的算法：最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V，)，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選擇代價(jià)最小且頂點(diǎn)落在T中不同的連通分量上的邊，將此邊加入到T中；重復(fù)上述過程2，直至所有頂點(diǎn)都在同一連通分量上為止。,克魯斯卡爾算法構(gòu)造最小生成樹的過程,Kruskal算法可以用堆來實(shí)現(xiàn)。設(shè)e是圖的邊數(shù)，則構(gòu)造最小生成樹的總時(shí)間代價(jià)是O(eloge).,可見，Prim算法適合于邊數(shù)多的圖，而Kruskal算法適合于邊數(shù)少(eadivex；/對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(！(-indegreek)Push(S，k)；/若入度減為0，則入棧/for/whileif(countadivex；/對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(！(-indegreek)Push(S，k)；/若入度減為0，則入棧/for/whileif(countvej)vej=r;當(dāng)j的所有前驅(qū)已經(jīng)排序時(shí),vej便是所求的值.,datafirstarc,StatusTopologicalOrder(ALGraphG，Stack/i號(hào)頂點(diǎn)入T棧并計(jì)數(shù)for(p=G.verticesi.firstarc；p；p=p-nextarc)j=p-adjvex；/對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(-indegreej=0)Push(S，j)；/若入度減為0，則入棧if(vei+*(p-info)vej)vej=vei+*(p-info)；/for*(p-info)=dut()/whileif(countadjvex；dut=*(p-info)；/dutif(vlk-dutadjvex；dut=*(p-info)；ee=vej；el=vlk-dut；tag=(ee=e1)?*：；printf(j，k，dut，ee，el，tag)；/輸出關(guān)鍵活動(dòng)/CriticalPath,在拓?fù)渑判蚯髒ei和逆拓?fù)溆行蚯髒li時(shí),所需時(shí)間為O(n+e),求各個(gè)活動(dòng)的ek和lk時(shí)所需時(shí)間為O(e),總時(shí)間復(fù)雜度仍然是O(n+e)。,最短路徑,問題的提出：一位旅客要從A城到B城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時(shí)間最短的路線；他希望選擇一條途中費(fèi)用最小的路線；,這些問題均是帶權(quán)圖上的最短路徑問題。,邊上的權(quán)表示一站邊上的權(quán)代表距離邊的權(quán)代表費(fèi)用,設(shè)G是帶權(quán)有向圖，稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)(Source)，最后一個(gè)頂點(diǎn)為終點(diǎn)(Destination)；一條路經(jīng)的長(zhǎng)度是路徑上邊的權(quán)之和；最短路徑問題：如果從圖中某一頂點(diǎn)出發(fā)到達(dá)另一頂點(diǎn)的路徑可能不止一條，如何找到一條長(zhǎng)度最小的路徑。,單源最短路徑問題：設(shè)G是帶權(quán)(=0)有向圖，給定一個(gè)頂點(diǎn)v，求v到其余頂點(diǎn)的最短距離。,最短路徑的Dijkstra算法,Dijkstra算法基本思想:按路徑長(zhǎng)度的遞增次序，逐步產(chǎn)生最短路徑.設(shè)源點(diǎn)為v0首先求出v0為源點(diǎn)長(zhǎng)度最短的一條最短路徑，即具有最小權(quán)的邊;求出源點(diǎn)到各個(gè)頂點(diǎn)下一個(gè)最短路徑：設(shè)其終點(diǎn)是u，則v0到u的最短路徑或者是邊，或者由一條已求得的最短路徑（v0v)和邊構(gòu)成；重復(fù)2直到從頂點(diǎn)v0到其它各頂點(diǎn)的最短路徑全部求出為止。,例：求v0其他各點(diǎn)的最短路徑用S表示已求出最短路徑的結(jié)點(diǎn)集初始狀態(tài)：S=v0,第一條最短路徑：(v0,v2)S=v0,v2,求下一條最短路徑：先求v0到其他頂點(diǎn)vi的只經(jīng)過S結(jié)點(diǎn)的路徑：,v0-v1:v0-v3:(v0,v2,v3)60v0-v4:(v0,v4)30v0-v5:(v0,v5)100,第二條最短路徑：(v0,v4)，S=v0,v2,v4,第一條最短路徑：(v0,v2)S=v0,v2,求下一條最短路徑：先求v0到其他頂點(diǎn)vi的只經(jīng)過S結(jié)點(diǎn)的路徑：,v0-v1:v0-v3:(v0,v2,v3)60,(v0,v4,v3)50v0-v5:(v0,v5)100,(v0,v4,v5)90,第二條最短路徑：(v0,v4)，S=v0,v2,v4,第三條最短路徑：(v0,v4,v3)，S=v0,v2,v4,v3,第四條最短路徑：(v0,v4,v3,v5)，S=v0,v2,v4,v3,v5,用S表示當(dāng)前找到最短路徑的終點(diǎn)集；引入一個(gè)輔助數(shù)組D