1第7章圖27.1圖的術語與定義圖的定義圖(Graph)——圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點的非空有限集

E(G)是邊的有限集合，邊是頂點的無序對或有序對。圖的分類有向圖無向圖37.1圖的術語與定義圖的定義有向圖——有向圖G是由兩個集合V(G)和E(G)組成的。

其中：V(G)是頂點的非空有限集。

E(G)是有向邊（也稱弧）(的有限集合，弧是頂點的有序對，記為<v,w>，v,w是頂點，v為弧尾，w為弧頭。47.1圖的術語與定義例如：G1=<V1,E1>V1={A,B,C,D,E}E1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,

<D,A>,<E,C>}EACBD57.1圖的術語與定義圖的定義無向圖——無向圖G是由兩個集合V(G)和E(G)組成的。

其中：V(G)是頂點的非空有限集。

E(G)是邊的有限集合，邊是頂點的無序對，記為

(v,w)或

(w,v)，并且(v,w)=(w,v)。67.1圖的術語與定義例如：G2=<V2,E2>

V2={v0,v1,v2,v3,v4}

E2={(v0,v1),(v0,v3),(v1,v2),(v1,v4),

(v2,v3),(v2,v4)}V0V4V3V1V277.1圖的術語與定義例如：G2=<V2,E2>V2={v0，v1，v2，v3}E2={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v0>}例245136G1圖G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}

V0

V1

V2

V387.1圖的術語與定義圖的應用舉例 例1、交通圖（公路、鐵路）

頂點：地點 邊：連接地點的路 例2、電路圖

頂點：元件 邊：連接元件之間的線路 例3、通訊線路圖

頂點：地點 邊：地點間的連線 例4、各種流程圖 如產品的生產流程圖。

頂點：工序 邊：各道工序之間的順序關系97.1圖的術語與定義圖的基本術語1鄰接點及關聯邊 鄰接點：邊的兩個頂點 關聯邊：若邊e=(v,u),則稱頂點v、u關連邊e2頂點的度、入度、出度

頂點V的度

=與V相關聯的邊的數目 在有向圖中：

頂點V的出度

=以V為起點有向邊數

頂點V的入度

=以V為終點有向邊數

頂點V的度

=V的出度+V的入度 設圖G的頂點數為n，邊數為e

圖的所有頂點的度數和=2*e

（每條邊對圖的所有頂點的度數和“貢獻”2度）

V0

V4

V3

V1

V2eV0V1V2V3107.1圖的術語與定義路徑、回路

無向圖G=（V，E）中的頂點序列v1,v2,…,vk，若(vi,vi+1)E(i=1,2,…k-1)，v=v1,u=vk，則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路。 有向圖D=（V，E）中的頂點序列v1,v2,…,vk，若<vi,vi+1>E(i=1,2,…k-1)，v=v1，u=vk，則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路。117.1圖的術語與定義例如 在圖G1中，V0,V1,V2,V3是V0到V3的路徑；V0,V1,V2,V3,V0是回路。 在圖G2中，V0,V2,V3是V0到V3的路徑；V0,V2,V3,V0是回路。無向圖G1有向圖G2

V0

V4

V3

V1

V2V0V1V2V3127.1圖的術語與定義連通圖（強連通圖） 在無（有）向圖G=<V,E>中，若對任何兩個頂點v、u都存在從v到u的路徑，則稱G是連通圖（強連通圖）非連通圖連通圖強連通圖非強連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V4137.1圖的術語與定義子圖 設有兩個圖G=（V，E），G1=（V1，E1），若V1V，E1E，E1關聯的頂點都在V1中，則稱G1是G的子圖；例

(b)、(c)

是(a)

