圖論中搜索算法講座第1頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月圖論中搜索算法和最短路徑算法2第2頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月ReadEuler,readEuler,heisthemasterofusall.

P.-S.deLaplace3第3頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月4第4頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月5第5頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月§1圖_基本概念§2圖的存儲(chǔ)結(jié)構(gòu)

§4最短路徑§3圖的遍歷算法內(nèi)容6第6頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。線性表:

線性結(jié)構(gòu)樹(shù):

層次結(jié)構(gòu)圖:

結(jié)點(diǎn)之間的關(guān)系可以是任意的，即圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。如：

ABCDE第一節(jié):圖的基本概念7第7頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月1圖的定義和基本術(shù)語(yǔ)圖G

是由兩個(gè)集合—頂點(diǎn)集V(G)

和邊集E(G)

組成的，記作G=(V(G)，E(G))，簡(jiǎn)稱(chēng)G=(V，E)。ABCDEABCDEABCDEV是頂點(diǎn)的有窮非空集合

E是兩個(gè)頂點(diǎn)之間的關(guān)系，即邊的有窮集合

8第8頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月無(wú)向圖和有向圖無(wú)向圖:

邊是頂點(diǎn)的無(wú)序?qū)?，即邊沒(méi)有方向性。v1v2v3v5v4上面無(wú)向圖可以表示為：G=(V,E),其中V={v1,v2,v3,v4,v5}E={(v1,v2)

,(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}(v1,v2)表示頂點(diǎn)v1和v2之間的邊，(v1,v2)=(v2,v1)。9第9頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月有向圖:

其邊是頂點(diǎn)的有序?qū)Γ催呌蟹较蛐?。v1v2v4v3V={v1,v2,v3,v4}E={<v1,v2>

,<v1,v3>,<v3,v4>,<v4,v1>,<v2,v1>}在有向圖中，通常邊稱(chēng)為弧，<v1,v2>表示頂點(diǎn)v1到v2的弧。稱(chēng)v1為弧尾，稱(chēng)v2為弧頭。<v1,v2>≠<v2,v1>上面有向圖可以表示為：G=(V,E),其中10第10頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月帶權(quán)無(wú)向圖(無(wú)向網(wǎng))和帶權(quán)有向圖(有向網(wǎng))有時(shí)對(duì)圖的邊或弧賦予相關(guān)的數(shù)值，這種與圖的邊或弧相關(guān)的數(shù)值叫做權(quán)。

這種帶權(quán)的圖通常稱(chēng)為網(wǎng)。

帶權(quán)的有向圖稱(chēng)為有向網(wǎng)。帶權(quán)的無(wú)向圖稱(chēng)為無(wú)向網(wǎng)。ABCDE53821497這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離?？梢员硎緩囊粋€(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的耗費(fèi)。11第11頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月子圖假設(shè)有兩個(gè)圖

G=(V,E)和

G’=(V’,E’)，如果

V’V，且

E’E，則稱(chēng)

G’

為

G

的子圖。

v1v2v4v3求子圖v1v1v3v1v4v3v1v2v4v3v1v2v4v312第12頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月鄰接與關(guān)聯(lián)對(duì)于無(wú)向圖

G=(V,E)，如果邊

(v,v’)∈E，則稱(chēng)頂點(diǎn)

v和

v’互為鄰接點(diǎn)，即

v

和

v’

相鄰接。

邊

(v,v’)依附于頂點(diǎn)

v和

v’，或者說(shuō)

(v,v’)

與頂點(diǎn)

v

和

v’

相關(guān)聯(lián)。

對(duì)于有向圖

G=(V,E)，如果弧

<v,v’>∈E，則稱(chēng)頂點(diǎn)

v鄰接到頂點(diǎn)

v’，頂點(diǎn)

v’鄰接自頂點(diǎn)

v。

vv’vv’弧<v,v’>

和頂點(diǎn)v,v’

相關(guān)聯(lián)。13第13頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月頂點(diǎn)的度對(duì)于無(wú)向圖，頂點(diǎn)

v的度是和

v相關(guān)聯(lián)的邊的數(shù)目，記做TD(v)。

v1v2v3v5v4頂點(diǎn)v3的度為

3對(duì)于有向圖，頂點(diǎn)

v的度

TD(V)分為兩部分——出度、入度。

以頂點(diǎn)

v為頭的弧的數(shù)目稱(chēng)為

v的入度，記為ID(v)

；以頂點(diǎn)

v為尾的弧的數(shù)目稱(chēng)為

v的出度，記為OD(v)；

頂點(diǎn)

v的度為T(mén)D(v)=ID(v)+OD(v)。

14第14頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v4v3頂點(diǎn)v1

的出度為2頂點(diǎn)v1

的入度為1頂點(diǎn)v1

的度為315第15頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月路徑、鏈、簡(jiǎn)單路徑、回路(環(huán))、簡(jiǎn)單回路無(wú)向圖G中若存在一條有窮非空序列w=v0e1

v1e2

v2

ek

vk

，其中vi和ei分別為頂點(diǎn)和邊，則稱(chēng)w

是從頂點(diǎn)v0到vk的一條路徑?！旤c(diǎn)v0和vk分別稱(chēng)為路徑

w

的起點(diǎn)和終點(diǎn)。路徑的長(zhǎng)度是路徑上的邊的數(shù)目。v0v1v2vk-1vk...e1e2ek起點(diǎn)和終點(diǎn)相同的路徑稱(chēng)為回路(環(huán))。16第16頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月若路徑w的邊e1,e2,,ek

互不相同，則稱(chēng)w為鏈?！袈窂絯的頂點(diǎn)v0,v1,,vk

互不相同，則稱(chēng)w為簡(jiǎn)單路徑?！璿0v1v2vk-1vk...e1e2ek鏈?zhǔn)欠駷楹?jiǎn)單路徑?簡(jiǎn)單路徑是否為鏈?不一定一定e1e2e3e4e5除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱(chēng)為簡(jiǎn)單回路(簡(jiǎn)單環(huán))。17第17頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月例157324G26路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，118第18頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月有向圖G中若存在一條有窮非空序列w=v0e1

