资源描述
1 2.解 决 办 法 方 法 一 ： 每 次 以 一 个 顶 点 为 源 点 ， 重 复 执 行Dijkstra算 法 n次 T(n)=O(n) 方 法 二 ： 弗 洛 伊 德 (Floyd)算 法 2 求 最 短 路 径 步 骤初 始 时 设 置 一 个 n阶 方 阵 ， 令 其 对 角 线 元 素 为 0， 若 存 在 弧 ， 则 对 应 元 素 为 权 值 ； 否 则为 逐 步 试 着 在 原 直 接 路 径 中 增 加 中 间 顶 点 ， 若 加入 中 间 点 后 路 径 变 短 ， 则 修 改 之 ； 否 则 ， 维 持原 值所 有 顶 点 试 探 完 毕 ， 算 法 结 束3. Floyd算 法 思 想 ： 逐 个 顶 点 试 探 法 从 图 的 带 权 邻 接 矩 阵 G.arcs出 发 ， 假 设 求 顶 点Vi到 Vj的 最 短 路 径 。 如 果 从 Vi到 Vj有 弧 ， 则 从 Vi到 Vj存 在 一 条 长 度 为 G.arcsij的 路 径 ， 但 该 路径 是 否 一 定 是 最 短 路 径 ， 还 需 要 进 行 n次 试 探 。 1.第 一 次 ， 判 别 （ Vi, V0 ） 和 （ V0， Vj ） ， 即 判 别(Vi, V0 , Vj） 是 否 存 在 ， 若 存 在 ， 则 比 较 （ Vi, Vj ） 和(Vi, V0 , Vj） 的 长 度 ， 取 长 度 较 短 的 为 从 Vi到 Vj的 中 间顶 点 序 号 不 大 于 0的 最 短 路 径 。 2. 第 二 次 ， 再 加 一 个 顶 点 V1， 如 果 (Vi, , V1） 和 (V1, , Vj） 分 别 是 当 前 找 到 的 中 间 顶 点 序 号 不大 于 0的 最 短 路 径 ， 那 么 (Vi, , V1, , Vj ） 就 有可 能 是 从 Vi到 Vj的 中 间 顶 点 序 号 不 大 于 1的 最 短 路径 。 将 它 和 已 经 得 到 的 从 Vi到 Vj之 间 顶 点 序 号 不 大于 0的 最 短 路 径 相 比 较 ， 取 较 短 者 为 从 Vi到 Vj的 中间 顶 点 序 号 不 大 于 1的 最 短 路 径 。 3. 第 三 次 ， 再 加 一 个 顶 点 V2， 继 续 进 行 试 探 。 V2 V3V0 V11 23 45689 0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 888 8D(-1) = D(-1)为 有 向 网 的 邻 接 矩 阵 第 一 步 :以 D(-1)为 基 础 ， 以 V0为 中 间 顶 点 ， 求 从 Vi到Vj的 最 短 路 径 。 该 路 径 或 者 为 从 Vi到 Vj的 边 , 或 者 为(Vi,V0)+(V0,Vj) 。 D (0) ij = minD(-1) ij, D(-1) i0+D(-1) 0j4 70) = D(0) ij 为 从 Vi到 Vj的 的 最 短 路 径 长 度 . V2 V3V0 V11 23 45689 以 D(0)为 基 础 ， 以 V1为 中 间 顶 点 ， 求 从 Vi,到 Vj的 最 短路 径 。 该 路 径 或 者 为 从 Vi到 Vj的 边 , 或 者 为 从 Vi开 始 通过 V0或 V1到 达 Vj的 最 短 路 径 。 D(1) ij = minD(0) ij, D(0) i1+D(0) 1j0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 888 8A(-1) = 4 7D(0) 10 36(1) V2 V3V0 V11 23 45689 以 D(1)为 基 础 ， 以 V2为 中 间 顶 点 ， 求 从 Vi,到 Vj的 最 短路 径 。 或 者 为 从 Vi到 Vj的 边 , 或 者 为 从 Vi开 始 通 过V0,V1, V2到 达 Vj的 最 短 路 径 。 D(2) ij = minD(1) ij, D(1) i2+D(1) 2j0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 888 8A(-1) = 4 7(0) 10 36D(1) 2 12 9 0 0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 888 8A(-1) = 4 7(0) 10 36(1) D2 12 9 03 =V2 V3V0 V11 23 45689 以 D(2)为 基 础 ， 以 V3为 中 间 顶 点 ， 求 从 Vi,到 Vj的 最 短路 径 。 或 者 为 从 Vi到 Vj的 边 , 或 者 为 从 Vi开 始 通 过V0,V1, V2,V3到 达 Vj的 最 短 路 径 。 D (3) ij = minD(2) ij, D(2) i3+D(2) 3j 9 1 8 D(3) ij 即 为 从 Vi到 Vj的 最 短 路 径 长 度 . 9 A C B2643 11 0 4 116 0 23 0初 始 ： 路 径 ： AB ACBA BCCA0 4 66 0 23 7 0加 入 B： 路 径 ： AB ABCBA BCCA CAB0 4 116 0 23 7 0加 入 A： 路 径 ： AB ACBA BCCA CAB0 4 65 0 23 7 0加 入 C： 路 径 ： AB ABCBCA BC CA CAB 例 题 ： 10 例 A C B2643 11 初 始 ： 0 4 116 0 23 0length= 0 1 12 0 23 0 0path=加 入 A： 0 4 116 0 23 7 0length= 0 1 12 0 23 1 0path=加 入 B： 0 4 66 0 23 7 0length= 0 1 22 0 23 1 0path=加 入 C： 0 4 65 0 23 7 0length= 0 1 23 0 23 1 0path= 11 论 点 ： A(-1) ij是 从 顶 点 vi 到 vj , 中 间 顶 点 是 v1的 最 短 路 径 的 长 度 ,A(k) ij是 从 顶 点 vi 到 vj , 中 间 顶 点 的 序 号 不 大 于 k的 最 短 路 径 的 长 度 , A(n-1)ij是 从 顶 点 vi 到 vj 的 最 短 路 径 长 度 。证 明 ： 归 纳 证 明 ， 始 归 纳 于 s (上 角 标 );(1) 归 纳 基 础 ： 当 s=-1 时 ， A(-1) ij= Edgeij, vi 到 vj , 不 经 过 任 何 顶 点 的 边 ， 是 最 短 路 径 。(2)归 纳 假 设 ： 当 sk时 ， A(s) ij是 从 顶 点 vi 到 vj , 中 间 顶 点 的 序 号 不 大 于 s的 最 短 路 径 的 长 度 ;(3)当 s=k时 ， 12 i jkA(k-1) ik A(k-1) kjA(k-1) ij 13 图 用 邻 接 矩 阵 存 储 edge 存 放 最 短 路 径 长 度 pathij是 从 Vi到 Vj的 最 短 路 径 上 Vj前 一 顶 点 序 号5.算 法 实 现void floyd ( ) for ( int i = 0; i n; i+ ) /矩阵dist与path初始化 for ( int j = 0; j n; j+ ) /置A(-1) distij = Edgeij; pathij = -1; / 初始不经过任何顶点 for ( int k = 0; k n; k+ ) /产生dist(k)及path(k) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if (distik + distkj distij ) distij = distik + distkj; pathij = k; /缩短路径, 绕过 k 到 j / floyd 14 6.算 法 分 析 ： 设 最 内 层 循 环 体 为 基 本 操 作 ， 算 法 有 三 层 循 环 ，每 层 循 环 n次 ， 所 以 T(n)=O(n3) 15 A(-1) A(0) A(1) A(2) A(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1) Path(0) Path(1) Path(2) Path(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0 3 0 2 0 3 0 16 A(-1) A(0) A(1) A(2) A(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1) Path(0) Path(1) Path(2) Path(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0 3 0 2 0 3 0
展开阅读全文