數(shù)據(jù)結(jié)構(gòu)授課教案-第7章

1、山東輕工業(yè)學(xué)院教師授課教案課程名稱：數(shù)據(jù)結(jié)構(gòu)（計科）課程代碼：學(xué) 分：4.5課程類別：必修開課單位:信息科學(xué)與技術(shù)學(xué)院授課班級：授課教師：楊春花 山東輕工業(yè)學(xué)院教務(wù)處制授課時間年 月 日 星期 第 節(jié)年 月 日 星期 第 節(jié)年 月 日 星期 第 節(jié)授課內(nèi)容概要第七章 圖第一節(jié) 圖的定義和術(shù)語圖的定義；有向圖和無向圖、完全圖、頂點的度、路徑、連通分量、生成樹等基本術(shù)語。第二節(jié) 圖的存儲結(jié)構(gòu) 鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。第三節(jié) 圖的遍歷深度優(yōu)先搜索的定義及實現(xiàn)和廣度優(yōu)先搜索的定義及實現(xiàn)。第四節(jié) 圖的連通性問題無向圖的連通分量和生成樹，最小生成樹的定義以及構(gòu)造最小生成樹的算法（Prim算

2、法和Kruskal算法）。第五節(jié) 有向無環(huán)圖及其應(yīng)用有向無環(huán)圖的定義；拓?fù)渑判?、AOV-網(wǎng)的定義和拓?fù)渑判虻乃惴?；AOE-網(wǎng)的定義、關(guān)鍵路徑的定義和求法。第六節(jié) 最短路徑單源最短路徑問題：Dijkstra算法；各頂點之間的最短路徑問題：Floyd算法。目的要求目的：理解圖的定義和實現(xiàn)?；疽螅豪斫馔?fù)渑判虻母拍詈退惴ǎ斫怅P(guān)鍵路徑問題、最短路徑問題；掌握圖的基本概念、鄰接矩陣和鄰接表存儲結(jié)構(gòu)、深度和廣度優(yōu)先遍歷、最小生成樹的概念、普里姆算法和克魯斯卡爾算法求最小生成樹的方法。重 點圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)；深度和廣度優(yōu)先遍歷方法；最小生成樹。難點圖的深度和廣度優(yōu)先遍歷方法；關(guān)鍵路徑；最短

3、路徑。作業(yè)布置習(xí)題7參考書1. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版), 嚴(yán)蔚敏，清華大學(xué)出版社，2002。3. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語言描述，(美)Sartaj Sahni著，汪詩林等譯，機械工業(yè)出版社，2002。課 型理論課學(xué)時分配復(fù) 習(xí) 分鐘主要教具投影、黑板講 授 分鐘教學(xué)方法講解、提問、示例指 導(dǎo) 分鐘教學(xué)手段板書、課件總 結(jié) 分鐘備注共8學(xué)時注：課型一欄填寫理論課、實驗課、習(xí)題課等授 課 內(nèi) 容備 注第7章 圖7.1圖的定義和術(shù)語7.1.1 圖的定義圖（Graph）是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，其形式化定義如下：Graph=（V，VR）其中V是頂點（Vertex）的非空有限集合，VR是頂點間關(guān)系的集合

4、?；。喝鬡R，則表示從頂點x到頂點y的一條?。╝rc），并稱x為弧尾（tail）或起始點(Initial node)，稱y為弧頭（head）或終端點(Terminal node)。此時的圖稱為有向圖(Digraph)。無向圖：若VR，必有VR，即VR是對稱關(guān)系，這時以無序?qū)Γ▁，y）來代替兩個有序?qū)?，表示x和y之間的一條邊（edge），此時的圖稱為無向圖(Undigraph)。 7.1.2 圖的應(yīng)用舉例例1 交通圖（公路、鐵路） 頂點：地點 邊：連接地點的公路 交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2 電路圖 頂點：元件 邊：連接元件之間的線路例3 通訊線路圖 頂點：地點 邊：

