《圖與網(wǎng)絡(luò)分析》PPT課件

《《圖與網(wǎng)絡(luò)分析》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《圖與網(wǎng)絡(luò)分析》PPT課件（190頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第 十 一 章 圖 與 網(wǎng) 絡(luò) 分 析Graph theory and network analysis 第 十 一 章 圖 與 網(wǎng) 絡(luò) 分 析11.1 引 言 引 言圖 論 是 專 門 研 究 圖 的 理 論 的 一 門 數(shù) 學(xué) 分 支 ，屬 于 離 散 數(shù) 學(xué) 范 疇 ， 與 運(yùn) 籌 學(xué) 有 交 叉 ， 它 有200多 年 歷 史 ， 大 體 可 劃 分 為 三 個(gè) 階 段 。 引 言第 一 階 段 從 十 八 世 紀(jì) 中 葉 到 十 九 世 紀(jì) 中 葉 ， 處 于萌 芽 階 段 ， 多 數(shù) 問 題 由 游 戲 而 產(chǎn) 生 ， 最有 代 表 性 的 工 作 是 所 謂 的 Euler七 橋

2、 問題 ， 即 一 筆 畫 問 題 。 引 言第 二 階 段 從 十 九 世 紀(jì) 中 葉 到 二 十 世 紀(jì) 中 葉 ， 這 時(shí) ，圖 論 問 題 大 量 出 現(xiàn) ， 如 Hamilton問 題 ，地 圖 染 色 的 四 色 問 題 以 及 可 平 面 性 問 題 等 ，這 時(shí) ， 也 出 現(xiàn) 用 圖 解 決 實(shí) 際 問 題 ， 如Cayley把 樹 應(yīng) 用 于 化 學(xué) 領(lǐng) 域 ， Kirchhoff用 樹 去 研 究 電 網(wǎng) 絡(luò) 等 . 引 言第 三 階 段 二 十 世 紀(jì) 中 葉 以 后 ， 由 生 產(chǎn) 管 理 、 軍 事 、交 通 、 運(yùn) 輸 、 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 等 方 面 提 出

3、實(shí) 際問 題 ， 以 及 大 型 計(jì) 算 機(jī) 使 大 規(guī) 模 問 題 的 求解 成 為 可 能 ， 特 別 是 以 Ford和 Fulkerson建 立 的 網(wǎng) 絡(luò) 流 理 論 ， 與 線 性 規(guī) 劃 、 動(dòng) 態(tài) 規(guī)劃 等 優(yōu) 化 理 論 和 方 法 相 互 滲 透 ， 促 進(jìn) 了 圖論 對(duì) 實(shí) 際 問 題 的 應(yīng) 用 。 哥 尼 斯 堡 七 橋 問 題 哥 尼 斯 堡 七 橋 問 題 最 后 ， 數(shù) 學(xué) 家 Euler在 1736年 巧 妙 地 給 出 了這 個(gè) 問 題 的 答 案 ， 并 因 此 奠 定 了 圖 論 的 基 礎(chǔ)Euler把 A、 B、 C、 D四 塊 陸 地 分 別 收 縮

4、 成 四 個(gè)頂 點(diǎn) ， 把 橋 表 示 成 連 接 對(duì) 應(yīng) 頂 點(diǎn) 之 間 的 邊 ， 問題 轉(zhuǎn) 化 為 從 任 意 一 點(diǎn) 出 發(fā) ， 能 不 能 經(jīng) 過 各 邊 一次 且 僅 一 次 ， 最 后 返 回 該 點(diǎn) 。 這 就 是 著 名 的Euler問 題 。 哥 尼 斯 堡 七 橋 問 題 哥 尼 斯 堡 七 橋 問 題 圍 坐 問 題 有 7個(gè) 人 圍 桌 而 坐 ， 如 果 要 求 每 次 相 鄰 的人 都 與 以 前 完 全 不 同 ， 試 問 不 同 的 就 座 方案 共 有 多 少 種 ？用 頂 點(diǎn) 表 示 人 ， 用 邊 表 示 兩 者 相 鄰 ， 因?yàn)?最 初 任 何 兩 個(gè)

