1、最短路問題,二、最小生成樹問題及其解法,三、最短路問題及其解法,一、圖論的基本概念,圖 論 的 基 本 概 念,一、 圖 的 概 念,1圖的定義,2頂點(diǎn)的次數(shù),3子圖,二、 圖 的 矩 陣 表 示,1 關(guān)聯(lián)矩陣,2 鄰接矩陣,返回,圖的定義,定義,定義,返回,頂點(diǎn)的次數(shù),例2 在一次聚會中，史密斯先生和他太太邀請四對夫妻參加晚會。每個(gè)人到的時(shí)候，房間里的一些人都要與別的一些人握手。當(dāng)然，每個(gè)人都不會與自己的配偶握手，也不會跟同一個(gè)人握手兩次。 之后，史密斯先生問每個(gè)人和別人握了幾次手，他們的答案都不一樣。那么史密斯太太和別人握了幾次手呢？,返回,例1 在一次聚會中，認(rèn)識奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)

2、。,由圖可知， 8號的配偶是0號。 7號的配偶是1號。 6號的配偶是2號。 5號的配偶是3號。 史密斯太太是4號，所以史密斯太太和別人握了4次手。,返回,鄰接矩陣,注：假設(shè)圖為簡單圖,返回,最 短 路 問 題 及 其 算 法,一、 基 本 概 念,二、固 定 起 點(diǎn) 的 最 短 路,三、每 對 頂 點(diǎn) 之 間 的 最 短 路,返回,基 本 概 念,返回,返回,求圖的最小生成樹最常用的兩種算法： （1）Prim算法 （2）Kruskal算法,注意：在一個(gè)加權(quán)連通圖G中，權(quán)最小的那棵生成樹稱為圖G的最小生成樹。,返回,Prim算法思想： 輸入加權(quán)圖的帶權(quán)鄰接矩陣 （1）建立初始候選邊集B， ； （

