離散數(shù)學ch04圖論最短路徑與關(guān)鍵路徑(編輯修改稿)
2025-02-14 02:22 本頁面
【文章內(nèi)容簡介】 (v1,v2 ,v3,v5 ,v4) 7 9 最短路徑及關(guān)鍵路徑 10(v5)第 1短 V1 V5 V4 V2 V3 V6 10 10 100 20 50 20 50 30 5 10 v2 v3 v4 v5 v6 step1 50 30 100 10 ∞ 20(v4)第 2短 step2 50 30 20 ∞ 30(v3)第 3短 step3 40 30 ∞ 35(v2)第 4短 step4 35 50 45(v6)第 5短 step5 45 /V1 /V5 /V1 /V3 /V2 最短路徑及關(guān)鍵路徑 2(v2)第 1短 v2 v3 v4 v5 v6 v7 step1 2 5 3 ∞ ∞ 3(v4)第 2短 step2 4 3 ∞ 4(v3)第 3短 step3 8 4 ∞ 7(v5)第 4短 step4 7 9 8(v6)第 5短 step5 8 V2 V1 2 V3 V6 V7 V4 V5 5 3 1 2 5 7 5 3 5 1 7 step6 13(v7)第 6短 13 ∞ ∞ ∞ 9 9 14 最短路徑及關(guān)鍵路徑 ?試用 Dijkstra算法求下列簡單無向賦權(quán)圖中 V1到 V11的最短路徑。 最短路徑及關(guān)鍵路徑 v1 v2 v5 v4 v10 v8 v7 v11 v3 v6 v9 2 1 1 2 9 1 9 4 6 5 3 9 7 2 4 3 1 1 6 8 2 7 —— 求任意兩點間最短距離的 Floyd算法 基本思想： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最 短的路徑。 最短路徑及關(guān)鍵路徑 求每一對頂點之間的最短路徑 在實施一個工程計劃時，若將整個工程分成若干工序，有些工序可以同時實施，有些工序必須在完成另一些工序后才能實施，工序之間的次序關(guān)系可以用有向圖來表示，這種有向圖稱為 PERT圖。 最短路徑及關(guān)鍵路徑 關(guān)鍵路徑問題 —— PERT圖（計劃評審技術(shù)圖） , ,D V E Vv? ???定 義 ： 設(shè) 為 一 個 有 向 圖 稱{ | }( ,)D xv x V v x E?? ? ? ? ? ??v為 的 后 繼 元 集 ；{ | }( ,)D xv x V x v E?? ? ? ? ? ??v為 的 先 驅(qū) 元 集 . 最短路徑及關(guān)鍵路徑 關(guān)鍵路徑問題 —— PERT圖（計劃評審技術(shù)圖） ,
法律信息相關(guān)推薦
鄂ICP備17016276號-1