5、地點間的連線例4 各種流程圖 如產(chǎn)品的生產(chǎn)流程圖 頂點：工序 邊：各道工序之間的順序關(guān)系7.1.3 圖的基本術(shù)語設(shè)用n表示圖中頂點的個數(shù)，用 e表示圖中邊或弧的數(shù)目，并且不考慮圖中每個頂點到其自身的邊或弧。無向完全圖：有n（n-1）/2條邊（圖中每個頂點和其余n-1個頂點都有邊相連）的無向圖為完全圖(Completed graph)。有向完全圖：有n（n-1）條邊（圖中每個頂點和其余n-1個頂點都有弧相連）的有向圖為（1）有向完全圖。稀疏圖(Sparse graph)：對于有很少條邊的圖（e n log n）稱為稀疏圖，反之稱為稠密圖(Dense graph)。 權(quán)與網(wǎng):在實際應(yīng)用中，有時圖的

6、邊或弧上往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)(Weight)，這些權(quán)可以表示從一個頂點到另一個頂點的距離或耗費等信息。我們將這種帶權(quán)的圖叫做賦權(quán)圖或網(wǎng)(NetWork)。子圖：設(shè)有兩個圖G=（V，E）和圖G=（V，E）,若VV且E E，則稱圖G為G的子圖(Subgraph)。例 下面 (b)、(c) 是 (a) 的子圖鄰接點及關(guān)聯(lián)邊：對于無向圖 G=（V，E），如果邊（v，v）E，則稱頂點v，v互為鄰接點(Adjacent)，即v，v相鄰接。邊（v，v）依附(Incident)于頂點v和v，或者說邊（v，v）與頂點v和v 相關(guān)聯(lián)。對于有向圖G=（V，A）而言，若弧A，

7、則稱頂點v鄰接到頂點v，頂點v鄰接自頂點v，或者說弧與頂點v，v相關(guān)聯(lián)。度、入度和出度：對于無向圖而言，頂點v 的度(Degree)是指和v相關(guān)聯(lián)的邊的數(shù)目，記作TD（v）。 對于有向圖而言，頂點v的度有出度和入度兩部分：以頂點v為弧頭的弧的數(shù)目稱為該頂點的入度(InDegree)，記作ID（v），以頂點v為弧尾的弧的數(shù)目稱為該頂點的出度(OutDegree)，記作OD（v）則頂點v的度為： TD（v）= ID（v）+ OD（v）。一般地，若圖G中有n個頂點，e條邊或弧，則圖中頂點的度與邊的關(guān)系如下：路徑與回路無向圖G=（V，E）中從頂點v到v/的路徑(Path)是一個頂點序列(V=vi0，v

8、i1，vi2，vim= v/),其中（vij-1，vij）E，1jm。如果圖G是有向圖，則路徑也是有向的，頂點序列應(yīng)滿足E，1jm。 路徑長度：指路徑上經(jīng)過的弧或邊的數(shù)目。 回路或環(huán)：在一個路徑中，若其第一個頂點和最后一個頂點是相同的，即v =v/，則稱該路徑為一個回路或環(huán)。簡單路徑：若表示路徑的頂點序列中的頂點各不相同，則稱這樣的路徑為簡單路徑。簡單回路：除了第一個和最后一個頂點外，其余各頂點均不重復(fù)出現(xiàn)的回路為簡單回路。 連通圖：在無向圖G=（V，E）中，若從vi到vj有路徑相通，則稱頂點vi與vj是連通的。如果對于圖中的任意兩個頂點vi、vjV，vi，vj都是連通的，則稱該無向圖G為連通

9、圖(Connected Graph)。 連通分量：無向圖中的極大連通子圖稱為該無向圖的連通分量(Connected Component)。 強連通圖：在有向圖G=（V，A）中，若對于每對頂點vi、vjV且vivj，從vi到vj和vj到vi都有路徑，則稱該有向圖為強連通圖。強連通分量：有向圖的極大強連通子圖稱作有向圖的強連通分量。生成樹一個連通圖的生成樹是指一個極小連通子圖，它含有圖中的全部頂點，但只有足已構(gòu)成一棵樹的n-1條邊。7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)方法有：鄰接矩陣表示法；鄰接表；鄰接多重表；十字鏈表 1 鄰接矩陣表示法 圖的鄰接矩陣表示法（Adjacency Matrix）也稱作數(shù)