的子圖(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2147.1圖的術語與定義連通分量（強連通分量）

無向圖G的極大連通子圖稱為G的連通分量。 極大連通子圖意思是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點加入，子圖不再連通。連通分量非連通圖

V0

V2

V3

V1

V5

V4157.1圖的術語與定義連通分量（強連通分量）

有向圖D的極大強連通子圖稱為D的強連通分量。 極大強連通子圖意思是：該子圖是D強連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強連通的。強連通分量

V0

V1

V2

V3

V0

V2

V3

V1167.1圖的術語與定義生成樹 包含連通圖G所有頂點的極小連通子圖稱為G生成樹。

極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，若T是G的生成樹當且僅當T滿足如下條件：

T是G的連通子圖

T包含G的所有頂點

T中無回路連通圖G1G1的生成樹

V0

V4

V3

V1

V2

V0

V4

V3

V1

V217

V0

V1

V2

V37.2圖的存儲結構一、數組表示法（鄰接矩陣表示）

鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：A[i][j]=1若(vi,vj)E或<vi,vj>E0否則01010010101011010001100在數組表示法中，用鄰接矩陣表示頂點間的關系

V0

V4

V3

V1

V2011000000001000187.2圖的存儲結構二、鄰接表

鄰接表是圖的鏈式存儲結構 1、無向圖的鄰接表 頂點：通常按編號順序將頂點數據存儲在一維數組中； 關聯同一頂點的邊：用線性鏈表存儲。

V0

V4

V3

V1

V22

01234m-1V0V1V2V3V413422110034該結點表示邊(V2,V4)，其中的4是V4在一維數組中的位置197.2圖的存儲結構結點 typedefstructArcNode {intadjvex;//鄰接點域，//存放與Vi鄰接的點在表頭數組中的位置

structArcNode*next;//鏈域，下一條邊或弧

}

ArcNode;表頭結點 typedefstructtnode {intvexdata;//存放頂點信息

ArcNode*firstarc;//指向第一個鄰接點

}

VNode,AdjList[MAX_VERTEX_NUM];typedefstruct { AdjListvertices; int vexnum,arcnum;//頂點數和弧數 int kind;//圖的種類 }adjvexnextvexdatafirstarc207.2圖的存儲結構無向圖的鄰接表的特點 1）在G鄰接表中，同一條邊對應兩個結點； 2）頂點v的度：等于v對應線性鏈表的長度； 3）判定兩頂點v，u是否鄰接：要看v對應線性鏈表中有無對應的結點。 4）在G中增減邊：要在兩個單鏈表插入、刪除結點； 5）設存儲頂點的一維數組大小為m（m圖的頂點數n），圖的邊數為

e，G占用存儲空間為：m+2*e。G占用存儲空間與G的頂點數、邊數均有關；適用于邊稀疏的圖。217.2圖的存儲結構二、鄰接表 2、有向圖的鄰接表 頂點：用一維數組存儲（按編號順序） 以同一頂點為起點的弧：用線性鏈表存儲1234v0v2v3v1vexdatafirstarc

3

2

4

1^^^^adjvexnext類似于無向圖的鄰接表，所不同的是：以同一頂點為起點的弧：用線性鏈表存儲V0V1V2V3227.2圖的存儲結構二、鄰接表 3、有向圖的逆鄰接表 頂點：用一維數組存儲（按編號順序） 以同一頂點為終點的弧：用線性鏈表存儲。1234v0v2v3v1vexdatafirstarc

4

1

1

3^^^^類似于有向圖的鄰接表，所不同的是：以同一頂點為終點弧：用線性鏈表存儲V0V1V2V3237.2圖的存儲結構三、有向圖的十字鏈表表示法弧結點：typedefstructArcBox{inttailvex,headvex;//弧尾、弧頭在表頭數組中位置

structarcnode*hlink；//指向弧頭相同的下一條弧

structarcnode*tlink;//指向弧尾相同的下一條弧}ArcBox;tailvexheadvexhlinktlink頂點結點：typedefstructVexNode{VertexTypedata;//存與頂點有關信息

ArcBox*firstin；//指向以該頂點為弧頭的第一個弧結點

ArcBox*firstout;//指向以該頂點為弧尾的第一個弧結點}VexNode;VexNodeOLGraph[M];datafirstinfirstout247.2圖的存儲結構三、有向圖的十字鏈表表示法例bdacabcd1234

13

12

34

31

43

42

41^^^^^^^^相同弧尾相同弧頭257.2圖的存儲結構四、無向圖的鄰接多重表表示法頂點結點：typedefstructVexBox{VertexTypedata;//存與頂點有關的信息

EBox*firstedge;//指向第一條依附于該頂點的邊}

VexBox;VexBoxAMLGraph[M];datafirstedge邊結點：typedefstructnode{VisitIfmark;//標志域，記錄是否已經搜索過

intivex,jvex;//該邊依附的兩個頂點在表頭數組中位置

structEBox*ilink,*jlink;//分別指向依附于ivex和jvex的下一條邊}

EBox;markivexilinkjvexjlink267.2圖的存儲結構四、無向圖的鄰接多重表表示法例aecbd1234acdb5e

12

14

34

3235

52^^^^^277.3圖的遍歷圖的深度遍歷（DFS） 從圖的某一頂點V0

出發，訪問此頂點；然后依次從

V0

的未被訪問的鄰接點出發，深度優先遍歷圖，直至圖中所有和

V0

相通的頂點都被訪問到；

若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7287.3圖的遍歷圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例1例1深度遍歷1：V1V2V4V8V5V6V3V7由于沒有規定訪問鄰接點的順序，所以深度優先序列不是唯一的。例1深度遍歷2：V1V3V7V8V6V5V2V4297.3圖的遍歷圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V5307.3圖的遍歷圖的深度遍歷（DFS）——算法7.4和7.5開始訪問V,置標志求V鄰接點有鄰接點w求下一鄰接點W訪問過結束NYNYDFS(G,w)開始標志數組初始化V=0V訪問過?DFS(g,v)V=V+1V<VexNum結束NYYN317.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V4327.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法V1V2V4V5V3V7V6V8例12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍歷：V1V3V7V6V2V4V8V5337.3圖的遍歷圖的廣度遍歷（BFS） 從圖的某一頂點V0出發，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發，廣度優先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8347.3圖的遍歷圖的廣度遍歷（BFS）——遞歸算法開始標志數組初始化V=0V訪問過BFSV=V+1V<Vexnum結束NYYN357.3圖的遍歷圖的廣度遍歷（BFS）——算法7.6開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NY367.3圖的遍歷圖的廣度遍歷（BFS）例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143377.3圖的遍歷圖的廣度遍歷（BFS）例14235012345432fr遍歷序列：1432012345

32fr遍歷序列：1432012345

325fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2387.3圖的遍歷圖的廣度遍歷（BFS）/p>

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2397.4圖的最小生成樹問題提出 要在n個城市間建立通信聯絡網，

頂點——表示城市

權——城市間建立通信線路所需花費代價

希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）最小——最小代價生成樹問題分析 n個城市間，最多可設置

n(n-1)/2

條線路。 n個城市間建立通信網，只需

n-1

條線路。 問題轉化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權值之和）最小。407.4圖的最小生成樹普魯姆算法（Prim） 設G=（V，GE）為一個具有n個頂點的連通網絡，T=（U，TE）為構造的生成樹。 （1）初始時，U={u0}，TE=； （2）在所有uU、vV-U的邊（u,v）中選擇一條權值最小的邊，不妨設為（u,v）； （3）(u,v)加入TE，同時將v加入U； （4）重復(2)(3)，直到U=V為止；UV-UvuU擴大V-U縮小vu417.4圖的最小生成樹普魯姆算法（Prim）——教材P175V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}427.4圖的最小生成樹克魯斯卡爾(Kruskal)算法 設連通網N=(V,{E})。

令最小生成樹初始狀態為只有n個頂點而無邊的非連通圖

T=(V,{})，每個頂點自成一個連通分量。

在E中選取代價最小的邊，若該邊依附的頂點落在

T中不同的連通分量上，則將此邊加入到

T中；否則，舍去此邊，選取下一條代價最小的邊。

依此類推，直至T中所有頂點都在同一連通分量上為止。437.4圖的最小生成樹克魯斯卡爾(Kruskal)算法V3V1V4V6V5V2365216554616543212345447.4圖的最小生成樹克魯斯卡爾(Kruskal)算法V3V1V4V6V5V2365216554616543212345datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222采用邊集數組的形式保存圖：457.4圖的最小生成樹兩種算法比較普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應范圍467.5有向無環圖——拓撲排序問題提出：學生選修課程問題 頂點——表示課程 有向弧——表示先決條件，若課程i

是

課程j

的先決條件，則圖中有弧

<i,j>。

學生應按怎樣的順序學習這些課程，才能無矛盾、順利地完成學業——拓撲排序。定義

AOV網——用頂點表示活動，用弧表示活動間優先關系的有向圖稱為頂點表示活動的網（ActivityOnVertexnetwork），簡稱AOV網。

若

<vi,vj>是圖中有向邊，則

vi

是

vj

的直接前驅；vj

是

vi

的直接后繼。 AOV網中不允許有回路，這意味著某項活動以自己為先決條件。477.5有向無環圖——拓撲排序拓撲排序

把AOV網絡中各頂點按照它們相互之間的優先關系排列成一個線性序列的過程。

檢測AOV網中是否存在環方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都在它的拓撲有序序列中，則該AOV網必定不存在環。拓撲排序的方法

在有向圖中選一個沒有前驅的頂點且輸出之。

從圖中刪除該頂點和所有以它為尾的弧。

重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止。487.5有向無環圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12課程代號課程名稱先修課C1程序設計基礎無C2離散數學C1C3數據結構C1,C2C4匯編語言C1C5語言的設計和分析C3,C4C6計算機原理C11C7編譯原理C3.C5C8操作系統C3,C6C9高等數學無C10線性代數C9C11普通物理C9C12數值分析C1,C9,C10497.5有向無環圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網的拓撲序列不是唯一的507.5有向無環圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1517.5有向無環圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1527.5有向無環圖——拓撲排序拓撲排序C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2537.5有向無環圖——拓撲排序拓撲排序C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2547.5有向無環圖——拓撲排序拓撲排序C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3557.5有向無環圖——拓撲排序拓撲排序C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3567.5有向無環圖——拓撲排序拓撲排序C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4577.5有向無環圖——拓撲排序拓撲排序C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4587.5有向無環圖——拓撲排序拓撲排序C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5597.5有向無環圖——拓撲排序拓撲排序C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5607.5有向無環圖——拓撲排序拓撲排序C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7617.5有向無環圖——拓撲排序拓撲排序C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7627.5有向無環圖——拓撲排序拓撲排序C6C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9637.5有向無環圖——拓撲排序拓撲排序C6C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9647.5有向無環圖——拓撲排序拓撲排序C6C8C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10657.5有向無環圖——拓撲排序拓撲排序C6C8C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8667.5有向無環圖——拓撲排序拓撲排序算法實現 以鄰接表作存儲結構。 把鄰接表中所有入度為0的頂點進棧。 棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼

Vk，把

Vk的入度

減1；若

Vk的入度為

0

則進棧。

重復上述操作直至棧空為止。

若棧空時輸出的頂點個數不是

n，則有向圖有環；否則，拓撲排序完畢。 （實現過程見教材P182）677.5有向無環圖——拓撲排序拓撲排序32104例1234560122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop687.5有向無環圖——拓撲排序拓撲排序0122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416toptopp2697.5有向無環圖——拓撲排序拓撲排序0122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416topp21707.5有向無環圖——拓撲排序拓撲排序0122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416P=NULL21top1717.5有向無環圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416P20top1727.5有向無環圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210446P20top1737.5有向無環圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210446P20top10747.5有向無環圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210443P20top10757.5有向無環圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210443P20top101P=NULL767.5有向無環圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210443P10top1013777.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210443P10top1003787.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210442P10top1003P=NULL797.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321044210top1003P=NULL2807.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104400top1003P24817.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104500top1003P24827.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104500top1003P=NULL24837.5有向無環圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：63210400top1003P=NULL245847.5有向無環圖——關鍵路徑問題提出： 1）工程能否順序進行，即工程流程是否“合理”

2）完成整項工程至少需要多少時間，哪些子工程是影響工程進度的關鍵子工程？V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1頂點表示事件邊表示活動事件Vj發生表示

ak已結束ak

VjVi事件Vi發生表示

ak可以開始

AOE網857.5有向無環圖——關鍵路徑AOE網

AOE——用邊表示活動的網。它是有一個帶權的有向無環圖。 頂點——表示事件，弧——表示活動， 權值——活動持續的時間。

路徑長度——路徑上各活動持續時間之和

關鍵路徑——路徑長度最長的路徑叫關鍵路徑AOV網、AOE網，用都能表示工程各子工程的流程，一個用頂點表示事件，一個用邊表示活動，但AOV網側重表示活動的前后次序，AOE網除表示活動先后次序，還表示了活動的持續時間等，因此可利用AOE網解決工程所需最短時間及哪些子工程拖延會影響整個工程按時完成等問題。867.6最短路徑問題提出： 用帶權的有向圖表示一個交通運輸網，圖中： 頂點——表示城市，邊——表示城市間的交通聯系，權——表示此線路的長度或沿此線路運輸所花的時間或費用等。問題： 從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑。求從某個源點到其余各頂點的最短路徑——迪杰斯特拉(Dijkstra)算法求每一對頂點之間的最短路徑——弗洛伊德(Floyd)算法877.6最短路徑路徑長度最短的最短路徑的特點：在這條路徑上，必定只含一條弧，并且這條弧的權值最小。它只可能有兩種情況：或者是直接從源點到該點（只含一條弧）；或者是從源點經過頂點v1，再到達該頂點（由兩條弧組成）。下一條路徑長度次短的最短路徑的特點：再下一條路徑長度次短的最短路徑的特點：它可能有三種情況：或者是直接從源點到該點（只含一條弧）；或者是從源點經過頂點v1，再到達該頂點（由兩條弧組成）；或者是從源點經過頂點v2，再到達該頂點。其余最短路徑的特點：它或者是直接從源點到該點（只含一條弧）；或者是從源點經過已求得最短路徑的頂點，再到達該頂點。887.6最短路徑求最短路徑步驟初始時令S={V0}，T={其余頂點

}，T中頂點對應的距離值若存在<V0,Vi>，為<V0,Vi>弧上的權值若不存在<V0,Vi>，為從T中選取一個其距離值為最小的頂點W，加入S，對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值；重復上述步驟，直到S中包含所有頂點，即S=V為止。897.6最短路徑求最短路徑步驟13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj516432085623013717329907.6最短路徑求最短路徑步驟13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj516432085623013717329917.6最短路徑求最短路徑步驟13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj516432085623013717329927.6最短路徑求最短路徑步驟13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj516432085623013717329937.6最短路徑求最短路徑步驟13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329947.6最短路徑求最短路徑步驟 圖用帶權鄰接矩陣存儲ad[][]。 數組dist[]存放當前找到的從源點V0到每個終點的最短路徑長度，其初態為圖中直接路徑權值。

數組pre[]表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號。627543185623013717329957.6最短路徑求最短路徑步驟627543185623013717329dist012345601383032pre01234560110101(1)k=1113312220221941215111長度最短路徑13<V1,V2>8<V1,V3>13<V1,V3,V4>19<V1,V3,V4,V5>21<V1,V3,V4,V5,V6>20<V1,V2,V7>算法分析：T(n)=O(n2)967.6最短路徑求每一對頂點之間的最短路徑方法一：每次以一個頂點為源點，重復執行Dijkstra算法n次——

T(n)=O(n3)方法二：弗洛伊德(Floyd)算法算法思想：逐個頂點試探法求最短路徑步驟初始時設置一個n階方陣，令其對角線元素為0，若存在弧<Vi,Vj>，則對應元素為權值；否則為。逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值。所有頂點試探完畢，算法結束。977.6最短路徑例ACB264311041160230初始：路徑：ABACBABCCA0411602370加入V1：路徑：ABACBABCCACABACB264311加入V1點（A）考察：<v2,v3>=2<v2,v1><v1,v3>=17<v3,v2>=<v3,v1><v1,v2>=7987.6最短路徑0411602370加入V1：路徑：ABACBABCCACABACB264311加入V2點（B）考察：<v1,v3>