數(shù)學(xué)建模圖論

1、圖論一最短路問(wèn)題問(wèn)題描述：尋找最短路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點(diǎn)間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時(shí)間、費(fèi)用、線路容量等。將問(wèn)題抽象為賦權(quán)有向圖或無(wú)向圖，邊上的權(quán)均非負(fù)對(duì)每個(gè)頂點(diǎn)定義兩個(gè)標(biāo)記（，），其中：表示從頂點(diǎn)到的一條路的權(quán)：的父親點(diǎn)，用以確定最短路的路線：具有永久標(biāo)號(hào)的頂點(diǎn)集1.1Dijkstra算法：即在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終為最短路的權(quán)輸入：的帶權(quán)鄰接矩陣步驟：（1） 賦初值：令，對(duì)，令， 。（2） 對(duì)每個(gè) （即不屬于上面集合的點(diǎn)），用 代替，這里表示頂點(diǎn)和之間邊的權(quán)值。計(jì)算，把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，令。（3） 若，則停

2、止；若，則用代替，轉(zhuǎn)（2）算法結(jié)束時(shí)，從到各頂點(diǎn)的距離由的最后一次編號(hào)給出。在進(jìn)入之前的編號(hào)叫標(biāo)號(hào)，進(jìn)入之后的編號(hào)叫標(biāo)號(hào)。算法就是不斷修改各頂點(diǎn)的標(biāo)號(hào)，直至獲得標(biāo)號(hào)。若在算法運(yùn)行過(guò)程中，將每一頂點(diǎn)獲得標(biāo)號(hào)所由來(lái)的邊在圖上標(biāo)明，則算法結(jié)束時(shí)，至各頂點(diǎn)的最短路也在圖上標(biāo)示出來(lái)了。理解：貪心算法。選定初始點(diǎn)放在一個(gè)集合里，此時(shí)權(quán)值為0初始點(diǎn)搜索下一個(gè)相連接點(diǎn)，將所有相連接的點(diǎn)中離初始點(diǎn)最近的點(diǎn)納入初始點(diǎn)所在的集合，并更新權(quán)值。然后以新納入的點(diǎn)為起點(diǎn)繼續(xù)搜索，直到所有的點(diǎn)遍歷。Matlab代碼：Dijk.mfunctionmydistance,mypath=Dijk(a,sb,db);%sb為起點(diǎn)，d

3、b為終點(diǎn)n=size(a,1);visited(1:n)=0;%n為結(jié)點(diǎn)數(shù) visited為結(jié)點(diǎn)標(biāo)號(hào)distance(1:n)=inf;distance(sb)=0;%起點(diǎn)到各終點(diǎn)距離的初始化visited(sb)=1;u=sb;%u為新的P標(biāo)號(hào)頂點(diǎn)（初始點(diǎn)）parent(1:n)=0;%父節(jié)點(diǎn)的初始化%經(jīng)過(guò)以下一個(gè)for.end便可以找到最短路徑及該最短路徑對(duì)應(yīng)的最短路程for i=1:n-1%(找所有未標(biāo)號(hào)的點(diǎn)) id=find(visited=0);%查找未標(biāo)號(hào)的頂點(diǎn) for v=id %找到一個(gè)未標(biāo)號(hào)的點(diǎn)v if a(u,v)+distance(u)<distance(v)%uv

4、之間的距離+起點(diǎn)到u的距離小于 v到起點(diǎn)的距離（第一次是無(wú)窮大的，所以第一次肯定滿足，下一次則找比這個(gè)點(diǎn)到u距離小的v） distance(v)=distance(u)+a(u,v);%修改標(biāo)號(hào)值 則v到原點(diǎn)的距離（權(quán)）修改。 parent(v)=u; %u是v的父節(jié)點(diǎn) end end temp=distance;%以上面的distance作為臨時(shí)的最小距離，如果下一次循環(huán)的未標(biāo)號(hào)頂點(diǎn)有更小的距離則替換 temp(visited=1)=inf;%已標(biāo)號(hào)的點(diǎn)距離換為無(wú)窮，避免再次搜索 t,u=min(temp);%找出距離最小的點(diǎn) （t是最小值，u是最小值的下標(biāo)） 最后一次循環(huán)會(huì)得到一個(gè)最小距離