10、組表示法。它采用兩個數(shù)組來表示圖：一個是用于存儲頂點信息的一維數(shù)組，另一個是用于存儲圖中頂點之間關(guān)聯(lián)關(guān)系的二維數(shù)組，這個關(guān)聯(lián)關(guān)系數(shù)組被稱為鄰接矩陣。 鄰接矩陣法的特點：1. 存儲空間：需要n2個存儲空間。2. 便于運算：便于判定圖中任意兩個頂點之間是否有邊相連; 便于求得各個頂點的度。 鄰接表 (Adjacency List)鄰接表是圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)1） 無向圖的鄰接表頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲2） 有向圖的鄰接表和逆鄰接表l 有向圖的鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為起點的?。河镁€性鏈表存儲l 有向圖的逆鄰接表頂點：用一

11、維數(shù)組存儲（按編號順序）以同一頂點為終點的?。河镁€性鏈表存儲鄰接表的特點：存儲空間：對于有n個頂點，e條邊的無向圖而言，若采取鄰接表作為存儲結(jié)構(gòu)，則需要n個表頭結(jié)點和2e個表結(jié)點。 無向圖的度：在無向圖的鄰接表中，頂點vi的度恰好就是第i個邊鏈表上結(jié)點的個數(shù)。 有向圖的出度/入度：在有向圖的鄰接表中，第i個邊鏈表上頂點的個數(shù)是頂點vi的出度。在有向圖的逆鄰接表中，第i個邊鏈表上頂點的個數(shù)是頂點vi的入度。 （有向圖的）十字鏈表(Orthogonal List) （無向圖的）鄰接多重鏈表(Adjacency Multi_list)7.圖的遍歷圖的遍歷(Traversing Graph)從圖中的某

