數(shù)據(jù)結(jié)構(gòu)與算法6

第6章圖（4課時(shí)）圖也是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，它比樹結(jié)構(gòu)更為復(fù)雜。在樹結(jié)構(gòu)中，各數(shù)據(jù)元素之前有著明顯的層次關(guān)系，上一層中的一個(gè)前繼結(jié)點(diǎn)對(duì)應(yīng)下一層中的d（d≥0）個(gè)后繼結(jié)點(diǎn)，但下一層中的一個(gè)后繼結(jié)點(diǎn)最多只與上一層中的一個(gè)前繼結(jié)點(diǎn)相關(guān)，因此，樹型結(jié)構(gòu)主要是用來表示數(shù)據(jù)元素之間一對(duì)多的關(guān)系。而在圖結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)結(jié)點(diǎn)都可能相關(guān)，圖結(jié)構(gòu)可以用來表示數(shù)據(jù)元素之間多對(duì)多的關(guān)系。6.1

圖的基本概念及特性6.1.1圖的基本概念6.1.2用圖來描述實(shí)際問題6.1圖的基本概念及特性6.1.1圖的基本概念圖G由頂點(diǎn)（圖中通常將結(jié)點(diǎn)稱為頂點(diǎn)）的非空有限集合V和邊的集合E組成，記為G=(V,E)。每一個(gè)頂點(diǎn)偶對(duì)就是圖中的一條邊，所以，E用于表示V上的連接關(guān)系。在一個(gè)圖中，至少要包含一個(gè)頂點(diǎn)，但可以沒有任何邊。通常用V(G)和E(G)來表示圖G的頂點(diǎn)集合和邊集合。下面給出圖的基本術(shù)語。1.有向圖和無向圖若E(G)中的頂點(diǎn)偶對(duì)是有序的，則這些有序偶對(duì)就形成了有向邊，此時(shí)圖G稱為有向圖。其中，有向邊也簡(jiǎn)稱為弧。在有向圖G中，對(duì)于一條從頂點(diǎn)vi到頂點(diǎn)vj的弧，記作<vi,vj>并有<vi,vj>∈E(G)，稱vi為弧尾，vj為弧頭。例如，圖6-1（a）中所示的G1是一個(gè)有向圖，其頂點(diǎn)集合V(G1)={v0,v1,v2,v3,v4}，邊集合E(G1)={<v0,v1>,<v0,v2>,<v1,v4>,<v2,v0>,<v3,v0>,<v3,v2>}。6.1圖的基本概念及特性6.1.1圖的基本概念2.頂點(diǎn)的度、入度和出度在無向圖G中，若存在(vi,vj)∈E(G)，則稱頂點(diǎn)vi和頂點(diǎn)vj互為鄰接點(diǎn)，即頂點(diǎn)vi和頂點(diǎn)vj相鄰接，或者說頂點(diǎn)vi、vj與邊(vi,vj)相關(guān)聯(lián)。與頂點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為頂點(diǎn)vi的度，記作D(vi)。例如，圖6-1（b）所示的無向圖G2中，各頂點(diǎn)的度分別為：D(v0)=3，D(v1)=D(v2)=D(v3)=2，D(v4)=1。在有向圖G中，若存在<vi,vj>∈E(G)，則稱頂點(diǎn)vi鄰接到頂點(diǎn)vj，或頂點(diǎn)vj鄰接自頂點(diǎn)vi。以頂點(diǎn)vi為弧頭的弧的數(shù)目稱為頂點(diǎn)vi的入度，記作ID(vi)；以頂點(diǎn)vi為弧尾的弧的數(shù)目稱為vi的出度，記作OD(vi)；頂點(diǎn)vi的入度和出度之和稱為vi的度，記作D(vi)。6.1圖的基本概念及特性6.1.1圖的基本概念3.路徑、路徑長度和回路

