圖論論文--最短路徑算法應(yīng)用

1、課程論文課程名稱圖論及其應(yīng)用題目最短路徑算法應(yīng)用最短路徑游覽校園姓名學(xué)號(hào)專業(yè)計(jì)算機(jī)技術(shù)A[ij]←A[ij]∨A[kj]（4）k增1（5）如果k≤n，則轉(zhuǎn)到步驟（3），否則停止。所得的矩陣A即為關(guān)系R的傳遞閉包t(R)的關(guān)系矩陣。設(shè)關(guān)系R的關(guān)系圖為G，設(shè)圖G的所有頂點(diǎn)為v1v2…vn，則t(R)的關(guān)系圖可用該方法得到：若G中任意兩頂點(diǎn)vi和vj之間有一條路徑且沒有vi到vj的弧，則在圖G中增加一條從vi到vj的弧，將這樣改造后的圖記為G

2、’，則G’即為t(R)的關(guān)系圖。G’的鄰接矩陣A應(yīng)滿足：若圖G中存在從vi到vj路徑，即vi與vj連通，則A[ij]=1，否則A[ij]=0。這樣，求t(R)的問題就變?yōu)榍髨DG中每一對(duì)頂點(diǎn)間是否連通的問題。定義一個(gè)n階方陣序列A(0)A(1)A(2)…A(n)，每個(gè)方陣中的元素值只能取0或1。A(m)[ij]=1表示存在從vi到vj且中間頂點(diǎn)序號(hào)不大于m的路徑（m=1..n），A(m)[ij]=0表示不存在這樣的路徑。而A(0)[ij]

3、=1表示存在從vi到vj的弧，A(0)[ij]=0表示不存在從vi到vj的弧。這樣，A(n)[ij]=1表示vi與vj連通，A(n)[ij]=0表示vi與vj不連通。故A(n)即為t(R)的關(guān)系矩陣。那么應(yīng)如何計(jì)算方陣序列A(0)A(1)A(2)…A(n)呢？很顯然，A(0)=M（M為R的關(guān)系矩陣）。若A(0)[i1]=1且A(0)[1j]=1，或A(0)[ij]=1，當(dāng)且僅當(dāng)存在從vi到vj且中間頂點(diǎn)序號(hào)不大于1的路徑，此時(shí)應(yīng)將A(1

4、)[ij]置為1，否則置為0。一般地，若A(k1)[ik]=1且A(k1)[kj]=1，或A(k1)[ij]=1，當(dāng)且僅當(dāng)存在從vi到vj且中間頂點(diǎn)序號(hào)不大于k的路徑，此時(shí)應(yīng)將A(k)[ij]置為1，否則置為0（k=1..n）。用公式表示即為：A(k)[ij]=(A(k1)[ik]∧A(k1)[kj])∨A(k1)[ij]ijk=1..n這樣，就可得計(jì)算A(k)的方法：先將A(k)賦為A(k1)；再對(duì)所有i=1..n，若A(k)[ik]

5、=1（即A(k1)[ik]=1），則對(duì)所有j=1..n，執(zhí)行：A(k)[ij]←A(k)[ij]∨A(k1)[kj]但這與前述Warshall算法中的第（3）步還有一定距離。若將上式改為：A(k)[ij]←A(k)[ij]∨A(k)[kj]（即把A(k1)[kj]改為A(k)[kj]）就可將上標(biāo)k去掉，式子就可進(jìn)一步變?yōu)椋篈[ij]←A[ij]∨A[kj]這樣可以只用存儲(chǔ)一個(gè)n階方陣的空間完成計(jì)算，且與前述Warshall算法中第（3）

6、步的式子一致。那么，可不可以把A(k1)[kj]改為A(k)[kj]呢？答案是肯定的。下面將證明在計(jì)算A(k)的過程中A(k1)[kj]與A(k)[kj]相等（A(k)被賦初值A(chǔ)(k1)后）。考察計(jì)算A(k)的方法只有當(dāng)i=k時(shí)A(k)[kj]的值才有可能改變，此時(shí)將式A(k)[ij]←A(k)[ij]∨A(k1)[kj]中的i換為k，得A(k)[kj]←A(k)[kj]∨A(k1)[kj]，對(duì)某一j，執(zhí)行該式的賦值操作前A(k)[kj