圖論模型：最短路ppt課件-資料下載頁
2025-05-06 23:19本頁面
【正文】 （即最短路長度），之間的距離到表示點(diǎn)個(gè)點(diǎn)：有設(shè)網(wǎng)絡(luò).I,)() } ,({m i n,m ax)(11,1為直徑為網(wǎng)絡(luò)的中心，點(diǎn)則稱若：記定義kkinijinjivIvdvdIdvd ??????? ? 例 4 教育部們打算在某新建城區(qū)建一所學(xué)校 ,讓附近七個(gè)居民區(qū)的學(xué)生就近入學(xué)。七個(gè)居民區(qū)之間的道路如下圖所示 . ? 學(xué)校應(yīng)建在哪個(gè)居民區(qū)， ? 才能使大家都方便？ ? （圖中距離單位：百米） ? 解：由狄克斯特拉（ Dijkstra） ? 算法計(jì)算得各居民之間的最短距離列表如下 : 7234 324615724ABDCEFGA B C D E F G d (vi) ∑di,j A 0 3 4 5 7 8 10 10 37 B 3 0 3 2 4 5 7 7 24 C 4 3 0 5 5 6 8 8 31 D 5 2 5 0 2 3 5 5(min) 22(min) E 7 4 5 2 0 1 3 7 22(min) F 8 5 6 3 1 0 2 8 25 G 10 7 8 5 3 2 0 10 35 ? 從上表來看，應(yīng)選擇 D作為學(xué)校的地址，這樣最遠(yuǎn)的居民區(qū)離學(xué)校的距離也只有 500米 . ? 在現(xiàn)實(shí)生活中，同一網(wǎng)絡(luò)中的各點(diǎn)要求提供的服務(wù)的數(shù)量也不盡 相同。我們將各點(diǎn)要求提供的服務(wù)數(shù)量作為該點(diǎn)的權(quán)數(shù)，重新考慮選址問題。 ? 例 5 在例 4中，若七個(gè)區(qū)的學(xué)生人數(shù)分別為 24 3 50人，試問教育部門應(yīng)將學(xué)校建在哪個(gè)居民區(qū)，才能使大家都方便？ .),()}({m i n),2,1()(),(211,為網(wǎng)絡(luò)的重心則稱點(diǎn)若令點(diǎn)的權(quán)為：設(shè)定義kkininjjiiiiiivvhvhnidfvhvffv????????? ? ? 所以應(yīng)選擇 E作為新建學(xué)校的地址。 ??? 7 1 ,)( j jiii dfvhA B C D E F G A 0 75 180 150 140 280 500 1325 B 120 0 135 60 80 175 350 920 C 160 75 0 150 100 210 400 1095 D 200 50 225 0 40 105 250 870 E 280 100 225 60 0 35 150 850（ min） F 320 125 270 90 20 0 100 925 G 400 175 360 150 60 70 0 1215 ? 練習(xí)題 ? 準(zhǔn)備在 A， B， C， D， E， F， G七個(gè)居民點(diǎn)中建一個(gè)劇場，各個(gè)居民點(diǎn)之間的距離和聯(lián)系如下圖 1所示，問劇場應(yīng)建在那一個(gè)居民點(diǎn)，使各點(diǎn)到劇場的距離之和為最?。? ? 求上圖 2中從點(diǎn) v1到 v8的最短路及長度 . 64321 . 52 . 5 1 . 83 1 . 5V5V3 V4V2V6V1 V 728669921 72142V1V3V2V4V5V7V6V8圖 1 圖
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1