在圖G中，若存在一個(gè)頂點(diǎn)序列(,,…,)，使得對(duì)于任意0≤j<n-1有（若G為有向圖）或（若G為無向圖），則該序列是從頂點(diǎn)到頂點(diǎn)的一條路徑。顯然，從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑不一定唯一。一條路徑中邊的數(shù)目稱為路徑長度。在一條路徑中，若一個(gè)頂點(diǎn)至多只經(jīng)過一次，則該路徑稱為簡(jiǎn)單路徑；若組成路徑的頂點(diǎn)序列中第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同，則該路徑稱為回路（或環(huán)）；在一個(gè)回路中，若除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)外，其他頂點(diǎn)只出現(xiàn)一次，則該回路稱為簡(jiǎn)單回路（或簡(jiǎn)單環(huán)）。6.1圖的基本概念及特性6.1.1圖的基本概念4.連通圖對(duì)無向圖，若至少存在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑，則稱頂點(diǎn)vi和頂點(diǎn)vj是連通的。若無向圖G中任意兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖。

對(duì)有向圖，若存在從頂點(diǎn)vi到頂點(diǎn)vj的路徑或存在從頂點(diǎn)vj到頂點(diǎn)vi的路徑，則稱頂點(diǎn)vi和頂點(diǎn)vj是單向連通的；若兩條路徑同時(shí)存在則稱頂點(diǎn)vi和頂點(diǎn)vj是強(qiáng)連通的。有向圖G中，若任意兩個(gè)頂點(diǎn)都是單向連通的，則稱G是單向連通圖；若任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱G為強(qiáng)連通圖。6.1圖的基本概念及特性6.1.1圖的基本概念5.子圖、連通分量和強(qiáng)連通分量

對(duì)于圖G、G'，若滿足且，則G'是G的子圖。也就是說，從圖G的頂點(diǎn)集合中選出一個(gè)子集并從邊集合中選出與該頂點(diǎn)子集相關(guān)的一些邊所構(gòu)成的圖，就是圖G的子圖。

一個(gè)無向圖的極大連通子圖稱為該無向圖的連通分量；一個(gè)有向圖的極大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。這里的“極大”是指向連通子圖或強(qiáng)連通子圖中再添加一個(gè)頂點(diǎn)，該子圖就不再連通或強(qiáng)連通。顯然，若一個(gè)圖本身就是連通圖或強(qiáng)連通圖，那么它的連通分量或強(qiáng)連通分量就是圖本身，具有唯一性。若一個(gè)圖本身是非連通圖或非強(qiáng)連通圖，那么它的連通分量可能有多種形式。

6.1圖的基本概念及特性6.1.1圖的基本概念

例如，圖6-2（a）和圖6-2（c）分別是非連通圖和非強(qiáng)連通圖，對(duì)應(yīng)的兩種形式的連通分量和強(qiáng)連通分量分別如圖6-2（b）和圖6-2（d）所示。

6.1圖的基本概念及特性6.1.1圖的基本概念6.權(quán)和帶權(quán)圖

與前一章學(xué)習(xí)的樹中結(jié)點(diǎn)的權(quán)相似，可以為一個(gè)圖中的每條邊標(biāo)上一個(gè)具有某種意義的實(shí)數(shù)，該實(shí)數(shù)就稱為是邊的權(quán)。通常用邊的權(quán)表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的代價(jià)。邊上帶權(quán)的圖就稱為帶權(quán)圖。

6.1圖的基本概念及特性6.1.1圖的基本概念7.生成樹和最小生成樹

若無向圖G的一個(gè)子圖G'是一棵包含圖G所有頂點(diǎn)的樹，則G'稱為圖G的生成樹。生成樹本身是一棵樹，具備樹的所有性質(zhì)。對(duì)于樹中的任一結(jié)點(diǎn)，根結(jié)點(diǎn)都是其祖先，因此樹中的任意兩個(gè)結(jié)點(diǎn)都是連通的，即子圖G'是連通圖。另一方面，子圖G'與圖G具有相同的頂點(diǎn)集合，而子圖G'的邊集合是圖G邊集合的子集，因此圖G必然也是連通圖。也就是說，只有連通圖才有生成樹。

連通圖的生成樹不具有唯一性，從不同的頂點(diǎn)出發(fā)或采用不同的遍歷算法，可以得到不同的生成樹。6.1圖的基本概念及特性6.1.1圖的基本概念例如，圖6-3（b）所示的就是根據(jù)圖6-3（a）得到的兩種不同形式的生成樹。在所有形式的生成樹中，邊上的權(quán)之和最小的生成樹，稱為最小生成樹。