v1e2

v2

ek

vk

，其中vi和ei分別為頂點(diǎn)和弧，則稱(chēng)w

是從頂點(diǎn)v0到vk的一條路徑。…v0v1v2vk-1vk...e1e2ek鏈簡(jiǎn)單路徑回路簡(jiǎn)單回路19第19頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，320第20頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月連通、連通圖無(wú)向圖G，如果從頂點(diǎn)

v

到頂點(diǎn)

v’

有路徑，則稱(chēng)

v

和

v’

是連通的。

如果對(duì)于無(wú)向圖

G

中任意兩個(gè)頂點(diǎn)

vi,vj

∈V,vi和

vj都是連通的，則稱(chēng)

G是連通圖。

v1v2v3v5v4是否為連通圖21第21頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月第2節(jié)圖的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)鄰接矩陣鏈?zhǔn)酱鎯?chǔ)鄰接表鄰接多重表十字鏈表如何表達(dá)頂點(diǎn)之間存在的聯(lián)系？v1v2v4v322第22頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月2.1鄰接矩陣設(shè)圖G=(V，E)具有n(n≥1)個(gè)頂點(diǎn)v1,v2,,vn

和m

條邊或弧e1,e2,,em

，則G的鄰接矩陣是n×n

階矩陣，記為A(G)

?！涿恳粋€(gè)元素aij

定義為:鄰接矩陣存放n

個(gè)頂點(diǎn)信息和n2

條邊或弧信息。aij=01頂點(diǎn)vi與vj不相鄰接頂點(diǎn)vi與vj相鄰接v1v2v4v3例有向圖GA(G)=12341234011000000001100023第23頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v3v5v4例無(wú)向圖G0101010101010111010001100A(G)=1234512345優(yōu)點(diǎn):1.容易判斷任意兩個(gè)頂點(diǎn)之間是否有邊或弧。2.容易求取各個(gè)頂點(diǎn)的度。24第24頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月無(wú)向圖，頂點(diǎn)vi

的度是鄰接矩陣中第

i行或第

i列的元素之和。例G中，v1

的度為2。v1v2v3v5v4例無(wú)向圖G0101010101010111010001100A(G)=123451234525第25頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v4v3例有向圖GA(G)=123412340110000000011000有向圖，頂點(diǎn)vi

的出度是鄰接矩陣中第

i行的元素之和。頂點(diǎn)vi

的入度是鄰接矩陣中第

i列的元素之和。例v1

的出度為2；入度為1。26第26頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月無(wú)向圖的鄰接矩陣都是對(duì)稱(chēng)矩陣。有向圖的鄰接矩陣一般不對(duì)稱(chēng)。12341234011000000001100001010101010101110100011001234512345故無(wú)向圖可以采用壓縮存儲(chǔ)方式無(wú)向圖有向圖27第27頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月帶權(quán)圖(網(wǎng))的鄰接矩陣v1v2v3v5v4v65487935651aij=

wij∞頂點(diǎn)vi與vj相鄰接頂點(diǎn)vi與vj不相鄰接∞5∞7∞∞∞∞4∞∞∞

8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞A=

123456123456

