圖論論文--最短路徑算法應用

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

2、’，則G’即為t(R)的關系圖。G’的鄰接矩陣A應滿足：若圖G中存在從vi到vj路徑，即vi與vj連通，則A[ij]=1，否則A[ij]=0。這樣，求t(R)的問題就變?yōu)榍髨DG中每一對頂點間是否連通的問題。定義一個n階方陣序列A(0)A(1)A(2)…A(n)，每個方陣中的元素值只能取0或1。A(m)[ij]=1表示存在從vi到vj且中間頂點序號不大于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)的關系矩陣。那么應如何計算方陣序列A(0)A(1)A(2)…A(n)呢？很顯然，A(0)=M（M為R的關系矩陣）。若A(0)[i1]=1且A(0)[1j]=1，或A(0)[ij]=1，當且僅當存在從vi到vj且中間頂點序號不大于1的路徑，此時應將A(1

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

5、=1（即A(k1)[ik]=1），則對所有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]）就可將上標k去掉，式子就可進一步變?yōu)椋篈[ij]←A[ij]∨A[kj]這樣可以只用存儲一個n階方陣的空間完成計算，且與前述Warshall算法中第（3）

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