5、 人 都 允 許 相 鄰 ， 所 以 任何 兩 點(diǎn) 都 可 以 有 邊 相 連 。 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 假 定 第 二 次 就 座 方 案 是（ 1， 3， 5， 7， 2， 4， 6， 1） ，那 么 第 三 次 就 座 方 案 就 不 允 許 這 些 頂 點(diǎn) 之間 繼 續(xù) 相 鄰 ， 只 能 從 圖 中 刪 去 這 些 邊 。圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題

6、圍 坐 問 題 假 定 第 三 次 就 座 方 案 是（ 1， 4， 7， 3， 6， 2， 5， 1） ， 那 么 第 四次 就 座 方 案 就 不 允 許 這 些 頂 點(diǎn) 之 間 繼 續(xù) 相 鄰 ，只 能 從 圖 中 刪 去 這 些 邊 ， 只 留 下 7點(diǎn) 孤 立 點(diǎn) ，所 以 該 問 題 只 有 三 個(gè) 就 座 方 案 。圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 假 定 第 三 次 就 座 方 案 是（ 1， 4， 7， 3， 6， 2， 5， 1） ，那 么 第 四

7、次 就 座 方 案 就 不 允 許 這 些頂 點(diǎn) 之 間 繼 續(xù) 相 鄰 ， 只 能 從 圖 中 刪去 這 些 邊 ， 只 留 下 7點(diǎn) 孤 立 點(diǎn) ， 所 以該 問 題 只 有 三 個(gè) 就 座 方 案 。圍 坐 問 題 哈 密 頓 （ Hamilton） 回 路 是 十 九世 紀(jì) 英 國(guó) 數(shù) 學(xué) 家 哈 密 頓 提 出 ， 給 出 一個(gè) 正 12面 體 圖 形 ， 共 有 20個(gè) 頂 點(diǎn) 表 示20個(gè) 城 市 ， 要 求 從 某 個(gè) 城 市 出 發(fā) 沿 著棱 線 尋 找 一 條 經(jīng) 過 每 個(gè) 城 市 一 次 而 且僅 一 次 ， 最 后 回 到 原 處 的 周 游 世 界 線路 （ 并 不

8、 要 求 經(jīng) 過 每 條 邊 ） 。哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 引 言 瑞 士 數(shù) 學(xué) 家 Euler 在 1736年 發(fā) 表 的 一 篇 題 為“ 依 據(jù) 幾 何 位 置 的 解 題 方 法 ” 的 論 文 ， 有 效 的 解決 了 哥 尼 斯

9、堡 七 橋 問 題 ， 是 有 記 載 的 第 一 篇 圖 論論 文 ， Euler被 認(rèn) 為 是 圖 論 的 創(chuàng) 始 人 。 圖 論 的 第 一 本 專 著 是 匈 牙 利 的 O Konig寫 的 “ 有限 圖 與 無 限 圖 的 理 論 ” ， 發(fā) 表 于 1936。 從 1736到 1936， 前 后 200年 ， 總 的 來 講 這 一 時(shí)期 圖 論 發(fā) 展 緩 慢 。 直 到 20世 紀(jì) 中 葉 ， 電 子 計(jì) 算 機(jī) 的 發(fā) 展 和 零 散 數(shù) 學(xué)問 題 具 有 越 來 越 重 要 的 地 位 ， 使 得 圖 論 得 以 迅 速發(fā) 展 第 十 一 章 圖 與 網(wǎng) 絡(luò) 分 析11.

10、1 引 言11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 圖 論 是 專 門 研 究 圖 的 理 論 的 一 門數(shù) 學(xué) 分 支 ， 主 要 研 究 點(diǎn) 和 線 之 間的 幾 何 關(guān) 系 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念定 義 ：圖 是 由 點(diǎn) 集 V=（ vi ） 和 V 中 元 素 的 無 序 對(duì) 的 一 個(gè) 集合 E=（ ek ） 所 構(gòu) 成 的 二 元 組 ， 記 為 G=（ V， E） ，其 中 ： V= （ v1， v2， . vm） 是 m個(gè) 頂 點(diǎn) 集 合 ； E= （ e1， e2， . en） 是 n條 邊 集 合 。