3∞∞∞1∞28第28頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月鄰接矩陣存儲(chǔ)的缺點(diǎn)：這種存貯方式的空間復(fù)雜度正比于圖的結(jié)點(diǎn)個(gè)數(shù)的平方，所以，當(dāng)圖中結(jié)點(diǎn)很多但邊卻很少時(shí)，采用這種結(jié)構(gòu)會(huì)造成很大的浪費(fèi)。29第29頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月2.2鄰接表對(duì)圖中每一個(gè)頂點(diǎn)建立一個(gè)單鏈表，指示與該頂點(diǎn)關(guān)聯(lián)的邊或出弧。vexinfofirstarcadjvexnextarcarcinfo表結(jié)點(diǎn)頭結(jié)點(diǎn)adjvex:鄰接頂點(diǎn)位置arcinfo:邊的信息nextarc

:下一條關(guān)聯(lián)邊結(jié)點(diǎn)vexinfo:頂點(diǎn)的信息firstarc:第一條關(guān)聯(lián)邊結(jié)點(diǎn)v1v2v3v5v4v6548793565130第30頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v3v5v4例無(wú)向圖Ge1e2e3e4e5e612345v1v2v3v4v54e22e1∧5e43e31e1∧5e64e52e3∧3e51e2∧3e62e4∧如何獲取頂點(diǎn)的度？頂點(diǎn)vi

的度為第i條鏈表中的結(jié)點(diǎn)數(shù)。需要多少存儲(chǔ)空間？n+2e31第31頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v4v3例有向圖Ge1e2e3e41234v1v2v3v43e22e1∧∧4e3∧1e4∧32第32頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月鄰接矩陣與鄰接表存儲(chǔ)空間求頂點(diǎn)的度求頂點(diǎn)的鄰接頂點(diǎn)鄰接表省一樣一樣判斷兩個(gè)頂點(diǎn)是否關(guān)聯(lián)鄰接矩陣方便0101010101010111010001100123451234512345v1v2v3v4v54e22e1∧5e43e31e1∧5e64e52e3∧3e51e2∧3e62e4∧33第33頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月3圖的遍歷與樹(shù)的遍歷類(lèi)似，如果從圖中某一頂點(diǎn)出發(fā)訪遍圖中所有頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程稱(chēng)為圖的遍歷。圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。通常有兩條遍歷圖的路徑:深度優(yōu)先搜索、廣度優(yōu)先搜索。圖的遍歷相對(duì)復(fù)雜，為了避免同一個(gè)頂點(diǎn)被訪問(wèn)多次，增設(shè)一個(gè)輔助的布爾數(shù)組visited[0..n-1]

指示頂點(diǎn)是否已被訪問(wèn)過(guò)。34第34頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月3.1深度優(yōu)先搜索深度優(yōu)先搜索是類(lèi)似于樹(shù)的一種先序遍歷v1v2v3v5v4v6v7v8圖可分為三部分:基結(jié)點(diǎn)第一個(gè)鄰接結(jié)點(diǎn)導(dǎo)出的子圖其它鄰接頂點(diǎn)導(dǎo)出的子圖深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v735第35頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月1.從圖中某個(gè)頂點(diǎn)v

出發(fā)，訪問(wèn)此頂點(diǎn)；2.然后依次從v

的未被訪問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷；3.直至圖中所有和v

有路徑相通的頂點(diǎn)都被訪問(wèn)到。4.若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)做起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到。算法描述:36第36頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月深度優(yōu)先遍歷算法(DFS)遞歸算法開(kāi)始訪問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問(wèn)過(guò)結(jié)束NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)DFSVi=Vi+1Vi==Vexnums結(jié)束NNYY37第37頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月visited[v]=TRUE

；printf(v)；//訪問(wèn)此頂點(diǎn)for(w=FirstAdjVex(G,v)；w>=0；w=NextAdjVex(G,v,w))if(!visited[w])DFSTraverse(G,w)

