企業(yè)運(yùn)籌學(xué)--圖與網(wǎng)絡(luò)理論講義(編輯修改稿)
2025-03-25 19:59 本頁面
【文章內(nèi)容簡介】 S Tj ?? ? )()( kk TP ?? ?令 計算 求 若 vk=vn則已經(jīng)求得 vn到 v1的最短路線 ， 否則繼續(xù)計算 使用條件 lij≥0 算法解釋 若以 p(vi)記 v1到 vi的最短距離 ，則根據(jù)動態(tài)規(guī)劃原理應(yīng)有 第一步 取 P(v1)＝ 0， 而 T(vj)則是對 P(vj)所取的初值； )}({min)( iijij plP ?? ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ?????????SjTPj )(0)( 1??狄克斯拉算法 1 狄克斯拉 算法 2 算法解釋 第二步 利用 P(vi)已知 ， 據(jù)上式對 T(vj)進(jìn)行修正； v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 })(),(min{ ijij lPT ????????????SjTPj )(0)( 1??})(),(min {)( 12122 lPTT ?? ??? 2}20,min{ ???? })(),(min{)( 13133 lPTT ?? ??? 6}60,min{ ???? ??)(4?T 5 ??)( 6?T 狄克斯拉算法 3 算法解釋 第三步 對 T(vj)求 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 })(),(min{ ijij lPT ????????????SjTPj )(0)( 1??2)( 2 ??T 63 ??)( 4?T 5 ?)(6?T)}({min jS Tj?? ? )()(kk TP ?? ? 2)}(min{)(2 ?? jTP ?? 狄克斯拉算法 4 算法解釋 k=2, 不是最優(yōu) ， 繼續(xù) })(),(min{ ijij lPT ????????????SjTPj )(0)( 1?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 })(),(min{)( 23233 lPTT ?? ??? 5}32,6min{ ??? })(),(min{)( 24244 lPTT ?? ??? 10}82,min{ ???? })(),(min{)(25255 lPTT ?? ??? 11}92,min{ ???? ???? })(),(min{)( 26266 lPTT ???)}({min jS Tj?? ? )()(kk TP ?? ? 狄克斯拉算法 5 算法解釋 在所有的 T(vj)中確定最小的 })(),(min{ ijij lPT ????????????SjTPj )(0)( 1??)}({min jS Tj?? ? )()(kk TP ?? ? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 5)( 3 ??T 10)( 4 ??T 11)( 5 ? ??)( 6 5)()}({min 3 ??? ??? TT jSj 5)()( 33 ?? ?? TP 狄克斯拉算法 6 算法解釋 k=3, 不是最優(yōu) ， 繼續(xù) })(),(min{ ijij lPT ????????????SjTPj )(0)( 1?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 })(),(min{)( 34344 lPTT ?? ??? 10}55,10min{ ??? })(),()( 35355 lP ??8}35,11min{ ??? })(),(min{)(36366 lPTT ?? ??? ?????? }5,min{ 8)()}({min 5 ??? ??? TT jSj 8)()( 55 ?? ?? TP)}({min jS Tj?? ? )()(kk TP ?? ? 狄克斯拉算法 7 算法解釋 k=5, 不是最優(yōu) ， 繼續(xù) })(),(min{ ijij lPT ????????????SjTPj )(0)( 1??)}({min jS Tj?? ? )()(kk TP ?? ? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 })(),(min{)( 54544 lPTT ?? ??? 10}8,10min{ ???? })(),(min{)( 56566 lPT ?? ??9}18,min{ ???? 9)()}({min 6 ??? ??? TT jSj 9)()( 66 ?? ?? TP 狄克斯拉算法 8 算法解釋 k=6=n, 已經(jīng)是最優(yōu) 。 如果希望計算 v1到 v4的最短距離 ， 繼續(xù) })(),(min{ ijij lPT ????????????SjTPj )(0)( 1??)}({min jS Tj?? ? )()(kk TP ?? ? 10}39,10min{})(),(min{)( 64644 ????? lPTT ??? 10)()}({min 4 ??? ??? TT jSj 10)()( 44 ?? ?? TP v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 狄克斯拉算法 9 表格實(shí)現(xiàn) ???????????????????????????????????013103930583503698302620654321??????Lvj v1 v2 v3 v4 v5 v6 初始值 T( vj ) 0 ∞ ∞ ∞ ∞ ∞ v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 第一次 P( )+lij 0+2 0+6 0+∞ 0+∞ 0+∞ T( ) 2 6 ∞ ∞ ∞ 狄克斯拉算法 10 表格實(shí)現(xiàn) vj v1 v2 v3 v4 v5 v6 初始值 T( vj ) 0 ∞ ∞ ∞ ∞ ∞ 第一次 P( )+lij 0+2 0+6 0+∞ 0+∞ 0+∞ T( ) 2 6 ∞ ∞ ∞ 第二次 P( )+lij 2+3 2+8 2+9 2+∞ T( ) 5 10 11 ∞ 第三次 P( )+lij 5+5 5+3 5+∞ T( ) 10 8 ∞ 第四次 P( )+lij 8+ ∞ 8+1 T( ) 10 9 福德算法 1 適用于有負(fù)權(quán)，但無負(fù)回路的有向或無向網(wǎng)絡(luò)，其算法步驟如下： 令 jj ld 1)1( ? }min{ )()1(ijkikj ldd ???計算 若對所有 j )()1( kjkj dd ??則最優(yōu)，否則把 k的值加 1，繼續(xù)計算。 若 k=n1， 則說明存在負(fù)回路，最短路線不存在。 福德算法 2 適用于有負(fù)權(quán)，但無負(fù)回路的有向或無向網(wǎng)絡(luò)， 算法中 dj(k)為從 υ1到 υj的邊數(shù)不超過 k的路線中距離最短的。 算法依據(jù)的思想是動態(tài)規(guī)劃最優(yōu)性原理，在此處形成遞推公式。 }min{ )()1( ijkikj ldd ??? 福德算法 3 算法示例 }min{ )()1(ijkikj ldd ??? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L1jj ld ?)1( 福德算法 4 }min{)()1( ijkikj ldd ??? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ 福德算法 5 }min{ 1)1()2(1 ii ldd ?? v1 1 3 9 5 3 8 3 6 2
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1