3、2）從候選邊中選取最短邊（u,v）， ； （3）調(diào)整候選邊集B； （4）重復(fù)（2）、（3）直到T含有n-1條邊。,Prim算法的實(shí)現(xiàn)過程,1 1 1 1 2 3 4 5 8 inf 1 5,4 3 9,4 5 3,5 2 7,2 3 6,實(shí)現(xiàn)Prim算法的MATLAB程序： a=0 8 inf 1 5;8 0 6 inf 7;inf 6 0 9 10;1 inf 9 0 3; 5 7 10 3 0; T= ; e=0; v=1; n=5; sb=2:n; %1代表第一個(gè)紅點(diǎn)，sb代表白點(diǎn)集。 for j=2:n %構(gòu)造初始候選邊的集合 b(1,j-1)=1; b(2,j-1)=j; b(3,j

4、-1)=a(1,j); end,while size(T,2) n-1 min,i=min(b(3,:); %在候選邊中找最短邊。 T(:,size(T,2)+1)=b(:,i); e = e + b(3,i); v = b(2,i); v表示新涂的紅點(diǎn)。 temp = find(sb = b(2,i); sb(temp) = ; b(:,i) = ; for j =1:length(sb) %調(diào)整候選邊 d = a(v,b(2,j); if db(3,j) b(1,j) = v; b(3,j) = d; end end end,Kruskal算法思想： 假設(shè)給定了一個(gè)加權(quán)連通圖G，G的邊集合

5、為E，頂點(diǎn)個(gè)數(shù)n，則假設(shè)最小生成樹T中的邊和頂點(diǎn)均涂為紅色，其余為白色。初始時(shí)G中的邊均為白色。 （1）將所有的頂點(diǎn)涂成紅色； （2）在白色邊中，挑選一條權(quán)最小的邊，使其與紅色邊不形成圈，將該白色邊涂紅。 （3）重復(fù)（2）直到n-1條紅色邊，這n-1條紅色邊就構(gòu)成了最小生成樹T的邊集合。 注意：在用Kruskal算法求最小生成樹時(shí)，在第（2）步判斷是否形成圈在程序?qū)崿F(xiàn)時(shí)比較麻煩。,實(shí)現(xiàn)Kruskal算法的MATLAB程序： %加權(quán)圖的存儲結(jié)構(gòu)采用邊權(quán)矩陣b(i,j)m3 b=1 1 1 2 2 3 3 4 2 4 5 3 5 4 5 5 8 1 5 6 7 9 10 3; B,I=sortro

6、ws(b,3); B=B; m =size(b,2); n=5; t=1:n; k=0; T= ; c = 0;,for i= 1:m if t(B(1,i)=t(B(2,i) %判斷第i條邊是否與樹中的邊形成圈。 k=k+1; T(k,1:2) = B(1:2,i); c=c+B(3,i); tmin = min(t(B(1,i),t(B(2,i); tmax = max(t(B(1,i),t(B(2,i); for j=1:n if t(j) = tmax t(j)= tmin; end end end if k=n-1 break; end end T,c,Kruskal實(shí)現(xiàn)過程： 初始

7、化后排序： B=1 4 1 2 2 1 3 3 4 5 5 3 5 2 4 5 1 3 5 6 7 8 9 10； 第一輪：tmin=1;tmax=4;t=1 2 3 1 5; 第二輪：tmin=4;tmax=5;t=1 2 3 1 1; 第三輪：t(1)=t(5)直接進(jìn)入下一輪 第四輪：tmin=2;tmax=3;t=1 2 2 1 1; 第五輪：tmin=1;tmax=2;t=1 1 1 1 1;,求最短路徑的最常用的兩種算法： （1）Dijkstra算法 （2）Floyd算法,注意：普通路徑長度定義為該路徑所包含的全體邊的長度之和。 最短路徑是指在圖中，從頂點(diǎn)u到頂點(diǎn)v的路徑中普通路徑長

8、度最短的路徑稱為u到v的最短路徑。,固 定 起 點(diǎn) 的 最 短 路,最短路是一條路徑，且最短路的任一段也是最短路,假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹,因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路,算法步驟：,TO MATLAB(road1),1,2,3,4,5,6,7,8,返回,Dijkstra算法的MATLAB實(shí)現(xiàn)： w=0 2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;. 8 6 7 0 5 1 2 inf;inf 1 inf 5 0

9、 3 inf 9;inf inf inf 1 3 0 4 6;. inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0 n=size(w,1); w1=w(1,:); %賦初值 for i=1:n l(i)=w1(i); z(i)=1; end s=; s(1)=1; u=s(1); k=1；,while kl(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u; end end end end l,z,%求v* ll=l; for i=1:n for j=1:k if i=s(j) ll(i)=ll(i); else ll(i)=inf

10、; end end end,lv=inf; for i=1:n if ll(i)lv lv=ll(i); v=i; end end lv, v s(k+1)=v k=k+1 u=s(k) end l,z,每 對 頂 點(diǎn) 之 間 的 最 短 路,1求距離矩陣的方法,2求路徑矩陣的方法,3查找最短路路徑的方法,（一）算法的基本思想,（三）算法步驟,返回,（二）算法原理,算法的基本思想,返回,算法原理 求距離矩陣的方法,返回,算法原理 求路徑矩陣的方法,在建立距離矩陣的同時(shí)可建立路徑矩陣R,即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來查找任何點(diǎn)對之間最短路的路徑

11、,返回,算法原理 查找最短路路徑的方法,pk,p2,p1,p3,q1,q2,qm,則由點(diǎn)i到j(luò)的最短路的路徑為：,返回,算法步驟,TOMATLAB(road2(floyd),返回,Folyd算法的MATLAB實(shí)現(xiàn)： functionD,R=floyd(a) n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end end,for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k, D, R end,在命

12、令窗口中輸入： a=0 9 inf 3 inf;9 0 2 inf 7;inf 2 0 2 4;3 inf 2 0 inf;inf 7 4 inf 0; floyd(a),一、 可化為最短路問題的多階段決策問題,二、 選 址 問 題,1 中心問題,2 重心問題,返回,可化為最短路問題的多階段決策問題,返回,選址問題-中心問題,TO MATLAB(road3(floyd),S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5,S(v3)=6,故應(yīng)將消防站設(shè)在v3處.,返回,選址問題-重心問題,返回,實(shí)驗(yàn)作業(yè),生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率.生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時(shí)回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機(jī)會.可見，生產(chǎn)部門在生產(chǎn)過程中必須時(shí)刻注意市場需求的變化，以便