12、個頂點出發(fā)，按某種方法對圖中的所有頂點訪問且僅訪問一次。 7.3.1深度優(yōu)先搜索深度優(yōu)先搜索（Depth_First Search）是指按照深度方向搜索 ，它類似于樹的先根遍歷?；舅枷耄?（1）訪問出發(fā)點v0。 （2）依次以v0的未被訪問的鄰接點為出發(fā)點，深度優(yōu)先搜索圖，直至圖中所有與v0有路徑相通的頂點都被訪問。若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復(fù)上述深度優(yōu)先搜索過程，直至圖中所有頂點均被訪問過為止。 1 圖的深度優(yōu)先搜索的遞歸算法：int visitedMAX_VERTEX_NUM; /*訪問標(biāo)志數(shù)組*/void DFSTraverseGraph (G

13、raph g) /*對圖g進行深度優(yōu)先搜索，Graph 表示圖的一種存儲結(jié)構(gòu)，如數(shù)組表示法或鄰接表等*/for (vi=0;vig.vexnum;vi+) visitedvi=False;/訪問標(biāo)志數(shù)組初始化for( vi=0;vig.vexnum;vi+)/*調(diào)用深度遍歷連通子圖的操作*/*若圖g是連通圖，則此循環(huán)只執(zhí)行一次*/ if (!visitedvi ) DFS (g，vi)；/* TraverseGraph */ void DFS（Graph g, int v0） /*深度遍歷v0所在的連通子圖*/visit（v0）；visitedv0 =True；/*訪問頂點v0，并置訪問標(biāo)志數(shù)

14、組相應(yīng)分量值*/w=FirstAdjVertex(g,v0);while ( w!=-1) /*鄰接點存在*/if(! visited w ) DFS (g,w); w=NextAdjVertex(g,v0,w); /*找下一個鄰接點*/ /*DFS*/ 有了（具體的存儲結(jié)構(gòu)）鄰接表，深度優(yōu)先序列是唯一的3）用非遞歸過程實現(xiàn)深度優(yōu)先搜索void DFS (Graph g, int v0) /*從v0出發(fā)深度優(yōu)先搜索圖g*/ InitStack(S); Push(S, v0)；while ( ! Empty(S) v=Pop(S); if (!visited(v) /*棧中可能有重復(fù)結(jié)點*/ v

15、isit(v); visitedv=True; w=FirstAdj(g, v); /*求v的第一個鄰接點*/while (w!=-1 ) if (!visited(w) Push(S, w);w=NextAdj(g, v, w); 7.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索（Breadth_First Search）是指按照廣度方向搜索，它類似于樹的按層次遍歷?；舅枷耄海?）從圖中某個頂點v0出發(fā)，首先訪問v0。（2）依次訪問v0的各個未被訪問的鄰接點。 （3）分別從這些鄰接點（端結(jié)點）出發(fā)，依次訪問它們的各個未被訪問的鄰接點（新的端結(jié)點）。訪問時應(yīng)保證：如果Vi和Vk為當(dāng)前端結(jié)點，且Vi在Vk之

16、前被訪問，則Vi的所有未被訪問的鄰接點應(yīng)在Vk的所有未被訪問的鄰接點之前訪問。重復(fù)（3），直到所有端結(jié)點均沒有未被訪問的鄰接點為止。 若此時還有頂點未被訪問，則選一個未被訪問的頂點作為起始點，重復(fù)上述過程，直至所有頂點均被訪問過為止。 int visitedMAX_VERTEX_NUM; /*訪問標(biāo)志數(shù)組*/void BFSTraverseGraph (Graph g) /*對圖g進行深度優(yōu)先搜索，Graph 表示圖的一種存儲結(jié)構(gòu)，如數(shù)組表示法或鄰接表等*/for (vi=0;vig.vexnum;vi+) visitedvi=False;/訪問標(biāo)志數(shù)組初始化for( vi=0;vig.vex

17、num;vi+)/*調(diào)用深度遍歷連通子圖的操作*/*若圖g是連通圖，則此循環(huán)只執(zhí)行一次*/ if (!visitedvi ) BreadthFirstSearch (g，vi)；/* TraverseGraph */ void BreadthFirstSearch(Graph g, int v0) /*廣度優(yōu)先搜索圖g中v0所在的連通子圖*/visit(v0); visitedv0=True;InitQueue(Q); /*初始化空隊*/ EnQueue(Q,v0)；/* v0進隊*/while ( ! Empty(Q) DeQueue(&Q, &v); /*隊頭元素出隊*/w=FirstAd

18、j(g,v); /*求v的第一個鄰接點*/while (w!=-1 ) if (!visited(w) visit(w); visitedw=True; EnterQueue(Q, w); w=NextAdj(g, v, w); 7. 圖的連通性問題7.4.1 無向圖的連通分量和生成樹1 無向圖的連通分量在對圖遍歷時，對于連通圖，無論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調(diào)用一次搜索過程，即從任一個頂點出發(fā)，便可以遍歷圖中的各個頂點。對于非連通圖，則需要多次調(diào)用搜索過程，而每次調(diào)用得到的頂點訪問序列恰為各連通分量中的頂點集。調(diào)用搜索過程的次數(shù)就是該圖連通分量的個數(shù)。 例2 無向圖的生成樹生成樹

19、是一個連通圖G 的一個極小的連通子圖。包含圖G 的所有頂點，但只有n-1 條邊，并且是連通的。生成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。7.4. 最小生成樹在一個連通網(wǎng)的所有生成樹中，各邊的代價之和最小的那棵生成樹稱為該連通網(wǎng)的最小代價生成樹（Minimum Cost Spanning Tree），簡稱為最小生成樹。例要在 n 個城市間建立交通網(wǎng)，要考慮的問題如何在保證 n 點連通的前題下最節(jié)省經(jīng)費? 求解: 連通6個城市且代價最小的交通線路? 最小生成樹的重要性質(zhì)如下：設(shè)N=(V,E) 是一連通網(wǎng)，U 是頂點集

20、V的一個非空子集。若（u , v）是一條具有最小權(quán)值的邊，其中uU，vV-U，則存在一棵包含邊（u , v）的最小生成樹。 用反證法來證明這個最小生成樹（MST）的性質(zhì)：假設(shè)不存在這樣一棵包含邊（u , v）的最小生成樹。任取一棵最小生成樹T，將（u , v）加入T中。根據(jù)樹的性質(zhì)，此時T中必形成一個包含（u , v）的回路，且回路中必有一條邊（u , v）的權(quán)值大于或等于（u , v）的權(quán)值。刪除（u , v），則得到一棵代價小于等于T的生成樹T，且T為一棵包含邊（u , v）的最小生成樹。這與假設(shè)矛盾。 1普里姆(prime)算法假設(shè)N=(V,E)是連通網(wǎng)，TE為最小生成樹中邊的集合。（1

21、）初始U=u0(u0V),TE=； （2）在所有uU, vV-U的邊中選一條代價最小的邊（u0，v0）并入集合TE，同時將v0并入U； （3）重復(fù)（2），直到U=V為止。 此時，TE中必含有n-1條邊，則T=（V，TE）為N的最小生成樹。 例：求下圖的最小生成樹。2. 克魯斯卡爾算法假設(shè)N=(V,E)是連通網(wǎng)，將N中的邊按權(quán)值從小到大的順序排列；（1）將n個頂點看成n個集合； （2）按權(quán)值由小到大的順序選擇邊，所選邊應(yīng)滿足兩個頂點不在同一個頂點集合內(nèi)，將該邊放到生成樹邊的集合中。同時將該邊的兩個頂點所在的頂點集合合并；（3）重復(fù)（2），直到所有的頂點都在同一個頂點集合內(nèi)。 7. 有向無環(huán)圖的應(yīng)

22、用有向無環(huán)圖(directed acycline graph)：一個無環(huán)的有向圖，簡稱DAG圖。有向無環(huán)圖是描述一項工程或系統(tǒng)的進行過程的有效工具。如描述工程流程、生產(chǎn)過程中各道工序的流程、程序流程、課程的流程等。7.5.1 拓?fù)渑判? AOV-網(wǎng)：用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向無環(huán)圖，稱為頂點表示活動的網(wǎng)（Activity On Vertex Network），簡稱為AOV-網(wǎng)。 例：某工程可分為7個子工程，若用頂點表示子工程（也稱活動）， 用弧表示子工程間的順序關(guān)系。工程流程可用右圖的AOV網(wǎng)表示表示課程之間優(yōu)先關(guān)系的AOV網(wǎng)2 拓?fù)渑判?Topological Sort)

23、對工程問題，人們至少關(guān)心如下兩類問題：1）工程能否順序進行，即工程流程是否“合理”2）完成整項工程至少需要多少時間，哪些子工程是影響工程進度的關(guān)鍵子工程為求解工程流程是否“合理”，通常用AOV網(wǎng)的有向圖表示工程流程，通過檢測AOV網(wǎng)中是否存在環(huán)來實現(xiàn)。拓?fù)渑判蚴菣z測AOV網(wǎng)中是否存在環(huán)的有效方法。某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判?。AOV網(wǎng)所代表的一項工程中活動的集合顯然是一個偏序集合。為了保證該項工程得以順利完成，必須保證AOV網(wǎng)中不出現(xiàn)回路；否則，意味著某項活動應(yīng)以自身作為能否開展的先決條件，這是荒謬的。 3 拓?fù)渑判蚍椒?）在有向圖選一無前趨的頂點v，輸出