5、的點(diǎn) visited(u)=1;%標(biāo)記已經(jīng)標(biāo)號(hào)的頂點(diǎn)end%下面一段代碼用于輸出pathmypath=;%定義mypath為一個(gè)空矩陣if parent(db)=0%如果存在路 =為不等于即前面有parent點(diǎn) t=db;%終點(diǎn)標(biāo)號(hào)賦給t mypath=db%將終點(diǎn)放入路徑集合里 while t=sb%當(dāng)終點(diǎn)不是初始點(diǎn) P = parent(t);%終點(diǎn)的父節(jié)點(diǎn)令為P mypath=P mypath; t=P;%把上一個(gè)點(diǎn)的父節(jié)點(diǎn)令為下一輪循環(huán)的節(jié)點(diǎn)，繼續(xù)搜索父節(jié)點(diǎn) endendmydistance=distance(db);%最短路程main.mn=29; a=zeros(n);a(1,2)

6、=2;a(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;a(2,3)=2;a(3,4)=2;a(4,5)=2;a(5,6)=2;a(6,7)=2;a(6,22)=35;a(7,8)=2;a(8,9)=2;a(9,10)=2;a(11,12)=2;a(12,13)=2;a(13,14)=2;a(13,20)=108;a(14,15)=2;a(15,16)=2; a(16,29)=41;a(17,18)=2;a(18,19)=2;a(18,23)=309; a(18,21)=134;a(19,20)=2;a(20,24)=145;a(20,27)=281;

7、a(20,26)=206;a(21,24)=24;a(22,25)=60;a(22,28)=142;a(23,27)=126;a(24,26)=145;a(26,29)=77;a(28,29)=115;a=a+a' a(a=0)=inf; %把所有零元素替換成無(wú)窮a(1:n+1:n2)=0; %對(duì)角線元素替換成零，Matlab中數(shù)據(jù)是逐列存儲(chǔ)的for i=1:10mydistance,mypath = Dijk( a,21,i );%從公交南北到A1-A10的最短路徑mypathend二floyed算法：2.1基本思想：直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出個(gè)矩陣、 、，使

8、最后得到的矩陣成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑。2.2基本原理2.2.1求距離矩陣把帶權(quán)鄰接矩作為距離矩陣的初值，即(1)，其中 是從到的只允許作為中間點(diǎn)的路徑中最短路的長(zhǎng)度(2)，其中 是從到的只允許、作為中間點(diǎn)的路徑中最短路的長(zhǎng)度%解釋：為從；為從 ()，其中是從到的只允許、作為中間點(diǎn)的路徑中最短路的長(zhǎng)度，即是從到中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)，因此即是距離矩陣。2.2.2求路徑矩陣在建立距離矩陣的同時(shí)可建立路徑矩陣，的含義是從到的最短路要經(jīng)過(guò)點(diǎn)號(hào)為的點(diǎn)， %初值每求得一個(gè)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 即當(dāng)被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在中，依次求

9、時(shí)求得，可由來(lái)查找任何點(diǎn)對(duì)之間最短的路徑2.2.3查找最短路徑若，則點(diǎn)是點(diǎn)到點(diǎn)的最短路的中間點(diǎn)。然后用同樣的方法再分頭查找。若：(1)向點(diǎn)追溯得：(2)向點(diǎn)追溯得： 步驟：到的距離：到之間的插入點(diǎn)輸入：帶權(quán)鄰接矩陣 (1) 賦初值：對(duì)所有 (2) 更新對(duì)所有，若，則 (3) 若，停止。否則，轉(zhuǎn)(2)Matlab代碼：floyed.m%輸出最短距離矩陣和最短路徑矩陣function d,r=floyd(w)n=length(w);for i=1:n for j=1:n d(i,j)=w(i,j); r(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if

10、d(i,k)+d(k,j)<d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=k; end end endendmyfloyed.m%輸入起點(diǎn)終點(diǎn)得到最短路徑和最短距離%可用循環(huán)求多個(gè)距離function dist,mypath=myfloyd(a,sb,db);%a為鄰接矩陣；a(i,j)為頂點(diǎn)i到j(luò)的直達(dá)距離，可以是有向的%sb起點(diǎn)，db終點(diǎn)% dist最短路距離 mypath最短路徑n = size(a,1);path=zeros(n);%初始化for k=1:n %遍歷每個(gè)點(diǎn) for i=1:n for j=1:n %遍歷每?jī)牲c(diǎn)之間的距離 if a(i,j)