11、當(dāng) V， E為 有 限 集 合 時(shí) ， G稱 為 有 限 圖 ， 否 則 稱 為無 限 圖 ， 本 章 只 討 論 有 限 圖 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念說 明 ：（ 1） V非 空 ， 即 沒 有 頂 點(diǎn) 的 圖 不 討 論 ；（ 2） E無 非 空 條 件 ， 即 允 許 沒 有 邊 ；（ 3） E是 一 個(gè) 不 與 V 中 頂 點(diǎn) 相 交 的 邊 集 合 ； （ 指 點(diǎn) 只 在 邊 的 端 點(diǎn) 處 相 交 ）（ 4） 任 一 條 邊 必 須 與 一 對(duì) 頂 點(diǎn) 關(guān) 聯(lián) ， 反

12、 之 不 然 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念定 義對(duì) 任 一 條 邊 （ vi， vj） 屬 于 E，如 果 邊 （ vi， vj） 的 端 點(diǎn) 無 序 ， 則 它 是 無 向 邊 ， 此時(shí) 圖 為 無 向 圖 。如 果 如 果 邊 （ vi， vj） 的 端 點(diǎn) 有 序 ， 則 它 表 示 以 vi為 始 點(diǎn) ， v j為 終 點(diǎn) 的 有 向 邊 （ 或 稱 為 弧 ） ， 此 時(shí)圖 為 有 向 圖 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基

13、本 概 念定 義 （ 鏈 ）如 果 圖 中 的 某 些 點(diǎn) 、 邊 可 以 排 列 成 點(diǎn) 和 邊的 交 錯(cuò) 序 列 ， 則 稱 此 為 一 條 鏈 。定 義 （ 圈 ）如 一 條 鏈 中 起 點(diǎn) 和 終 點(diǎn) 重 合 ， 則 稱 此 為 一條 圈 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念定 義 （ 鏈 ）如 果 圖 中 的 某 些 點(diǎn) 、 邊 可 以 排 列

14、成 點(diǎn) 和 邊的 交 錯(cuò) 序 列 ， 則 稱 此 為 一 條 鏈 。定 義 （ 圈 ）如 一 條 鏈 中 起 點(diǎn) 和 終 點(diǎn) 重 合 ， 則 稱 此 為 一條 圈 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念定 義 （ 鏈 ）如

15、 果 圖 中 的 某 些 點(diǎn) 、 邊 可 以 排 列 成 點(diǎn) 和 邊的 交 錯(cuò) 序 列 ， 則 稱 此 為 一 條 鏈 。定 義 （ 圈 ）如 一 條 鏈 中 起 點(diǎn) 和 終 點(diǎn) 重 合 ， 則 稱 此 為 一條 圈 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 圖 的 矩 陣 表 示 一 個(gè) 圖 非 常 直 觀 ， 但 是 不 容 易 計(jì) 算 ，特 別 不 容 易 在 計(jì) 算 機(jī) 上 進(jìn) 行 計(jì) 算 ， 一 個(gè) 有效 的 解 決 辦 法 是 將 圖 表 示 成 矩 陣 形 式 ， 通常 采 用 的 矩 陣 是 鄰 接 矩 陣 、 邊 長(zhǎng) 鄰 接 矩 陣 、弧 長(zhǎng) 矩 陣 和 關(guān) 聯(lián) 矩

16、陣 。 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念 11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念賦 權(quán) 圖 或 網(wǎng) 絡(luò)在 圖 的 各 邊 上 一 個(gè) 數(shù) 量 指 標(biāo) （ cij） ， 具 體 表示 這 條 邊 的 權(quán) （ 距 離 ， 單 價(jià) ， 通 過 能 力 等 ） 。無 向 網(wǎng) 絡(luò) ； 有 向 網(wǎng) 絡(luò) ； 混 合 網(wǎng) 絡(luò) ；邊 權(quán) 網(wǎng) 絡(luò) ； 點(diǎn) 權(quán) 網(wǎng) 絡(luò) 。 第 十 一 章 圖 與 網(wǎng) 絡(luò) 分 析11.1 引 言11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念11.3 最 短 路 問 題 11.3

