资源描述：
《图论(二)—最短路径和网路问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、圖論(二)—最短路徑及網路問題最短路徑法(Shortestpathalgorithm)l觀察：如果s,v1,v2,...,vi,..,vk是s到vk的最短路徑，則s,v1,v2,...,vi是s到vi的最短路徑。l有四種狀況：1.所有的權重均為1。求s到其他所有點之最短路徑。2.所有的權重均為非負值(0或大於0)。求s到其他所有點之最短路徑。3.權重可以為負，但迴路之總權重不為負值。求s到其他所有點之最短路徑。4.任意二點之間的最短路徑。l第一種情形(所有的權重均為1。求s到其他所有點之最短路徑。)BFS(BreadthFirstSearch
2、),複雜度：O(
3、E
4、)BeginLableswith0;i¬0;if$anunlabelednodeadjacenttoanodelabeledithenbeginwhile$anunlabelednodeadjacenttoanodelabeledidobeginlabelthisnodei+1;end_of_while;i¬i+1;go_toif_statement;end_of_if;end.第二種情形(所有的權重均為非負值，0或大於0。求s到其他所有點之最短路徑。)Dijstra’salgorithm複雜度：O(
5、V
6、2)notat
7、ion:l(x)¬0,labelxwith0Beginl(s)¬0;l(v)¬w,"v¹s;/*w代表無限大*/T¬V;P¬Æ;u¬s;RepeatforeachvertexvÎTadjacenttoudol(v)¬min{l(v),l(u)+w(u,v)};T¬T–{u};P¬PÈ{u};u¬anewvertexinTwithmin.l(u);Untileither(T=Æ)or(l(u)=w);end.l第三種情形(權重可以為負，但迴路之總權重不為負值。求s到其他所有點之最短路徑。)BellmanandFordalgorithm複雜度：O
8、(
9、V
10、·
11、E
12、)Umj=thelengthofashortestpathfromstojamongallpathsthatcontainatmostmarcs.=Beginm¬0;U0s¬0;U0j¬w,forallj¹s;/*w代表無限大*/repeatm¬m+1;Umj¬Ujm-1,"j,1£j£n;foreacharc(K,j)inGdoUmj=min{Ujm,UKm-1+w(K,j)};until(Umj=Ujm-1)or(m=n)for"jÎG;IF(m=n)and(Umj¹Ujm-1)thenoutput(“existnegat
13、ivecycle!”)end.(例)令Um=[Umj],j=1,2,3,4U0=[0,w,w,w]/*w代表無限大*/U1=[0,w,4,10]U2=[0,13,4,10]/*13=min(13,14)*/U3=[0,13,4,10]l第四種情形(任意二點之間的最短路徑)FloydandWarshallalgorithm複雜度:O(N3)Lettheverticesbenotedby1,2,3...,nUki,j=介於i,j之間的點編號最高為k時之總長度BeginU0ii¬0,"iU0ij¬w(i,j),"(i,j)ÎEU0ij¬w,"(i,
14、j)ÏE/*w代表無限大*/fork=1tondobeginfori=1tondoforj=1tondoUkij¬min{Uijk-1,Uikk-1+Ukjk-1}endendend.(例)3612457456334106432223936網路(network)【定義】網路(network)是一「加權有向圖」(weighteddirectedgraph)，並具有以下之性質：1.網路上有二個特殊的點，分別稱之為「源點」(source)和「終點」(sink)。無任何連線(directedlink/edge)指向源點；亦無任何連線由終點指向其它節點
15、。源點可以提供無限大的流出量，終點可以容納無限大的流入量。2.每一個有向連線均有二個(屬性)權重：「容量」(capacity)與「流量」(flow)。一般而言，容量與流量均是非負數，且容量大於等於流量。3.各節點之總流入量等於總流出量(亦即，各節點無存量)。【說明】1.network，在資訊、運輸、工程界，多譯為「網路」；在社會學界，多譯為「網絡」。2.network是一種特殊的graph。網路流量問題(NetworkFlowProblem)給予一個網路，求取由源點到終點的最大可能流量及路徑。l求解「網路流量問題」，必須用到「最大流量等於最小
16、切割定理」(max-flowmin-cuttheorem)。其演算法稱之為Ford&Fulkersonalgorithm。Max-flowMin-cuttheore