24、；2）從有向圖中刪除v及以v為尾的孤；3）重復(fù)1、2、直接全部輸出全部頂點或有向圖中不存在無前趨頂點。后一情況則說明有向圖中存在環(huán)。拓?fù)渑判蛩惴ǎ核惴ㄋ枷耄海?）選擇一入度為 0 頂點 v，輸出；（2） 將 v 鄰接到的頂點的入度減1；（3）重復(fù)1、2 直到輸出全部頂點或有向圖沒有入度為0的頂點；算法：p1827.5.2 關(guān)鍵路徑1 AOE-網(wǎng)：在有向圖中，用頂點表示事件，用弧表示活動，弧的權(quán)值表示活動所需要的時間。 我們把用這種方法構(gòu)造的有向無環(huán)圖叫做邊表示活動的網(wǎng)（Activity On Edge Network）,簡稱AOE-網(wǎng)。 AOE-網(wǎng)用在工程計劃和管理中，人們最關(guān)心的是：哪些活動

25、是影響工程進度的關(guān)鍵活動？至少需要多長時間能完成整個工程？AOE-網(wǎng)中的基本概念：源點：存在唯一的、入度為零的頂點，叫源點。匯點：存在唯一的、出度為零的頂點，叫匯點。關(guān)鍵路徑：從源點到匯點的最長路徑的長度即為完成整個工程任務(wù)所需的時間，該路徑叫做關(guān)鍵路徑。關(guān)鍵活動：關(guān)鍵路徑上的活動叫做關(guān)鍵活動。 V1 開始事件,V6 結(jié)束事件 事件vj的最早發(fā)生時間vej: 事件vj的最遲發(fā)生時間vli: 指在不推遲整個工期的前提下，事件vj 的最晚發(fā)生時間 活動ak的最早開始時間ek活動ak 的最晚開始時間1i:指在不推遲整個工期的前提下，事件ak j 的最晚發(fā)生時間活動ak 的延遲時間diffk 1事件v

