图的最短路径及应用

图 的 最 短 路 径 及 应 用(1) 最 小 生 成 树(2) 最 短 路 径 算 法(3) 深 入 应 用 wzl 2013-10-29 图 的 最 小 生 成 树 图 的 最 小 生 成 树 主 要 两 种 方 法 ： 顶 点 遍 历 （ 1） prim算 法 图 的 存 储 矩 阵 、 深 搜 算 法 、 集 合 运 算 （ 2） kruskal算 法 边 集 数 组 存 储 、 贪 心 算 法 、 集 合 运 算 prim算 法 的 要 点 是 ：（ 1） 设 有 n个 顶 点 的 连 通 网 ： G=（ V， E） ， T=（ U， TE） 是 G的 最 小 生 成 树 其 中 U是 顶 点 集 TE是 T的 边 集 U、 TE开 始 值 为 空 （ 2） 算 法 如 下 ：Procedure Prim(GA,CT); beginfor I:=1 to n-1 do 给 CT赋 初 值 ， 对 应 第 0次 的 LW值 CTI.from :=1 ; ctI.end: =I+1 ; ctI.w:=GA1, i+1 ;for k:=1 to n-1 do 进 行 n-1次 循 环 ， 求 出 最 小 生 成 树 的 第 K条 边 min:=maxint ; m:=k ; for j:=k to n-1 do if ctj.w min then min:=ctj.w ; m:=j; if m k then ctk 与 ctm 的 交 换 将 最 短 边 调 到 第 K单 元 j:=ctk.end; 将 新 的 并 入 T中 顶 点 给 J for I:=k+1 to n-1 do 修 改 LW中 的 有 关 边 d:=ctI.end ; w:=GAj, d ; IF WCTI.W then CTi. w:=w; CTi.from:=j ; End; Kruskal 算 法 （ 贪 心 算 法 ） 算 法 ：Procedure kruskal ( GE,C ) ; begin for i:=1 to n do si:= i ; 初 始 化 顶 点 集 合 i:=1 ; j:=1 i 表 示 边 数 ， j 表 示 数 组 GE的 下 标 while i= n-1 do (1) for k:=1 to n do 搜 索 顶 点 begin if GEJ.fr in sk then m1:=k ; if GEJ.ed in sk then m2:=k ; end ; 记 录 第 j条 边 的 两 个 端 点 的 集 合 序 号 (2) if m1 m2 then 生 成 树 的 一 条 边 being ci:=j ; 保 存 选 取 的 第 i条 边 ,j 是 GE数 组 的 下 标 i:=i+1 ; sm1:=sm1+sm2 ; sm2:= ; end; (3) j:=j+1 ; end ; 运 行 该 程 序 后 ， C数 组 的 值 为 ： 1 2 3 4 5 所 以 最 小 生 成 树 由 GE数 组 中 的 1， 2， 3， 5， 7 边 组 成 。1 2 3 5 7 图 的 最 短 路 径 （ 9） 标 号 法 标 号 法 是 一 种 非 常 直 观 的 求 最 短 路 径 的 算 法 ， 可以 用 一 个 数 轴 简 单 地 表 示 这 种 算 法 ： 以 A点 为 0点 ， 展 开 与 其 相 邻 的 点 ， 并 在 数 轴 中 标出 。 因 为 C点 离 起 点 A最 近 ， 因 此 可 以 断 定 C点 一 定 是 由 A直 接 到C点 这 条 路 径 是 最 短 的 （ 因 为 A、 C两 点 间 没 有 其 它 的 点 ， 所 以C点 可 以 确 定 是 由 A点 直 接 到 达 为 最 短 路 径 ） 。 因 而 就 可 以 以已 确 定 的 C点 为 当 前 展 开 点 ， 展 开 与 C点 想 连 的 所 有 点 A、 B、D、 E。 由 数 轴 可 见 ， A与 A点 相 比 ， A点 离 原 点 近 ， 因 而 保 留 A点 ，删 除 A点 ， 相 应 的 ， B、 B点 保 留 B点 ， D、 D保 留 D， E、 E 保 留 E， 得 到 下 图 ： 例 题 1、 特 快 专 递 加 国 是 个 小 国 ， 仅 有 n个 城 市 ( 1n40)。 奥 维 尔 负责 这 个 国 家 的 特 快 专 递 ， 他 有 一 辆 汽 车 沿 途 他 要 到 各个 城 市 去 送 ems信 件 ， 各 城 市 之 间 的 路 程 s ( 0s1000) 是 已 知 的 ， 且 A城 市 到 B城 市 与 B城 市 到 A城 市 的 路 程 大多 不 同 。 为 了 提 高 效 率 ， 他 从 快 递 公 司 出 发 到 每 个 城市 一 次 ， 然 后 返 回 快 递 公 司 所 在 城 市 ， 假 设 快 递 公 司所 在 的 城 市 为 1， 他 不 知 道 选 择 什 么 样 的 路 线 才 能 使 所走 的 路 程 最 短 。 请 你 帮 助 他 选 择 一 条 最 短 的 路 。 输 入 ： 城 市 数 n 和 各 城 市 之 间 的 路 程 （ 均 是 整 数 ）输 出 ： 最 短 的 路 径样 例 ： salesman.in30 2 11 0 22 1 0salesman.out 3 算 法 ：求 最 短 路 径 算 法 ， 所要 注 意 的 问 题 ：他 需 要 返 回 到 初 始 的城 市 Program salesma;Var g:array1.40,1.40 of integer; a:array1.40 of integer; v:array1.40 of boolean; n,i,j,q:integer; s,t,min:longint;Procedure try(p:integer); var i:integer; begin if q=n+1 then begin if s+gp,1min then min:=s+gp,1; exit; end; for i:=2 to n do if not(vi) then begin inc(s,gp,i);vi:=true;inc(q); if smin then try(i); dec(s,gp,i); vi:=false;dec(q); end; end;Procedure work; var i,j,k,p,l:integer; v:array1.40 of boolean; begin fillchar(v,sizeof(v),false); l:=1; min:=0; for i:=2 to n do begin k:=2; while vk do inc(k); p:=k; for j:=p+1 to n do if not(vj) and (gl,jgl,k) then k:=j; inc(min,gl,k); l:=k;vl:=true; end; inc(min,gl,1); end; begin assign(input,salesma.in);reset(input); assign(output,salesma.out);rewrite(output); read(n); for i:=1 to n do for j:=1 to n do read(gi,j); s:=0; q:=2;work; try(1); writeln(min); close(input);close(output);end. 方 法 2Program ksd; var a:array1.50,1.50 of longint; n,i,j,min:longint; f:array1.50 of boolean;Procedure go(i,s,sum:longint); var ii:longint; begin if s=n then begin if sum+ai,1=min then exit; For ii := 1 to n do if fii=false then begin fii:=true; go(ii,s+1,sum+ai,ii); fii:=false; end;end;begin assign(input,salesma.in); assign(output,salesma.out); reset(input); rewrite(output); readln(n); for i := 1 to n do for j := 1 to n do read(ai,j); min:=maxlongint; f1:=true; go(1,1,0); writeln(min); close(input); close(output); end. 例 题 2、 深 度 优 先 遍 历 算 法 优 化 输 入 n (1=n=2,000,000,000),输 出 该 数 据 的 所 有形 式 不 同 的 因 式 分 解 。 样 例 ： 12=12 12=6*2 12=4*3 12=3*4 12=3*2*2 12=2*6 12=2*3*2 12=2*2*3 算 法 1： 减 少 数 据 范 围 或 运 算 次 数利 用 递 归 算 法 ： 穷 举 2N之 间 的 所 有 整 数 ， 若 该 数 是 N的 约 数 ， 则递 归 对 该 数 进 行 分 解 ， 直 到 变 为 1 程 序 段 代 码 ： procedure solve ( n:integer ) ; var i:integer ; begin if n=1 then inc(total) else for i:=2 to n do if n mod i=0 then solve(n div i) end; 算 法 2： 改 进 方 法 ： 首 先 将 n的 所 有 因 子 数 按 从 小 到 大 的 顺序 ， 存 储 在 一 个 数 组 内 。 这 样 在 每 一 层 递 归 时 只 要 穷 举 当 前 待 分 解 的 数 就可 以 了 ， 由 于 该 数 是 N的 因 子 ， 所 以 它 的 因 子 也 是 N的 因 子 。 Procedure solve(k:longint); var i, j, temp:longint; begin if k=0 then inc(total) else for i:=k downto 1 do if fk mod fi=0 then if fk=fi then inc(total) else begin temp:=fk div fi; j:=k-1; while tempfj do dec(j); solve(j) end end; begin read(n); s:=0; i:=2; while i*i=n do begin if n mod i=0 then begin inc(s); fs:=i; f-s:=n div i end; i:=i+1 end; if (i-1)*(i-1)n then j:=-s else j:=-s+1; for i:=j to -1 do begin inc(s); fs:=fi； end; inc(s); fs:=n; total:=0; solve(s); writeln(total); end. 例 题 3、 n个 士 兵 排 列 问 题 有 n个 士 兵 （ 1n26） ， 编 号 依 次 为 A、 B、C， 队 列 训 练 时 ， 指 挥 官 要 把 一 些 士 兵 从 高 到 矮 依次 排 成 一 行 。 但 现 在 指 挥 官 不 能 直 接 获 得 每 个 人 的 身 高信 息 ， 只 能 获 得 “ p1比 p2高 ” 这 样 的 比 较 结 果 （ p1，p2 A， ， Z） ， 记 为 p1p2。根 据 这 些 关 系 ， 求 出 排 队 方 案 。 例 ： AB， BD， FD （ 没 有 循 环 ， 可 以 用 拓 扑 排 序 ）方 案 ： AFBD、 FABD、 ABFD 拓 扑 排 序 应 用 Program tppv; n个 士 兵 排 队 const maxn=100;var map:array1.maxn,1.maxn of byte; into:array1.maxn of byte; n,i,j,k:byte;Procedure init; var i,j:integer;begin readln(n); fillchar(map,sizeof(map),0); fillchar(into,sizeof(into),0); while not(seekeof(fp) do begin readln(fp,i,j); mapi,j=1 ; inc(intoj); end; close(fp);end; begin init; for i:=1 to n do begin j:=1; while (j=n)and(intoj0) do inc(j); write(j, ); intoj:=255; for k:=1 to n do if mapj,k=1 then dec(intok); end;end. 例 题 4、 雇 佣 计 划 ： 一 个 工 厂 管 理 员 需 要 确 定 每 个 月 需 要 的 工 人 ， 他 知 道每 个 月 需 要 的 最 少 工 人 数 。 当 他 雇 佣 或 解 雇 一 个 工 人 时 ，需 要 一 些 额 外 支 出 。 一 旦 一 个 工 人 被 雇 用 ， 即 使 他 不 工 作 ，他 也 将 得 到 工 资 ， 同 时 该 管 理 员 知 道 雇 佣 一 个 工 人 的 费 用 、解 雇 一 个 工 人 的 费 用 和 一 个 工 人 的 工 资 。 他 正 在 考 虑 为 了把 项 目 的 费 用 控 制 在 最 低 ， 他 将 每 月 雇 佣 或 解 雇 多 少 人 。 输 入 ： 三 行 ， 第 一 行 为 月 数 ， 第 二 行 含 有 雇 佣 一 个 工 人费 用 、 一 个 工 人 工 资 、 解 雇 一 个 工 人 费 用 （ =100） ， 第三 行 含 n个 数 ， 分 别 表 示 每 个 月 最 少 需 要 的 工 人 数（ minI则 需 解 雇 一 些 人 ， 解 雇 多 少 是 问 题 根 本 ： 本 例 题 中 ， 第 1个 月 10人 ： cost=cost+4*10+5*10=90第 2个 月 解 雇 1人 cost=cost+f(now-min2)+d*min2=141第 3个 月 需 11人 cost=cost+h*(min3-now)+d*min3=204这 不 是 最 佳 方 案 ， 此 时 可 以 采 取 第 2个 月 不 解 雇 的 策 略 ：4*10+5*10+5*10+（ 4*1+5*11） =199 。 采 取 贪 心 策 略 ： 尽 可 能 少 的 解 雇 工 人 ， 并 且 在 工 资 支 出 合 理 的 前 提 下 ，尽 可 能 使 现 有 工 人 数 维 持 在 一 个 最 长 时 间 内 ， 以 减 少 雇 佣和 解 雇 的 额 外 支 出 。 实 现 方 法 ： 在 minIminn间 按 最 少 需 要 人 数 递 增 的 顺 序 ，将 月 份 排 列 成 y1,y2,。program p3_5 (input,output);Var n,a,b,c,i,j,max,min:integer; s: extended; g: array0.100 of integer;begin readln(n); readln(a,b,c); for i:=1 to n do read(gi); max:=(a+c) div b+1; for i:=1 to n do begin if gi=gi-1 then s:=s+gi*b+(gi-gi-1)*a; if gimin) and (j=n) then min:=gj; if mingi then begin s:=s+(gi-min)*c; gi:=min; gi+1:=gi; end else begin gi:=gi-1; if gi+1gi then gi+1:=gi; end; s:=s+gi*b; end; end; writeln(s:0:0); end. 机 场 高 速 铁 路飞 机 航 线 注 意 ： 图 中 并 没 有标 出 所 有 的 铁 路 与 航线 。