17、 最 短 路 問 題對(duì) 一 個(gè) 賦 權(quán) 的 有 向 圖 D ;指 定 的 兩 個(gè) 點(diǎn) Vs 和 Vt ；找 到 一 條 從 Vs 到 Vt 的 路 ， 使 得 這 條 路 上 所 有弧 的 權(quán) 數(shù) 的 總 和 最 小 ；這 條 路 被 稱 之 為 從 Vs到 Vt的 最 短 路 。這 條 路 上 所 有 弧 的 權(quán) 數(shù) 總 和 被 稱 為 從 Vs到 Vt的距 離 。 11.3 最 短 路 問 題一 、 求 解 最 短 路 的 Dijkstra算 法 (迪 科 斯 徹 ， 雙 標(biāo) 號(hào) 法 ） 對(duì) 圖 中 的 點(diǎn) Vj 賦 予 兩 個(gè) 標(biāo) 號(hào) （ lj, kj） , 第 一 個(gè) 標(biāo) 號(hào) lj 表

18、 示 從 起 點(diǎn) Vs 到 Vj 的 最 短 路 的 長(zhǎng) 度 ， 第 二 個(gè) 標(biāo) 號(hào) kj 表 示 在 Vs 到 Vj 的 最 短 路 上 Vj 前 面 一 個(gè)鄰 點(diǎn) 的 下 標(biāo) 。例 如 ： V 6（ 8,4) 表 示 ， 從 起 點(diǎn) V 到 V 的 最 短 路 的 長(zhǎng) 度 為 在 這 條 最 短 路 上 V 的 前 一 個(gè) 鄰 點(diǎn) 為 V 。 11.3 最 短 路 問 題步 驟 ：1. 給 出 點(diǎn) V1 以 標(biāo) 號(hào) (0， s)2. 找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J,以 及 弧 的 集 合 3. 如 果 上 述 弧 的 集 合 是 空 集 ， 則

19、 計(jì) 算 結(jié) 束 。 如 果 Vt 已 標(biāo) 號(hào) （ lt,kt） ， 則 Vs 到 Vt 的 距 離 為 lt 。 如 果 V t 未 標(biāo) 號(hào) ， 則 可 以 斷 言 不 存 在 從 Vs到 Vt的 有 向 路 。 如 果 上 述 的 弧 的 集 合 不 是 空 集 ， 則 轉(zhuǎn) 下 一 步 。4. 對(duì) 上 述 弧 的 集 合 中 的 每 一 條 弧 ， 計(jì) 算 sij=li+cij 。 在 所 有 的 sij中 ， 找 到 其 值 為 最 小 的 弧 。 不 妨 設(shè) 此 弧 為（ Vc,Vd） ， 則 給 此 弧 的 終 點(diǎn) 以 雙 標(biāo) 號(hào) （ scd,c） ,返 回 步 驟 2。( , )

20、| , i j i jv v v I v J 11.3 最 短 路 問 題例 求 下 圖 中 v1 到 v6 的 最 短 路 v23 5 2 7 53 1512v1 v6v 5v3 v4 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4 .給 出 點(diǎn) V1 以 標(biāo) 號(hào) (0， s) (0， s) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) .找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J， 以 及

21、 弧 的 集 合( , ) | , i j i jv v v I v J 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) .找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1J V2, V3, V4, V5, V6 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) .找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合

22、I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1J V2, V3, V4, V5, V6 弧 的 集 合 (V1 , V2), (V1 , V3), (V1 , V4)( , ) | , i j i jv v v I v J 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)2.對(duì) 每 一 條 弧 ， 計(jì) 算 sij=li+cij 。 找 到 其 值 為 最 小 的 弧 , 給 此 弧 的 終 點(diǎn) 以 雙 標(biāo) 號(hào) s12=l1

23、+c12 =0 + 3 =3 s13=l1+c13 =0 + 2 =2 s14=l1+c14 =0 + 5 =5 MIN (s12 , s13 , s14) = s13 =2 (2， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)3.找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V3 J V2, V4, V5, V6 (2， 1) 11.3 最 短 路 問 題解 采 用 D