26、j的最早發(fā)生時間vej ve1=0 vej=Maxve(i)+dut() vej=從源點到頂點vj 的最長路徑的長度2事件vj的最遲發(fā)生時間vlivln=venvlj=Minvl(k)-dut()3 活動ak的最早開始時間ek設(shè)ak=, ek=vei4 活動ak 的最晚開始時間1i1k=vlj-dur()5 活動ak 的延遲時間diffk diffk= 1k- ek把活動ai的最晚開始時間1i與最早開始時間ei之差定義為活動ai的延遲時間6 關(guān)鍵活動對于活動ai，若有1i-ei=0 為關(guān)鍵活動，由關(guān)鍵活動組成的路徑就是關(guān)鍵路徑。7.6 最短路徑問題的提出：作為圖的最普通的應(yīng)用，是在交通運輸和通

27、信網(wǎng)絡(luò)中尋找兩個結(jié)點間的最短路徑。比如說，我們可以用圖來表示一個省或一個國家的公路結(jié)構(gòu)，圖的頂點表示城市，邊表示公路段。并且我們對邊加權(quán)，用以表示兩個城市之間的距離，或者表示通過這段公路所需要的時間或所需要支付的花費。這對于一個駕駛員來說，若想從A城駕駛汽車到B城，他就會想得到下列問題的解答： 從A到B有公路嗎？ 若從A到B的路不止一條，那么走哪一條路徑最短或花費最小?7.6.1單源最短路徑問題 問題的提出： 給定一個帶權(quán)有向圖 G與源點v， 求從v到G中其它頂點的最短路徑。 限定各邊上的權(quán)值大于或等于0。 為求得這些最短路徑，Dijkstra 提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法

28、。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。 算法的基本框架：1、設(shè)置并逐步擴充一個集合S，存放已求出的最短路徑的頂點，則尚未確定最短路徑的頂點集合是V-S。引進輔助向量dist ，它的每一個分量disti表示已經(jīng)找到的且從開始點v0到每一個終點vi的當(dāng)前最短路徑的長度（該路徑只經(jīng)過S中頂點最后到達(dá)vi ）。它的初態(tài)為：如果從v0到vi有弧，則disti為弧的權(quán)值；否則disti為。2、取distj=Mindisti | viV 則distj是從v0到vj 的最短路徑長度。 將vj加入S集合3、修改從v0出發(fā)到

29、集合VS上任一頂點vi的最短路徑的長度。即如果 distk+ arcskidisti則將disti修改為：distk+ arcski4、重復(fù)(2)、(3) n-1次，即可按最短路徑長度的遞增順序，逐個求出v0到圖中其它每個頂點的最短路徑。為了同時得到路徑，另設(shè)置一個路徑向量pathn，其中pi存放從v0vi的最短路徑上的前驅(qū)結(jié)點。例：求下圖從V0到其余各頂點的最短路徑。float Dn;intPn,Sn;DIJKSTRA(float Cn,int v)int i,j,k,v1,pre;int min,max=60,inf=80;v1=v-1;for (i=0;in;i+) Di=Cv1i;if

30、 (Di!=max) Pi=v;else Pi=0;n n for (i=0;in;i+) Si=0;n Sv1=1; Dv1=0;n for (i=0;in-1;i+)n min=inf;q for (j=0;jn;j+)q if (!Sj)&(Djmin)q min=Dj; k=j; Sk=1;for (j=0;jDk+Ckj) Dj=Dk+Ckj;Pj=k+1;for (i=0;in;i+) printf(“%fn%d”,Di,i+1);pre=pi;while (pre!=0) printf(“-%d”,pre);pre=Ppre-1;7.6.2 任意一對頂點間的最短路徑佛羅依德(Floyd)算法的基本思想設(shè)圖g用鄰接矩陣法表示，求圖g中任意一對頂點vi、vj間的的最短路徑。 （-1）將vi到vj 的最短的路徑長度初始化為g.arcsij，然后進行如下n次比較和修正： （0）在vi、vj間加入頂點v0，比較（vi,v0,vj）和(vi,vj)的路徑的長度，取其中較短的路徑作為vi到vj 的且中間頂點號不大于0的最短路徑。 （1）在