6.1圖的基本概念及特性6.1.1圖的基本概念下面通過兩個(gè)實(shí)例介紹如何用圖來描述實(shí)際問題?！纠?-1】有若干個(gè)城市，通過在兩個(gè)城市之間修建高速公路使得從任一城市出發(fā)經(jīng)過高速公路都可以到達(dá)另一城市。為了使修建高速公路的工程總造價(jià)最低，應(yīng)如何設(shè)計(jì)？

該問題的圖描述如下：將所有城市作為圖的頂點(diǎn)，任意兩個(gè)頂點(diǎn)相連接形成邊，兩個(gè)城市之間修建高速公路的工程造價(jià)作為邊的權(quán)。顯然，邊沒有方向，因此對(duì)于該問題應(yīng)使用無向圖表示。

如圖6-4（a）所示是該問題的一個(gè)圖描述示例，這里考慮4個(gè)城市，任意兩個(gè)城市之間修建高速公路的工程造價(jià)作為邊的權(quán)在邊上標(biāo)注。從而，該問題就轉(zhuǎn)化為了從圖G中計(jì)算子圖G'的問題，目標(biāo)子圖G'具有如下特點(diǎn)：6.1圖的基本概念及特性6.1.2用圖來描述實(shí)際問題是一個(gè)連通圖且包含圖G中的所有頂點(diǎn)（從任一城市出發(fā)可以到達(dá)另一城市）；在所有滿足上一條件的子圖中，目標(biāo)子圖G'的權(quán)之和最?。üこ炭傇靸r(jià)最低）。根據(jù)上述兩條特點(diǎn)，可知目標(biāo)子圖G'應(yīng)是一棵樹（刪除任一條邊都會(huì)導(dǎo)致子圖不連通，添加任一條邊都會(huì)使最終的權(quán)之和增加），并且應(yīng)該是具有最小權(quán)之和的最小生成樹。關(guān)于最小生成樹的計(jì)算方法在6.4.1節(jié)中給出。6.1圖的基本概念及特性6.1.2用圖來描述實(shí)際問題【例6-2】一個(gè)人開車從一個(gè)地方去另一個(gè)地方，有多種路線，為了使總里程數(shù)最少，應(yīng)走哪條路線？該問題的圖描述如下：將所有路口作為圖的頂點(diǎn)，路口之間的道路作為連接兩個(gè)頂點(diǎn)的邊，道路長度作為邊的權(quán)?？紤]有些道路是單行路，且往返行駛里程數(shù)可能會(huì)有所不同，因此，對(duì)于該問題應(yīng)使用有向圖表示。如圖6-4（b）所示是該問題的一個(gè)圖描述示例，這里考慮5個(gè)路口，從一個(gè)路口到另一個(gè)路口的行駛里程數(shù)作為邊的權(quán)在邊上標(biāo)注。從而，該問題就轉(zhuǎn)化為了計(jì)算圖中兩個(gè)頂點(diǎn)間最短路徑的問題。關(guān)于最短路徑的計(jì)算方法在6.4.2節(jié)中給出。6.1圖的基本概念及特性6.1.2用圖來描述實(shí)際問題6.2圖的抽象數(shù)據(jù)類型和表示方式圖一般需要進(jìn)行下面的基本操作：創(chuàng)建圖對(duì)圖作深度優(yōu)先遍歷對(duì)圖作廣度優(yōu)先遍歷獲取頂點(diǎn)數(shù)目獲取邊的數(shù)目獲取與指定頂點(diǎn)相關(guān)聯(lián)的第一條邊獲取與指定邊有相同關(guān)聯(lián)頂點(diǎn)的下一條邊添加一個(gè)頂點(diǎn)添加一條邊獲取一個(gè)頂點(diǎn)中存儲(chǔ)的數(shù)據(jù)判斷一條邊是否存在設(shè)置一條邊的權(quán)獲取一條邊的權(quán)6.2圖的抽象數(shù)據(jù)類型和表示方式在計(jì)算機(jī)中存儲(chǔ)圖，主要是要確定頂點(diǎn)的存儲(chǔ)方式及頂點(diǎn)之間關(guān)系（即邊）的存儲(chǔ)方式。與前面學(xué)習(xí)的線性表和樹相比，圖存儲(chǔ)的難點(diǎn)在于頂點(diǎn)之間的關(guān)系更為復(fù)雜（圖中任意兩個(gè)頂點(diǎn)都可以通過連接形成邊）。因此，如何存儲(chǔ)圖中的邊以方便地對(duì)邊進(jìn)行增、刪、改、查等操作是圖存儲(chǔ)要解決的首要問題。根據(jù)邊的存儲(chǔ)方式的不同，圖的存儲(chǔ)結(jié)構(gòu)有多種表示方法，讀者可以根據(jù)實(shí)際應(yīng)用需要選取合適的表示方法。下面主要介紹鄰接矩陣、鄰接壓縮表和鄰接鏈表這三種常用表示方法并給出每種表示方法的具體實(shí)現(xiàn)。6.2圖的抽象數(shù)據(jù)類型和表示方式6.2.1鄰接矩陣6.2.3鄰接鏈表6.2.2鄰接壓縮表6.2圖的抽象數(shù)據(jù)類型和表示方式鄰接矩陣法是用矩陣來表示各頂點(diǎn)之間的連接關(guān)系。對(duì)于有n個(gè)頂點(diǎn)的圖G=(V,E)，其鄰接矩陣A為n*n的方陣，元素A[i][j]（0≤i,j<n）定義為：其中，wij為邊(vi,vj)或<vi,vj>上的權(quán)。例如，圖6-5（a）中所示的有向圖G1和圖6-5（c）中所示的無向圖G2的鄰接矩陣分別如圖6-5（b）和圖6-5（d）所示。6.2.1鄰接矩陣6.2圖的抽象數(shù)據(jù)類型和表示方式6.2.1鄰接矩陣6.2圖的抽象數(shù)據(jù)類型和表示方式鄰接壓縮表可以看作是鄰接矩陣的一種壓縮表示形式。當(dāng)圖中邊的數(shù)目遠(yuǎn)遠(yuǎn)小于結(jié)點(diǎn)數(shù)目的平方時(shí)，鄰接壓縮表占據(jù)的存儲(chǔ)空間會(huì)遠(yuǎn)遠(yuǎn)小于鄰接矩陣占據(jù)的存儲(chǔ)空間；但其缺點(diǎn)是邊的添加、刪除等操作較為復(fù)雜。鄰接壓縮表使用三個(gè)順序表來表示圖中頂點(diǎn)之間的連接關(guān)系和權(quán)，下面給出具體存儲(chǔ)形式。設(shè)圖中共有n個(gè)頂點(diǎn){v0,v1,…,vn-1}，三個(gè)順序表分別為s、w和h。在s中依次記錄與頂點(diǎn)vi（i=0,1,…,n-1）相關(guān)聯(lián)的頂點(diǎn)，如圖6-6（a）所示，可知：對(duì)無向圖G，s中的元素?cái)?shù)目?jī)杀队趫D中邊的數(shù)目，且有（j=0,1,…,ji-1）；對(duì)有向圖G，s中的元素?cái)?shù)目等于圖中邊的數(shù)目，且有（j=0,1,…,ji-1）。在w中依次記錄s中存儲(chǔ)的各條邊的權(quán)，其元素?cái)?shù)目等于s中的元素?cái)?shù)目，如圖6-6（b）所示。在h中依次記錄與頂點(diǎn)vi相關(guān)聯(lián)的頂點(diǎn)在s中的起始存儲(chǔ)位置，如圖6-6（c）所示，h中的元素?cái)?shù)目等于圖中頂點(diǎn)的數(shù)目。6.2.2鄰接壓縮表6.2.2鄰接壓縮表6.2圖的抽象數(shù)據(jù)類型和表示方式6.2.2鄰接壓縮表6.2圖的抽象數(shù)據(jù)類型和表示方式鄰接鏈表可以看作是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接鏈表中，每個(gè)頂點(diǎn)中設(shè)置一個(gè)指向鏈表頭的指針，在鏈表中保存與該頂點(diǎn)相鄰接的頂點(diǎn)信息（包括頂點(diǎn)位置及兩個(gè)頂點(diǎn)形成的邊的權(quán)）。例如，圖6-5（a）中所示的有向圖G1和圖6-5（c）中所示的無向圖G2的鄰接鏈表分別如圖6-8（a）和圖6-8（b）所示。6.2.3鄰接鏈表6.2圖的抽象數(shù)據(jù)類型和表示方式6.3圖的遍歷圖的遍歷，是指從某一頂點(diǎn)出發(fā)按照某種規(guī)則依次訪問圖中的所有頂點(diǎn)，且每個(gè)頂點(diǎn)只被訪問一次。與樹相比，圖中頂點(diǎn)之間的關(guān)系更為復(fù)雜，因此圖的遍歷也要比樹的遍歷更復(fù)雜。根據(jù)搜索路徑的不同，圖的遍歷通常采有兩種方法：廣度優(yōu)先遍歷和深度優(yōu)先遍歷。下面分別介紹這兩種遍歷方法并給出它們的具體實(shí)現(xiàn)。6.3圖的遍歷6.3.1廣度優(yōu)先遍歷及其實(shí)現(xiàn)6.3.2深度優(yōu)先遍歷及其實(shí)現(xiàn)6.3圖的遍歷廣度優(yōu)先遍歷類似于樹的逐層遍歷，即先從某一個(gè)頂點(diǎn)開始訪問，然后訪問與該頂點(diǎn)相鄰接且未被訪問過的頂點(diǎn)集V1(G)，再訪問與V1(G)中頂點(diǎn)相鄰接且未被訪問過的頂點(diǎn)集V2(G)，重復(fù)該過程直至與初始頂點(diǎn)連通的所有頂點(diǎn)都被訪問完。對(duì)于非連通圖或非強(qiáng)連通圖，還要從某一個(gè)未被訪問的頂點(diǎn)開始重復(fù)上一過程，直至所有頂點(diǎn)訪問完畢。例如，對(duì)于圖6-5（a）所示按例6-1創(chuàng)建的有向圖，從頂點(diǎn)v0開始按照廣度優(yōu)先遍歷依次訪問到的頂點(diǎn)為：v0、v1、v2、v4、v3；對(duì)于圖6-5（c）所示按例6-1創(chuàng)建的無向圖，從頂點(diǎn)v0開始按照廣度優(yōu)先遍歷依次訪問到的頂點(diǎn)為：v0、v1、v2、v3、v4。6.3.1廣度優(yōu)先遍歷及其實(shí)現(xiàn)深度優(yōu)先遍歷類似于樹的先序遍歷，即從某一個(gè)頂點(diǎn)開始訪問，訪問后將該頂點(diǎn)去除得到若干子圖，對(duì)每個(gè)子圖再依次進(jìn)行深度優(yōu)先遍歷。例如，對(duì)于圖6-5（a）所示按例6-1創(chuàng)建的有向圖，從頂點(diǎn)v0開始按照深度優(yōu)先遍歷依次訪問到的頂點(diǎn)為：v0、v1、v4、v2、v3；對(duì)于圖6-5（c）所示按例6-1創(chuàng)建的無向圖，從頂點(diǎn)v0開始按照深度優(yōu)先遍歷依次訪問到的頂點(diǎn)為：v0、v1、v4、v2、v3。對(duì)于圖的深度優(yōu)先遍歷，與樹的先序遍歷一樣，有遞歸和非遞歸兩種實(shí)現(xiàn)方式，其中非遞歸方式需要利用棧。6.3.2深度優(yōu)先遍歷及其實(shí)現(xiàn)6.3圖的遍歷6.4應(yīng)用實(shí)例這里給出最小生成樹的求解算法和具體實(shí)現(xiàn)方法。6.4.1最小生成樹6.4.2最短路徑6.4應(yīng)用實(shí)例1.Prim算法