11、>a(i,k)+a(k,j) %如果i,j距離大于從i到k加上從k到j(luò)的距離 a(i,j)=a(i,k)+a(k,j) %則i,j距離被更新 path(i,j)=k; %k點(diǎn)加入最短路徑 end end endenddist = a(sb,db);%打印pathparent = path(sb,:); %起點(diǎn)到終點(diǎn)最短路上各頂點(diǎn)的父親點(diǎn)parent(parent=0)=sb; %如果父親點(diǎn)為0則表示該頂點(diǎn)為起點(diǎn)mypath=db;t=db; %終點(diǎn)放入路徑中while t=sb %但某點(diǎn)的父親點(diǎn)不是不是初始點(diǎn)時(shí)，繼續(xù)循環(huán) p = parent(t); %把該點(diǎn)的父親點(diǎn)賦給p mypath

12、 = p,mypath; %把p加入path中 t = p; %把p作為新的點(diǎn)繼續(xù)循環(huán)找父親點(diǎn)的父親點(diǎn)end可測(cè)試數(shù)據(jù)：n=29; a=zeros(n);a(1,2)=2;a(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;a(2,3)=2;a(3,4)=2;a(4,5)=2;a(5,6)=2;a(6,7)=2;a(6,22)=35;a(7,8)=2;a(8,9)=2;a(9,10)=2;a(11,12)=2;a(12,13)=2;a(13,14)=2;a(13,20)=108;a(14,15)=2;a(15,16)=2; a(16,29)=41;a(1

13、7,18)=2;a(18,19)=2;a(18,23)=309; a(18,21)=134;a(19,20)=2;a(20,24)=145;a(20,27)=281;a(20,26)=206;a(21,24)=24;a(22,25)=60;a(22,28)=142;a(23,27)=126;a(24,26)=145;a(26,29)=77;a(28,29)=115;a=a+a' a(a=0)=inf; %把所有零元素替換成無(wú)窮a(1:n+1:n2)=0; %對(duì)角線元素替換成零，Matlab中數(shù)據(jù)是逐列存儲(chǔ)的% for i=1:10d,r=floyd(a)%從公交南北到A1-A10的最短

14、路徑% end 二最小生成樹在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。1.Prim算法（貪心算法）圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)（英語(yǔ)：Vertex (graph theory)），且其所有邊的權(quán)值之和亦為最小。構(gòu)造連通賦權(quán)圖的最小生成樹(是鄰接矩陣)，設(shè)置兩個(gè)集合和，其中用于存放的最小生成樹中的頂點(diǎn)，集合存放的最小生成樹中的邊。令集合的初值為(即初始(出發(fā))點(diǎn)為)，集合的初值為(空集)。算法思想：從的邊中，選取具有最小權(quán)值的邊，將頂點(diǎn)加入集合中，將邊加入集合中，如此不斷重復(fù)

15、，直到時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合中包含了最小生成樹的所有邊。算法過(guò)程： ，。while 找最小邊，其中； end代碼：clcclear all;%初始化鄰接矩陣a = zeros(7);a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a+a'a(a=0)=inf;%算法主體result = ; %定義一個(gè)空集放結(jié)果p=1;tb=2:length(a); %p為起點(diǎn) tb為下一個(gè)點(diǎn)while size(result,2)=len