；returnOK；voidDFSTraverse(GraphG，intv){//visited[0..n-1]初始為0；v指示頂點(diǎn)在數(shù)組中的位置；}38第38頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v3v5v4v6v7v8過(guò)程分析v1v2v3v4v6v8v5v7深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v739第39頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月棧實(shí)現(xiàn)深度優(yōu)先搜索v1v2v3v4v6v8v5v7深度優(yōu)先搜索順序:v1v2v4v8v5v3v6v7v1v2v4v8v5v3v6v7總是從棧頂出發(fā)搜索！40第40頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月initstack(S)；visited[v]=TRUE；Push(S,v)；printf(v)；Gettop(S,v)；for(w=FirstAdjVex(G,v)；w>=0；w=NextAdjVex(G,v,w))if(!visited[w]){visited[w]=TRUE；Push(S,w)；printf(w)；Gettop(S,v)；}Pop(S)；while(!StackEmpty(S)){}voidDFSTraverse(GraphG，intv){}41第41頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月深度優(yōu)先搜索的C語(yǔ)言實(shí)現(xiàn)：typedefstructnode{intadjvex;//鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置structnode*next;//鏈域，指示下一條邊或弧}JD;//表頭接點(diǎn)：typedefstructtnode{intvexdata;//存放頂點(diǎn)信息structnode*firstarc;//指示第一個(gè)鄰接點(diǎn)}TD;TDga[M];//ga[0]不用v1v2v3v5v4e1e2e3e4e5e642第42頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月voidtraver(TDg[],intn){inti;staticintvisited[M];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0) dfs(g,i,visited);}43第43頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月voiddfs(TDg[],intv,intvisited[]){JD*w;inti;printf("%d",v);visited[v]=1;w=g[v].firstarc;while(w!=NULL){i=w->adjvex;if(visited[i]==0) dfs(g,i,visited);w=w->next;}}44第44頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月3.2廣度優(yōu)先搜索廣度優(yōu)先搜索類(lèi)似于樹(shù)的層次遍歷，廣度優(yōu)先搜索順序:v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父輩結(jié)點(diǎn)被訪問(wèn)后才會(huì)訪問(wèn)子孫結(jié)點(diǎn)！把圖人為的分層，按層遍歷。45第45頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月1.從圖中某個(gè)頂點(diǎn)v

出發(fā)，訪問(wèn)此頂點(diǎn)；2.然后依次訪問(wèn)v

的各個(gè)未曾訪問(wèn)的鄰接點(diǎn)；4.直至圖中所有和v

有路徑相通的頂點(diǎn)都被訪問(wèn)到。5.若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)做起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到。3.然后依次從這些鄰接點(diǎn)出發(fā)再依次訪問(wèn)它們的鄰接點(diǎn)；算法描述:46第46頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月v1v2v3v5v4v6v7v8過(guò)程分析廣度優(yōu)先搜索順序:v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v847第47頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月廣度優(yōu)先遍歷算法開(kāi)始標(biāo)志數(shù)組初始化Vi=1Vi訪問(wèn)過(guò)BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY48第48頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月開(kāi)始訪問(wèn)V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問(wèn)過(guò)結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問(wèn)w,置標(biāo)志w入隊(duì)NaaY49第49頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索算法InitQueue(Q)；visited[v]=TRUE；EnQueue(Q,v)

；printf(v)；DeQueue(Q,u)；while(!QueueEmpty(Q)){}voidBFSTraverse(GraphG，intv){//visited[0..n-1]初始均為0；v指示頂點(diǎn)在數(shù)組中的位置；}for(w=FirstAdjVex(G,u)；w>=0；w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE；EnQueue(Q,w)；printf(w)；}//其鄰接頂點(diǎn)均送入隊(duì)列50第50頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月4最短路徑ABCGFED旅客希望停靠站越少越好，則應(yīng)選擇A——B——C——G旅客考慮的是旅程越短越好，1120920720210540340640190A——D——E——F——G51第51頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月帶權(quán)圖的最短路徑計(jì)算問(wèn)題通常在實(shí)際中，航運(yùn)、鐵路、船行都具有有向性，故我們以帶權(quán)有向圖為例介紹最短路徑算法。帶權(quán)無(wú)向圖的最短路徑算法也通用。從單個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑算法。52第52頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月4.1從單個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑算法——Dijkstra算法思想:貪心算法(局部最優(yōu))，按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑。貪心算法:利用局部最優(yōu)來(lái)計(jì)算全局最優(yōu)。利用已得到的頂點(diǎn)的最短路徑來(lái)計(jì)算其它頂點(diǎn)的最短路徑。例，v5v0v1v4v3601005v21030201050求從v0

到其余各頂點(diǎn)的最短路徑。1.初始，D[i]

的值為v0

到vi

的弧的權(quán)值D[i]

表示v0

到vi

的最短路徑的長(zhǎng)度顯然，D[i]

中的最小值D[2]

便是v0到v2

的最短路徑的長(zhǎng)度，Path[2]=(v0,v2)Path[i]表示v0

到vi

的最短路徑53第53頁(yè)，課件共57頁(yè)，創(chuàng)作于2023年2月設(shè)下一條最短路徑的終點(diǎn)是vk

，則這條最短路徑或者是(v0,vk)

、或者是v0經(jīng)過(guò)v2

或v4到達(dá)vk

的路徑；2.如何尋找下一條最短路徑？例，v5v0v1v4v3601005v21030201050設(shè)下一條最短路徑的終點(diǎn)是vj

，則這條最短路徑或者是(v0,vj)、或者是

v0經(jīng)過(guò)v2到達(dá)vj

的路徑；其中取D[i](D[2]除外)中的最小值得到v4，Path[4]=(v0,v4)。3.如何尋找下一條最短路徑？取D[i](D[2]、D[4]除外)

中的最小值得到v3

，Path[3]=(v0,v4,v