24、ijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)3.找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V3 J V2, V4, V5, V6 弧 的 集 合 (V1 , V2), (V1 , V4), (V3 , V4)( , ) | , i j i jv v v I v J (2， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)3

25、.對(duì) 每 一 條 弧 ， 計(jì) 算 sij=li+cij 。 找 到 其 值 為 最 小 的 弧 , 給 此 弧 的 終 點(diǎn) 以 雙 標(biāo) 號(hào) s12=l1+c12 =0 + 3 =3 s14=l1+c14 =0 + 5 =5 s34=l3+c34 =2 + 1 =3 MIN (s12 , s14 , s34) = s12 = s34 = 3 (2， 1)(3， 1) (3， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)4.找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J,

26、 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V2, V3, V4 J V5, V6 (2， 1)(3， 1) (3， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)4.找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V2, V3, V4 J V5, V6弧 的 集 合 (V2 , V6), (V4 , V6)( , ) |

27、, i j i jv v v I v J (2， 1)(3， 1) (3， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)4.對(duì) 每 一 條 弧 ， 計(jì) 算 sij=li+cij 。 找 到 其 值 為 最 小 的 弧 , 給 此 弧 的 終 點(diǎn) 以 雙 標(biāo) 號(hào) s26=l2+c26 =3 + 7 =10 s46=l4+c46 =3 + 5 =8MIN (s26 , s46) = s46 = 8 (2， 1)(3， 1) (3， 3) (8， 4) 11.3 最 短 路 問 題解 采 用 Dijks

28、tra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)5.找 出 已 標(biāo) 號(hào) 點(diǎn) 的 集 合 I， 沒 標(biāo) 號(hào) 的 點(diǎn) 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V2, V3, V4 , V6 J V6 (2， 1)(3， 1) (3， 3)上 述 弧 的 集 合 是 空 集 ， 計(jì) 算 結(jié) 束 。 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) (2， 1)(3， 1)(3， 3) (8， 4)由 于

29、V 已 標(biāo) 號(hào) （ , ）則 V 到 V 的 距 離 為 。最 短 路 徑 為 (由 倒 推 得 到 )V V V V 11.3 最 短 路 問 題 例 電 信 公 司 準(zhǔn) 備 在 甲 、 乙 兩 地 沿 路 架 設(shè) 一 條光 纜 線 ， 問 如 何 架 設(shè) 使 其 光 纜 線 路 最 短 ？ 下 圖 給 出 了 甲 乙 兩 地 間 的 交 通 圖 。 權(quán) 數(shù) 表 示 兩 地 間 公 路 的 長(zhǎng) 度 （ 單 位 ： 公 里 ） 。 V 1 （ 甲 地 ） 15 17 62444 310 6 5V2 V7 （ 乙 地 ）V3 V4 V5 V6 11.3 最 短 路 問 題 這 是 一 個(gè) 求 無

30、 向 圖 的 最 短 路 的 問 題 。 可 以 把 無 向 圖 的 每 一 邊 （ vi,vj） 都 用 方 向 相 反 的 兩 條弧 （ vi,vj） 和 （ vj,vi） 代 替 ， 就 化 為 有 向 圖 ， 也 可 直 接 在 無 向 圖 中 用 Dijkstra算 法 來 求 解 。 只 要 在 算 法 中 把 從 已 標(biāo) 號(hào) 的 點(diǎn) 到 未 標(biāo) 號(hào) 點(diǎn) 弧 的 集 合 改成 已 標(biāo) 號(hào) 點(diǎn) 到 未 標(biāo) 號(hào) 點(diǎn) 邊 的 集 合 即 可 。 11.3 最 短 路 問 題例 求 下 圖 中 v1 到 v 的 最 短 路 V1 15 17 6244310 6 5V2V 3 V4 V5 V

31、6V7 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 .給 出 點(diǎn) V1 以 標(biāo) 號(hào) (0， s)(0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7 11.3 最 短 路 問 題解 采 用 Dijkstra算 法2. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V1 , V2), (V1 , V3) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7 11.3 最 短 路 問 題解 采 用 Dijkstra算 法s 12=l1+c12 =0 + 15 =15s13=l1+c13 =0 +