16、gth(a)-1 %size(result,2)取矩陣result的第二列 temp = a(p,tb); %所有以1為起點(diǎn)的權(quán)值 temp = temp(:); %temp=temp(:)把所有的元素都拿出來(lái)，從左到右一列一列的拿，變?yōu)橐涣小?d = min(temp); %最小權(quán)值 jb,kb = find(a(p,tb)=d,1); %找出起點(diǎn)集到終點(diǎn)集的最小權(quán)值的下一個(gè)點(diǎn)（第一個(gè)）所在位置：行jb和列kb j = p(jb);k = tb(kb); result = result,j;k;d; p = p,k; tb(find(tb=k)=;endKruskal算法：從邊出發(fā)，從所有的

17、邊當(dāng)中選一條最小的邊（如果最小的邊不止一條，則任選一條即可）然后判斷這條邊的兩個(gè)端點(diǎn)是否在同一棵樹中（并查集判斷），如果已經(jīng)在同一棵樹中，則舍去這條邊，因?yàn)樵谶@之前已經(jīng)有一條比這條還短的邊連接這兩個(gè)節(jié)點(diǎn)了，如果不在，則把這兩個(gè)節(jié)點(diǎn)連到一棵樹中，并且記錄下這條邊，以此類推，直到邊數(shù)達(dá)到，此時(shí)個(gè)點(diǎn)已經(jīng)在同一棵樹中了，算法結(jié)束。輸入： 圖G  輸出： 圖G的最小生成樹  具體流程：  (1)選，使得是權(quán)值最小的邊(2)若已選好，則從中選取，使得中無(wú)圈；是中權(quán)值最小的邊。(3)直到選得為止代碼：clcclear all;%

18、初始化鄰接矩陣a(1,2,3) = 50,60;a(2,4,5) = 65,40;a(3,4,7) = 52,45;a(4,5,6) = 50,30; %鄰接矩陣另一種輸入方式a(4,7) = 42;a(5,7) = 70;i,j,b= find(a); %a中非零值data = i'j'b' %存放所有非零值位置及值index = data(1:2,:); %存放非零的兩點(diǎn)loop = length(a)-1;result = ;%算法主體while length(result)<loop temp = min(data(3,:); %權(quán)值最小 flag = f

