運(yùn)籌學(xué)圖與網(wǎng)絡(luò)(管理運(yùn)籌學(xué)圖與網(wǎng)絡(luò)模型,最短路徑怎么求)

1.管理運(yùn)籌學(xué) 圖與網(wǎng)絡(luò)模型,最短路徑怎么求

就是通過(guò)廣度搜索遍歷當(dāng)前節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系，然后再依次遞歸。

我給你開(kāi)個(gè)頭啊：

首先設(shè)首節(jié)點(diǎn)為1，那么子節(jié)點(diǎn)是2,3,4，那么我分別遍歷

1-2 = 4

1-3 = 5

1-4 = 2

全部遍歷完后我在從下面的第一個(gè)子節(jié)點(diǎn)開(kāi)始遍歷，

1(-2)-5 = 11

1(-2)-3 = 10 和1-3 = 5 對(duì)比 5<10 那么 1-3 = 5

1(-3)-2 = 11 和1-2 = 4進(jìn)行對(duì)比 4<11 那么1-2 = 4

1(-3)-6 = 14

1(-3)-4 = 6 和 1-4 = 2進(jìn)行對(duì)比 2< 6 那么 1-4 =2

1(-4)-3 = 3 和 1-3=5 進(jìn)行對(duì)比 5 > 3 那么 1-3 = 3

..

依次遍歷完整個(gè)圖

最開(kāi)始設(shè)1 到其他點(diǎn)的路徑為無(wú)限大，

然后依次遍歷，if( ( 1到當(dāng)前點(diǎn)的路徑 + 當(dāng)前點(diǎn)到某子節(jié)點(diǎn)的路徑) < (1 到該子節(jié)點(diǎn)的路徑) ）

1到該子節(jié)點(diǎn)的路徑 = 1到當(dāng)前點(diǎn)的路徑 + 當(dāng)前點(diǎn)到該子節(jié)點(diǎn)的路徑）