32、10 =10MIN (s12 , s13) = s13 =102. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V1 , V2), (V1 , V3) (0， s) V1 15 17 6244310 6 5V2V3 V4 V5 V6V7(10， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法3. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V1 , V2), (V3 , V2) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1) 11.3 最 短 路 問 題解 采 用

33、 Dijkstra算 法3. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V1 , V2), (V3 , V2) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1) s12=l1+c12 =0 + 15 =15 s32=l3+c32 =10 + 3 =13 s35=l3+c35 =10 + 4 =14MIN (s12 , s32 , s35) = s32 =13 (13， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法4. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (

34、V2 , V4), (V2 , V7) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 s 24=l2+c24 =13 + 6 =19 s27=l2+c27 =13 + 17 =30 s35=l3+c35 =10 + 4 =14MIN (s24 , s27 , s35) = s35 =144. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V3 , V5) (0， s) V1 15

35、 17 6244310 6 5V2V3 V4 V5 V6V7(10， 1)(13， 3) (14， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法5. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V5 , V6) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法5. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V2 , V4),

36、 (V2 , V7) , (V5 , V4) , (V5 , V6) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3) s24=l2+c24 =13 + 6 =19 s27=l2+c27 =13 + 17 =30 s54=l5+c54 =14 + 4 =18 s56=l5+c56 =14 + 2 =16MIN (s24 , s27 , s54 , s56) = s56 =16 (16， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法6. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集

37、合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3)(16， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法6. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3)(16， 5)

38、 s24=l2+c24 =13 + 6 =19 s27=l2+c27 =13 + 17 =30 s54=l5+c54 =14 + 4 =18 s67=l6+c67 =16 + 6 =22MIN (s24 , s27 , s54 , s67) = s54 =18 (18， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法7. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V2 , V7), (V4 , V7) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 5)

39、(16， 5)(18， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法7. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合 (V2 , V7), (V4 , V7) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 5)(16， 5)(18， 5) s27=l2+c27 =13 + 17 =30 s47=l4+c47 =18 + 5 =23 s67=l6+c67 =16 + 6 =22MIN (s27 , s47 , s67) = s67 =22 (22， 6)

40、11.3 最 短 路 問 題解 采 用 Dijkstra算 法8. 已 標(biāo) 號(hào) 點(diǎn) 至 沒 標(biāo) 號(hào) 的點(diǎn) 的 邊 的 集 合為 空 ， 計(jì) 算 結(jié) 束 (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 5)(16， 5)(18， 5) (22， 6) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法(0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3)(16， 5)(18， 5) (22， 6)由 于 V 7 已 標(biāo) 號(hào) （ 22

41、,6）則 V 到 V 的 距 離 為 22。最 短 路 徑 為 V V3 V5 V6 V7 11.3 最 短 路 問 題習(xí) 題 采 用 Dijkstra算 法 求 V 到 V8 的 最 短 路4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1) 11.3 最 短 路 問 題4 95 41676

42、544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2) 11.3 最 短 路 問 題4

43、95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3

44、V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3

45、 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) (15， 7) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) (15， 7) 由 于 V8 已 標(biāo) 號(hào) （ 15,7）

46、則 V 到 V8的 距 離 為 15。最 短 路 徑 為 V V2 V5 V7 V8 11.3 最 短 路 問 題6 V1 V8 V2 V 5 V7(0， s) (4， 1) (8， 2) (14， 5) (15， 7) 由 于 V8 已 標(biāo) 號(hào) （ 15,7）則 V 到 V8的 距 離 為 15。最 短 路 徑 為 V V2 V5 V7 V8 11.3 最 短 路 問 題例 某 公 司 使 用 一 臺(tái) 設(shè) 備 ， 在 每 年 年 初 ， 公 司 就 要決 定 是 購(gòu) 買 新 的 設(shè) 備 還 是 繼 續(xù) 使 用 舊 設(shè) 備 。 如 果 購(gòu) 置 新 設(shè) 備 ， 就 要 支 付 一 定 的 購(gòu) 置