19、ind(data(3,:)=temp); flag = flag(1); v1 = index(1,flag); %權(quán)值最小兩點(diǎn)的第一個(gè)點(diǎn) v2 = index(2,flag); %權(quán)值最小兩點(diǎn)的第二個(gè)點(diǎn) if v1=v2 %如果兩點(diǎn)不是同一個(gè)點(diǎn) result = result,data(:,flag); %加入結(jié)果集中 end index(find(index = v2) = v1; %讓兩個(gè)端點(diǎn)相同，則后面搜索時(shí)不再被選 data(:,flag) = ; index(:,flag) = ;endresult三網(wǎng)絡(luò)最大流在一定條件下，求解給定系統(tǒng)的最大流量。應(yīng)用背景：鐵路運(yùn)輸系統(tǒng)中的車輛流，

20、城市給排水系統(tǒng)的水流問(wèn)題，控制系統(tǒng)中的信息流問(wèn)題，常見的人流，物流，水流，氣流，電流，現(xiàn)金流等。為解決該問(wèn)題，首先引入一些必要的概念：1.網(wǎng)絡(luò)與流給一個(gè)有向圖，其中為弧集，在中指定了一點(diǎn)，稱為發(fā)點(diǎn)（記為），另一點(diǎn)稱為收點(diǎn)（記為），其余的點(diǎn)叫中間點(diǎn)，對(duì)于每一條弧，對(duì)應(yīng)有一個(gè)（或簡(jiǎn)寫為），稱為弧的容量。通常把這樣的有向圖叫做一個(gè)網(wǎng)絡(luò)，記為，其中。所謂網(wǎng)絡(luò)上的流，是指定義在弧集合，并稱為弧上的流量。2.可行流與最大流滿足下列條件的流稱為可行流：（1） 容量限制條件：對(duì)每一弧。（2） 平衡條件：對(duì)于中間點(diǎn)，流出量=流入量，即對(duì)于每個(gè)，有 ，對(duì)于發(fā)點(diǎn)，記 ，對(duì)于收點(diǎn) ，記，式中：為這個(gè)可行流的流量，即發(fā)

21、點(diǎn)的凈輸出量。可行流總是存在的，如零流。最大流問(wèn)題可以寫為如下的線性規(guī)劃模型： 3.增廣路給定一個(gè)可行流，把網(wǎng)絡(luò)中使的弧稱為飽和弧，使的弧稱為非飽和弧。把稱為零流弧，的弧稱為費(fèi)零流弧。若是網(wǎng)絡(luò)中聯(lián)接發(fā)點(diǎn)和收點(diǎn)的一條路，定義路的方向是從到，則路上的弧被分為兩類：一類是弧的方向與路的方向一致，稱為前向弧，前向弧的全體即為；另一類弧與路的方向相反稱為后向弧，后向弧的全體稱為。定義：設(shè)是一個(gè)可行流， 是從到的一條路，若滿足：前向弧是非飽和弧，后向弧是非零流弧，則稱為（關(guān)于可行流）一條增廣路。Ford-Fulkerson算法流程：其中，每個(gè)頂點(diǎn)的標(biāo)號(hào)值有兩個(gè)，第一個(gè)標(biāo)號(hào)值表示在可能的增廣路上，的前驅(qū)頂點(diǎn)

22、；的第二個(gè)編號(hào)值記為，標(biāo)志在可能的增廣路上可以調(diào)整的流量。初始化給發(fā)點(diǎn)標(biāo)號(hào)，對(duì)已標(biāo)號(hào)頂點(diǎn)的鄰接頂點(diǎn)按以下規(guī)則標(biāo)號(hào)：若，且時(shí)，令，則給頂點(diǎn)標(biāo)號(hào)為，若，則不給頂點(diǎn)標(biāo)號(hào)。，且，令，則給標(biāo)號(hào)為，這里第一個(gè)標(biāo)號(hào)值，表示在可能的增廣路上，為反向?。蝗?，則不給標(biāo)號(hào)。增流過(guò)程： 令。 若的標(biāo)號(hào)為，則；若的標(biāo)號(hào)為，則。Ford_Fulkerson.m%n表示節(jié)點(diǎn)數(shù)，C表示容量矩陣function f,wf,No=Ford_Fulkerson(n,C)for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f為零流for(i=1:n)No(i)=0;d(i)=0;end %No,d

23、 記錄標(biāo)號(hào)while(1) No(1)=n+1; d(1)=Inf; %給發(fā)點(diǎn)vs 標(biāo)號(hào) while(1)pd=1; %標(biāo)號(hào)過(guò)程 for(i=1:n)if(No(i) %選擇一個(gè)已標(biāo)號(hào)的點(diǎn)vi for(j=1:n)if(No(j)=0&f(i,j)<C(i,j) %對(duì)于未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng) vivj 為非飽和弧時(shí) No(j)=i;d(j)=C(i,j)-f(i,j);pd=0; if(d(j)>d(i)d(j)=d(i);end elseif(No(j)=0&f(j,i)>0) %對(duì)于未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng) vjvi 為非零流弧時(shí) No(j)=-i;d(j)

24、=f(j,i);pd=0; if(d(j)>d(i)d(j)=d(i);end;end;end;end;end if(No(n)|pd)break;end;end %若收點(diǎn)vt得到標(biāo)號(hào)或者無(wú)法標(biāo)號(hào), 終止標(biāo)號(hào)過(guò)程 if(pd)break;end %vt 未得到標(biāo)號(hào), f 已是最大流, 算法終止 dvt=d(n);t=n; %進(jìn)入調(diào)整過(guò)程, dvt 表示調(diào)整量 while(1) if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧調(diào)整 elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧調(diào)整 if(N

25、o(t)=1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %當(dāng)t的標(biāo)號(hào)為vs 時(shí), 終止調(diào)整過(guò)程 t=No(t); end;end; %繼續(xù)調(diào)整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end %計(jì)算最大流量f %顯示最大流wf %顯示最大流量No %顯示標(biāo)號(hào), 由此可得最小割, 程序結(jié)束輸入：C = ;n = ；四最小費(fèi)用最大流最小費(fèi)用最大流問(wèn)題是經(jīng)濟(jì)學(xué)和管理學(xué)的一類典型的基本問(wèn)題。在一個(gè)網(wǎng)絡(luò)中每條路徑都存在“容量”和“費(fèi)用”兩個(gè)限制條件，此類問(wèn)題是想尋找出：車輛從地到地，選擇合適的路徑及考慮分配路徑的流量，使其能夠在流量最大

26、的前提下，達(dá)到所用的費(fèi)用最小的要求。假設(shè)輛卡車要從地到地運(yùn)送物品，由于每條路段都存在不同的收費(fèi)情況，每條路能容納的車的數(shù)量也有一定限制，最小費(fèi)用最大流問(wèn)題指如何分配卡車的出發(fā)路徑可以使費(fèi)用降到最低，物品又能準(zhǔn)確全部的送達(dá)。物流成本最小問(wèn)題稱為最小費(fèi)用流問(wèn)題，在現(xiàn)實(shí)生活中有很多的應(yīng)用，一般把其歸為一類網(wǎng)絡(luò)優(yōu)化問(wèn)題?？梢园讶萘孔鳛榱?，費(fèi)用作為時(shí)間代價(jià)，來(lái)研究交通運(yùn)輸問(wèn)題。最小費(fèi)用最大流算法包含很多經(jīng)典的算法和流程，本文主要采用最大流算法和最小費(fèi)用最大流對(duì)偶算法。1. 模型的建立給定網(wǎng)絡(luò)，每一條弧上屬于，除了已給容量外，還給了一個(gè)單位流量的費(fèi)用（簡(jiǎn)記為）。所謂最小費(fèi)用最大流問(wèn)題就是要求一個(gè)最大流是的

27、一個(gè)可行流，為到（關(guān)于流），使得流的總輸送費(fèi)用取最小值。2對(duì)偶法求解最小費(fèi)用最大流問(wèn)題定義：已知網(wǎng)絡(luò)，是的一個(gè)可行流，為到 （關(guān)于流）的可增廣路徑，稱為路徑的費(fèi)用。若是從到所有可增廣路徑中費(fèi)用最小的路徑，則稱為最小費(fèi)用可增廣路徑。定理：若是流量為的最小費(fèi)用流，是關(guān)于的從到的一條最小費(fèi)用可增廣路徑，則經(jīng)過(guò)調(diào)整流量得到新的可行流（記為），一定是流量為的可行流中的最小費(fèi)用流。3.對(duì)偶法的基本思路 取 尋找從到的一條最小費(fèi)用可增廣路徑。若不存在，則為中的最小費(fèi)用最大流，算法結(jié)束。若存在，則用求最大流的方法將調(diào)整成，使，并將賦值給，轉(zhuǎn)n=6;C=0 8 0 7 0 00 0 9 5 0 0 0 0 0

28、2 0 50 0 0 0 9 00 0 6 0 0 100 0 0 0 0 0 ; %弧容量b = 0 2 0 8 0 00 0 2 5 0 0 0 0 0 1 0 60 0 0 0 3 00 0 4 0 0 70 0 0 0 0 0 ; %弧容量wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示預(yù)定的流量值for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 為零流while(1)for(i=1:n)for(j=1:n)if(j=i)a(i,j)=Inf;end;end;end%構(gòu)造有向賦權(quán)圖for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)=0)a(i,j)=b(i,j);elseif(C(i,j)>0&f(i,j)=C(i,j)a(j,i)=-b(i,j);elseif(C(i,