對(duì)于有n個(gè)頂點(diǎn)的圖G=(V,E)，Prim算法從空樹T開始，按照以下規(guī)則將n個(gè)頂點(diǎn)和n-1條邊依次添加到樹中，形成最小生成樹：從某一頂點(diǎn)v0'開始，將該頂點(diǎn)作為樹的根結(jié)點(diǎn)加入到T中，使得T中的數(shù)據(jù)元素集合D={v0'}，數(shù)據(jù)元素關(guān)系集合R={}。對(duì)于一個(gè)頂點(diǎn)在集合D中、另一個(gè)頂點(diǎn)在集合V-D中的那些邊，找出權(quán)最小的一條邊，將該邊在集合V-D中的頂點(diǎn)vi'（i=1,2,…,n-1）加入到集合D中，并將頂點(diǎn)間關(guān)系<vj',vi'>（j<i）加入到關(guān)系集合R中。重復(fù)上一步驟直至集合D中包括圖G中所有n個(gè)頂點(diǎn)（此時(shí)關(guān)系集合R中包括n-1條邊）。若在某一步驟中找不到邊，則說明圖G是一個(gè)非連通圖或非強(qiáng)連通圖，在這種情況下不存在最小生成樹。6.4應(yīng)用實(shí)例6.4.1最小生成樹6.4應(yīng)用實(shí)例6.4.1最小生成樹2.Kruskal算法對(duì)于有n個(gè)頂點(diǎn)的圖G=(V,E)，Kruskal算法根據(jù)圖G中所有n個(gè)頂點(diǎn)生成一個(gè)包括n棵只有根結(jié)點(diǎn)的樹Ti（i=0,1,…,n-1）的森林F，并按照以下規(guī)則森林F中的樹合并，形成最小生成樹：從邊集合E中選取未被訪問過且具有最小權(quán)的邊，置該邊狀態(tài)為已訪問。判斷該邊的兩個(gè)頂點(diǎn)是否屬于不同的樹，若屬于不同的樹則使用該邊將兩棵樹合并為一棵；若屬于同一棵樹則不做任何處理。重復(fù)上一步驟直至森林F中只剩下一棵樹，該樹即是圖G的最小生成樹。若最后森林F中剩下不止一棵樹，則說明圖G是非連通圖或非強(qiáng)連通圖，在這種情況下不存在最小生成樹。6.4應(yīng)用實(shí)例6.4.1最小生成樹6.4應(yīng)用實(shí)例6.4.1最小生成樹1.從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑

圖中兩個(gè)頂點(diǎn)間的最短路徑計(jì)算問題，與從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑計(jì)算問題采用同樣的算法。只是前者在得到兩個(gè)頂點(diǎn)間的最短路徑后，不需再進(jìn)行后繼計(jì)算。Dijkstra提出了一種按路徑長度遞增次序生成最短路徑的算法。對(duì)于有n個(gè)頂點(diǎn)的圖G=(V,E)，若要計(jì)算從頂點(diǎn)v0'到其余各頂點(diǎn)vi'（i=1,2,…,n-1）的最短路徑，則其計(jì)算步驟為：6.4.2最短路徑6.4應(yīng)用實(shí)例令集合S為已計(jì)算出最短路徑的頂點(diǎn)集合（初始時(shí)S={v0'}），w(vj',vi')表示從頂點(diǎn)vj'到頂點(diǎn)vi'的邊的權(quán)（這里為方便計(jì)算，令w(vi',vi')=0），D(v0',vi')表示當(dāng)前計(jì)算得到的從頂點(diǎn)v0'到頂點(diǎn)vi'的最短路徑長度（初始D(v0',vi')=w(v0',vi')）。將頂點(diǎn)加入到集合S中，并將從頂點(diǎn)v0‘到頂點(diǎn)vm’的最短路徑記錄下來。若仍有頂點(diǎn)沒有加到集合S中，則對(duì)集合V-S中的頂點(diǎn)vi‘計(jì)算。重復(fù)上一步驟直至圖中所有頂點(diǎn)都加到集合S中。6.4.2最短路徑6.4應(yīng)用實(shí)例例如，對(duì)于圖6-4（b）中所示的有向圖，若計(jì)算從頂點(diǎn)v0到其余各頂點(diǎn)的最短路徑，則其計(jì)算過程如圖6-11所示。Dijkstra算法的原理可理解為：從某一頂點(diǎn)v0'到另一頂點(diǎn)vi'的最短路徑或者是(v0',vi')、或者是(v0',vi1',vi2',…,vij',vi')，若為后者則其中(v0',vi1',vi2',…,vij',vj')必然為從頂點(diǎn)v0'到頂點(diǎn)vj'的最短路徑。因此，根據(jù)已計(jì)算出的那些頂點(diǎn)的最短路徑，可以依次得到其他頂點(diǎn)的最短路徑。6.4.2最短路徑6.4應(yīng)用實(shí)例6.4.2最短路徑6.4應(yīng)用實(shí)例2.每一對(duì)頂點(diǎn)之間的最短路徑若要計(jì)算圖中每一對(duì)頂點(diǎn)之間的最短路徑，可以重復(fù)使用Dijkstra算法依次計(jì)算