47、 費(fèi) ， 當(dāng)然 新 設(shè) 備 的 維 修 費(fèi) 用 就 低 。 如 果 繼 續(xù) 使 用 舊 設(shè) 備 ， 可 以 省 去 購(gòu) 置 費(fèi) ， 但 維修 費(fèi) 用 就 高 了 。 請(qǐng) 設(shè) 計(jì) 一 個(gè) 五 年 之 內(nèi) 的 更 新 設(shè) 備 的 計(jì) 劃 ， 使 得五 年 內(nèi) 購(gòu) 置 費(fèi) 用 和 維 修 費(fèi) 用 總 的 支 付 費(fèi) 用 最 小 。 11.3 最 短 路 問 題設(shè) 備 每 年 年 初 的 價(jià) 格 表設(shè) 備 維 修 費(fèi) 如 下 表年 份 1 2 3 4 5年 初 價(jià) 格 11 11 12 12 13使 用 年 數(shù) 0-1 1-2 2-3 3-4 4-5每 年 維 修費(fèi) 用 5 6 8 11 18 年 份

48、 1 2 3 4 5年 初 價(jià) 格 11 11 12 12 13使 用 年 數(shù) 0-1 1-2 2-3 3-4 4-5每 年 維 修費(fèi) 用 5 6 8 11 181 2 3 4 5 6第 1年 購(gòu) 入 新 設(shè) 備 16 22 30 41 59第 2年 購(gòu) 入 新 設(shè) 備 16 22 30 41第 3年 購(gòu) 入 新 設(shè) 備 17 23 31 第 4年 購(gòu) 入 新 設(shè) 備 17 23第 5年 購(gòu) 入 新 設(shè) 備 18第 6年 購(gòu) 入 新 設(shè) 備 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第

49、i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23 11.3 最 短 路 問 題例 3的 解 ： 用 vi表

50、示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v6（ v1,v4） 表 示 ， 第 1年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 4年 年 初 。（ v4,v5） 表 示 ， 第 4年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 5年 年 初（ v5,v6） 表 示 ， 第 5年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 6年 年 初30 17 18 11.3 最 短 路 問 題例 3的 解 ： 用

51、 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41

52、5916 22 30 41 3123 17 1817 23(0， s) (16， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,v

53、j） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 2

54、3(0， s) (16， 1) (22， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1)(22， 1) (30， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表

55、示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817

56、 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一

57、臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) (53， 3)(53， 4) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購(gòu) 進(jìn) 的 設(shè) 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v

58、3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) (53， 3)(53， 4) 11.3 最 短 路 問 題其 最 短 路 有 兩 條 : V V3 V6 ; V V4 V6 .即 第 1年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 3年 年 初 ， 第 3年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使用 到 第 5年 年 底 ； 或 第 1年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 4年 年 初 ， 第 4年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 5年 年 底 。

59、費(fèi) 用 均 為 53。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) (53， 3)(53， 4) 11.3 最 短 路 問 題其 最 短 路 有 兩 條 : V V3 V6 ; V V4 V6 .即 第 1年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 3年 年 初 ， 第 3年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使用 到 第 5年 年 底 ； 或 第 1年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 4年 年 初 ， 第 4年 年 初 購(gòu) 進(jìn) 新 設(shè)

60、備 使 用 到 第 5年 年 底 。 費(fèi) 用 均 為 53。v 1 v2 v3 v4 v5 v631 1822 (53， 3)(22， 1) 11.3 最 短 路 問 題其 最 短 路 有 兩 條 : V V3 V6 ; V V4 V6 .即 第 1年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 3年 年 初 ， 第 3年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使用 到 第 5年 年 底 ； 或 第 1年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 4年 年 初 ， 第 4年 年 初 購(gòu) 進(jìn) 新 設(shè) 備 使 用 到 第 5年 年 底 。 費(fèi) 用 均 為 53。v 1 v2 v3 v4 v5 v630 2

