數(shù)學模型floyd算法-展示頁
2025-01-24 11:55本頁面
【正文】 ijr , r ij 的含義是從 v i 到 v j 的最短路要經(jīng)過點號為 r ij 的點．?? ?? )( )0()0( ijrR , jr ij ?)0(每求得一個 D ( k ) 時，按下列方式產(chǎn)生相應的新的 R ( k )否則若 )1()1()1()1()(?????????? kkjkikkijkijkijdddrkr在建立距離矩陣的同時可建立路徑矩陣 R． 即當 vk被插入任何兩點間的最短路徑時，被記錄在 R(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑． )(?D )(?R)(?R 數(shù)學模型與實驗 Tsinghua University Uncertainty Theory Laboratory 6 i j 算法原理 —— 查找最短路路徑的方法 若 1)( pr ij ?? ，則點 p 1 是點 i 到點 j 的最短路的中間點 . 然后用同樣的方法再分頭查找．若：（１） 向點 i 追朔得： 2)(1pr ip ?? , 3)(2pr ip ?? , … , kip prk?)( ?（２） 向點 j 追朔得： 1)(1qr jp ?? , 2)(1qr jq ?? , … , jr jqm?)( ?pk p2 p1 p3 q1 q2 qm 則由點 i到 j的最短路的路徑為： jqqqpppi mk , 21,12 ?? 數(shù)學模型與實驗 Tsinghua University Uncertainty Theory Laboratory 7 算法步驟 F l o y d 算法： 求任意兩點間的最短路．D ( i , j ) ： i 到 j 的距離．R( i , j ) ： i 到 j 之間的插入點．輸入 : 帶權鄰接矩陣 w ( i , j )（１） 賦初值：對所有 i , j , d ( i , j ) ? w( i , j ) , r( i , j )? j , k? 1( 2 ) 更新 d( i , j ) , r ( i , j )對所有 i , j ，若 d( i , k ) + d ( k , j ) d ( i , j ) ，則 d( i
教學教案相關推薦
鄂ICP備17016276號-1