61、3 (53， 4)(30， 1) 11.3 最 短 路 問 題第 1年 第 2年 第 3年 第 4年 第 5年購(gòu) 買 費(fèi) 11 12 13 14 14機(jī) 器 役 齡 0 1 1 2 2 3 3 4 4 5維 修 費(fèi) 5 6 8 11 18 殘 值 4 3 2 1 0習(xí) 題 ： 工 廠 使 用 一 臺(tái) 設(shè) 備 ， 每 年 年 初 作 出 決 定 ， 如 果繼 續(xù) 使 用 舊 的 ， 要 支 付 維 修 費(fèi) ， 如 果 購(gòu) 買 新 的 支 付 購(gòu)買 費(fèi) 。 試 制 定 五 年 更 新 計(jì) 劃 11.3 最 短 路 問 題1 2 3 4 5 6第 1年 購(gòu) 入 新 設(shè) 備 12 19 28 40 5

62、9第 2年 購(gòu) 入 新 設(shè) 備 13 20 29 41第 3年 購(gòu) 入 新 設(shè) 備 14 21 30第 4年 購(gòu) 入 新 設(shè) 備 15 22 第 5年 購(gòu) 入 新 設(shè) 備 15第 6年 購(gòu) 入 新 設(shè) 備 第 1年 第 2年 第 3年 第 4年 第 5年購(gòu) 買 費(fèi) 11 12 13 14 14機(jī) 器 役 齡 0 1 1 2 2 3 3 4 4 5維 修 費(fèi) 5 6 8 11 18殘 值 4 3 2 1 0 v1 v2 v3 v4 v5 v61219 28 40 59表 示 ， 第 1年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 2-6年 年 初 的 費(fèi) 用 。 v1 v2 v3

63、v4 v5 v61219 28 40 5920 29 41表 示 ， 第 2年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 3-6年 年 初 的 費(fèi) 用 。13 v1 v2 v3 v4 v5 v61219 28 40 5920 29 41表 示 ， 第 3年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 4-6年 年 初 的 費(fèi) 用 。14 21 3013 v1 v2 v3 v4 v5 v61219 28 40 592013 29 41表 示 ， 第 4年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 5-6年 年 初 的 費(fèi) 用 。14 21 3015 22

64、v1 v2 v3 v4 v5 v61219 28 40 592013 29 41表 示 ， 第 5年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 6年 年 初 的 費(fèi) 用 。14 21 3015 2215 v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) (12， 2) v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0，

65、s) (12， 2) (19， 3) v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) (12， 2) (19， 3) (49， 3) v1 v2 v3 v4 v5 v61219 28 40 592013 29 41表 示 ， 第 2年 年 初 購(gòu) 進(jìn) 一 臺(tái) 新 設(shè) 備 ， 使 用 到 第 3-6年 年 初 的 費(fèi) 用 。14 21 3015 2215 第 十 一 章 圖 與 網(wǎng) 絡(luò) 分 析11.1 引 言11.2 圖 與 網(wǎng) 絡(luò) 的 基 本 概 念11.3 最 短 路 問 題11.4 最 小 生 成 樹 問 題 11

66、.4 最 小 生 成 樹 問 題 樹 是 圖 論 中 的 重 要 概 念 ， 所 謂 樹 就 是 一 個(gè) 無 圈 的 連 通 圖 。v1v2 v3 v 4v5v6 v7v8 v9 v1v2 v3 v5v8v7v6v4 v1v2v3 v4v5v7 v6 v8 v9(a) (b) (c) 11.4 最 小 生 成 樹 問 題 樹 是 圖 論 中 的 重 要 概 念 ， 所 謂 樹 就 是 一 個(gè) 無 圈 的 連 通 圖 。v1v2 v3 v 4v5v6 v7v8 v9 v1v2 v3 v5v8v7v6v4 v1v2v3 v4v5v7 v6 v8 v9(a) (b) (c)無圈 連通 11.4 最 小 生 成 樹 問 題 無 向 圖 G=(V,E)， 保 留 G的 所 有 點(diǎn) ， 而 刪 掉 部 分 G的 邊 或 者 保 留 部 分 G的 邊 ， 所 獲 得 的 圖 G， 稱 之 為 G的 生 成 子 圖 ; 11.4 最 小 生 成 樹 問 題 無 向 圖 G=(V,E)， 保 留 G的 所 有 點(diǎn) ， 而 刪 掉 部 分 G的 邊 或 者 保 留 部 分 G的 邊 ， 所 獲 得 的 圖