第九章图与网络 算法思路 若P=uvU是从到的最短路，则P=1…u…v必然为到v的最 短路（若(v吧）≠0，则W(P)<W(P).否则若P"为至v的最短路，W(Pm)<W(P), 则由P”和边叫，构成一条至的长度小于P的路径这与P为至巴的最短路 矛盾.如图917所示，假定1吃路4是防至4的最短路，则物2一定是至吃的最 短路，这是因为，货间如果还有更短的路，如吃，则防购必为至4间的比 24更短的路，这与假设矛盾。 图917 因此得出寻找指定两点间最短路的方法是：由起点出发，逐步比较到附近各点所有可 能路的长短，从而求出从起点到其它各点的最短路线及其长度先给图G的每个顶点记一 个数（称为标号）临时标号（简称T标号）或者固定标号（简称P标号）.T标号表示从起点 到这一点的最短路长度的上界，P标号则是从起点到这一点的最短路长.每一步把某个点 的T标号改变为P标号，已得P标号的点不再改变其标号，这样，一且终点得到P标 号算法停止 算法步骤 用表示图中两点与巧之间的距高，若，与吗之间没有连线，令=+，（在 实际计算中，可用任一足够大的数代替).显然可令图中每个顶点：=0. 第一步：给起点标上固定的标号P()=0,并打上“*”号.给其它各点标上临时 标号，如起点到该点有边直接相连，就标T(心)=，否则T()=+∞.在编制计算机程 序时，也可以把其它各点都标上T标号为T)=+,0=2,3,n).并在T标号后面 注明从那一点来 第二步：在所有T标号中选取最小的，将其改为P标号（钉 ),并重新计算 有T标号的其它各点的T标号.计算的方法是：设顶点是刚得到P标号的点.把与顶 点有边直接相连而又属于T标号的各顶点的标号，改为下列T标号： T(vj)=min{T(vj),P(vi)+wij} 第三步：重复第二步，直至所有的顶点得到P标号止.然后从各个顶点反向追踪到起 点，这样就可以找出最短路，从各个顶点的P标号可以看出起点到该点的最短距离 至此，我们求出起点至终点包括中间各个顶点的最短路及其长度. 例4.求图9-15中1至其它各点的最短路长度. 解用Dijkstra算法迭代过程如图9-18所示
6 ⑥✌⑦✌⑧⑩⑨✘❶✖❷✘❸ ❹✌❺✌❻✌❼: ❽ P = v1 . . . u . . . vvj ❉✂✞ v1 ✡ vj õ✭✂✮❹ø, ❾ P 0 = v1 . . . u . . . v ✍✂❿✻ v1 ✡ v õ✭ ✮❹ø (❽ w(vvj ) 6= 0, ❾ W(P 0 ) < W(P)). ➀✂❾❽ P 00 ✻ v1 ➁ v õ✭✂✮❹ø,W(P 00) < W(P), ❾ r P 00 ❘✙ vvj ➂✌➃❳✌➄ v1 ➁ vj õ✫✌✬✌➅✌s P õø✌➆, ➇✌➈ P ✻ v1 ➁ vj õ✭✌✮✟ø ➉✌➊. ✁✌✑ 9–17 ✒ ✢ , ➋✌✔ v1v2v3v4 ❉ v1 ➁ v4 õ✭✌✮✟ø, ❾ v1v2v3 ❳✌✔❉ v1 ➁ v3 õ✭ ✮✁ø. ➇ ❉✤➌✤✻ v1,v3 ✥✁✤➍✤➎▲✁û✮ õø, ✁ v1v5v3, ❾ v1v5v3v4 ✍ ✻ v1 ➁ v4 ✥✁õ➐➏ v1v2v3v4 û ✮ õø, ➇✌➈✌➋✝➉✌➊. ✑ 9–17 ➌✌➑②✌❇✌➒✌➓✌➔✌✔✣✌✠✌✥✭✌✮✟øõ✌✯✌✐✌❉: r✘→✌✠❇✌➣, ↔✌↕ ➏✘➙✡✌➛✌➜✗ ✠✒ ▲❄ ➝ø õ✫✂✮, ✞✂➞☞✂❇ ✞✂→✂✠✡✂❊✂❋✗ ✠❹õ✭✂✮✟ø✟÷✂➟❊✫✌✬. ➠✂➡✂✑ G õ✂➢✂❂✂➤✂✠✂➥❳ ❂✌✛ (● ✻✌➦✌➧) ➨✌➩➦✌➧ (➫✌● T ➦✌➧) ✪✌➭✖➯✔ ➦✌➧ (➫✌● P ➦✌➧).T ➦✌➧✌✜✌✢✌✞✌→✌✠ ✡➇✌❳✠✟õ✭✌✮✟ø✌✫✌✬õ✌❀✌➲,P ➦✌➧❾❉✌✞✌→✌✠✡➇✌❳✠✟õ✭✌✮✟ø✌✫. ➢ ❳✌↕✵✌➳❂✌✠ õ T ➦✌➧✌➵✌➸✌✻ P ➦✌➧, ➺✘② P ➦✌➧✟õ✌✠✈✌➻➵✌➸❊ ➦✌➧, ➇✌➼, ❳✌➽✌➾✠ vn ②✡ P ➦ ➧ , ❤✌✐✌➚✌➪. ❹✌❺✌➶✌➹: ❯ wij ✜✂✢✑◆✕✣✂✠ vi ➈ vj ❍ ✥❹õ✦✂✧, ❽ vi ➈ vj ❍ ✥✂➘✂▲✂➴÷, ➷ wij = +∞,(☎ ③✌④✌➬✌❤ ✕, ❄ ❯✌➮❳✌➱✌✃✌❐õ✌✛✌❒✌❮). ❰✌❿✌❄✌➷✌✑✖✕➢✌❂✌➤✌✠ wii = 0. Ï✌Ð✌➶: ➡ →✌✠ v1 ➦✌❀ ➯✔ õ✌➦✌➧ P(v1) = 0, Ñ✌Ò❀ “∗” ➧ . ➡❊✌❋✗ ✠✌➦✌❀➨✌➩ ➦✌➧, ✁→✌✠✡✌Ó✠✌▲✙✌Ô✌Õ✌Ö➴ , × ➦ T(vj ) = w1j , ➀✌❾ T(vj ) = +∞. ☎✌Ø✌Ù➬✌❤✌Ú✌Û Ü➩, Ý✌❄✌❅ ✵✌❊✌❋✗ ✠✌❈✌➦✌❀ T ➦✌➧✌✻ T(vj ) = +∞,(j = 2, 3, . . . , n). Ñ✌☎ T ➦✌➧①✌Þ ß✖à✞✌á❳ ✠✌â. Ï✌ã✌➶: ☎✌✒▲ T ➦✌➧ ✕✘★✌ä✌✭✌➅õ , ✾✌❊➵✌✻ P ➦✌➧ (Ò ❀ “*” ➧ ) , Ñ✌åü✌➬✌❤ ▲ T ➦✌➧✌æ❊✌❋✗ ✠✌æ T ➦✌➧. ➬✌❤✌æ✌✯✌✐✌❉: ✝✌➤✌✠ vi ❉✌ç②✡ P ➦✌➧✌æ✌✠. ✵➈ ➤ ✠ vi ▲✙✌Ô✌Õ✌Ö➴✌➞✱✌è✌s T ➦✌➧✌æ✗ ➤✌✠ vj æ✌➦✌➧, ➵✌✻✌é✌ê T ➦✌➧: T(vj ) = min{T(vj ), P(vi) + wij}. Ï✌ë✌➶: å✌ì✌í✌î✌↕, Ô➁✒ ▲✌æ✌➤✌✠②✡ P ➦✌➧✌➪. ❿✌①✞ ✗ ❂✌➤✌✠✌ï✖▼✘ð✌ñ✡→ ✠ , ➇✌➼✌×✌❄✌❅✌➓✌❇✌✭✌✮✟ø, ✞ ✗ ❂✌➤✌✠✌æ P ➦✌➧❄✌❅✌❆✌❇ →✌✠✡✌Ó✠✌æ✭✌✮✦✌✧. ➁➑ , ò■☞✌❇ →✌✠ v1 ➁➾ ✠ vn ó✌ô ✕✥✗ ❂✌➤✌✠✌æ✭✌✮✟ø✌➟❊✫✌✬. õ 4. ☞✌✑ 9–15 ✕ v1 ➁✌❊✌❋✗ ✠✌æ✭✌✮✟ø✌✫✌✬. ö : ❯ Dijkstra ❤✌✐✌÷✌❒✌ø✌Û✁✌✑ 9–18 ✒ ✢
59.2最短路问题 7 ① 为了方便起见，我们用k表示计算步骤，将上述每步计算所得信息汇集在一起，即得
§9.2 ù✌ú✌û✖ü✘ý 7 (a) (b) (c) (d) (e) (f) (g) ✑ 9–18 ✻✌þ✌✯✌ÿ✌→✁, ò■ ❯ k ✜✌✢✌➬✌❤↕✁✂, ✾ ❀✌❁✌➢↕➬✌❤✒✌②✁✄✁☎✝✆✁✞✤☎✌❳→ , ✟✌②
第九章图与网络 如下点算到铁 T(v;) k 0° +o +∞ 15 +0 +0 10 4 135 + 15 436 > 3 集而p)=0.P)=10,P)=11,Po）= 8,P(%)=15.P()=13,P() 35. 例5.求图9-19中m至w的最短路及其长度 图9-19 解我们仅列出点算到铁 T(v;) 5 U6 00 + + +oo + 11 21 十0 +0 +0∞ 21 A2 42 + +0 45 4 42 6 +oc 6 6* + 756 由铁知P)=1它由7么它由或场产形 若P()由产 必P)4,它由防产 若P()由%产 ,P()=6,它由
8 ⑥✌⑦✌⑧⑩⑨✘❶✖❷✘❸ ✁é✁✠✌❤✁✡✁☛. vj T(vj ) v1 v2 v3 v4 v5 v6 v7 k 1 0 ∗ +∞ +∞ +∞ +∞ +∞ +∞ 2 101 151 8 ∗ 1 +∞ +∞ +∞ 3 10∗ 1 114 +∞ 134 +∞ 4 11∗ 4 162 134 +∞ 5 162 13∗ 3,4 +∞ 6 15∗ 6 436 7 35∗ 5 ✞✌➞ P(v1) = 0,P(v2) = 10, P(v3) = 11,P(v4) = 8, P(v5) = 15, P(v6) = 13, P(v7) = 35. õ 5. ☞✌✑ 9–19 ✕ v1 ➁ v8 æ✭✌✮✟ø✌➟❊✫✌✬. ✑ 9–19 ö : ò■✌✇ê ❇ ✠✌❤✁✡✁☛: vj T(vj ) v1 v2 v3 v4 v5 v6 v7 v8 k 1 0 ∗ +∞ +∞ +∞ +∞ +∞ +∞ +∞ 2 1 ∗ 1 21 +∞ +∞ +∞ +∞ +∞ 3 2 ∗ 1 42 42 +∞ +∞ +∞ 4 4 ∗ 2 42 +∞ 103 +∞ 5 4 ∗ 2 64 84 +∞ 6 6 ∗ 4 75 +∞ 7 7 ∗ 5,6 116 8 10∗ 7 r☞✡✁☛✁✌:P(v8) = 10, ❋ r v7 ✴✁✍; P(v7) = 7, ❋ r v5 ✪ v6 ✴✁✍; ❽ P(v7) r v5 ✴ ✍ ,P(v5) = 4, ❋ r v2 ✴✁✍;P(v2) = 1. ❋ r v1 ✴✁✍; ❽ P(v7) r v6 ✴✁✍,P(v6) = 6, ❋ r
59.2最短路问 9 4产可P侧)=4它由产可：P)=1它由产可.故n至w的东短路有泛条 P=功257g; P登=tt2467g, 长度为10 这里还需指Dsa算求对意负赋也有，为图和对为图都适际.对对为图来讲将连接 22公e 顶点韵各用 都为(e),即w(,)=w(,)=w(e) 三直应用举例 例6.设备更新问题 某工广使际一种设备，赣年年初该厂需对该设备的更新最否作决策。概购置新设 备，就要支付一定的购置费： 越长，每年所需的维修费就越多，现在的向题是如何制定 使一长这种设备的震设备购置费和日设备维修费给赛费际 们以一以五年之内设 备更新的计划为例. 已知该设备在五年内购系的 乘如表琴所 表9-1 年12345 购c41111121213 还已知设备使际不合年数的维修费如表9-2所广： 表9-2 使际期年 (0,1(1,223(3,4(4,5 维修费： 61 5 6 811 18 书种区阳装他里华秀新春级 解 在这一方案下，度费际为59+25=84 采取另一方案，如在」 顶年和 五.年名 购进一长新设备，购置费为11+12+13=36，维修费为5+6牛5+65=27，宝年度费 际为36+27=63. 那如复制定使羚度费际在模的设备更新升刘呢？经以把这以向题转化为在短路向 题设丰络如图20
§9.2 ù✌ú✌û✖ü✘ý 9 v4 ✴✁✍;P(v4) = 4, ❋ r v2 ✴✁✍; P(v2) = 1, ❋ r v1 ✴✁✍. ✎ v1 ➁ v8 æ✭✌✮✟ø▲✌✣➄: P ∗ 1 = v1v2v5v7v8; P ∗ 2 = v1v2v4v6v7v8, ✫✌✬✻ 10. ➇✑✏✂➎✑✒✂➔✂❇,Dijkstra ❤✂✐✂✼✑✓✑✔✑✕✂✚✂▲◆▼✑ ❘✂❙◆▼✑❈✑✖✂❯. ✼✂❙◆▼✑â✑✗✾➴ Õ ➤✂✠✂æ✗✂✙✑✘✻✑✙◆▼◗➴✑✚✂æ✂▲◆▼✙, ✛❋✂■æ✂✚✂❈✂✻ w(e), ✟ w(vi , vj ) = w(vj , vi) = w(e). ❅ ❀✌✣✌❂þ ➺☞✜✁✢ àþ➇✌❳✠ . ✣❩✥✤✧✦✧★✧✩ õ 6. ✝✟ú✟û✟ü✟ý✟þ. ➳✹✤✺✝✪❯❳✝✫✝✁ú, ➢ t✤t✝✬Ó✺✝✒✼Ó ✝✁ú✤æ✁û✁ü➈✤➀✝✭❇✝✮✰✯. ❽✝✱✝✲ü✤✝ ú , ×✌✆✁✳✁✴✌❳✌✔æ✱✁✲✁✵; ❽✁✶✁✷✪ ❯✁✸✌✝✟ú, ❾✁✒✁✳✁✴✌❳✌✔æ✁✹✁✺✵ , ✝✟ú✪ ❯✌æt✛ ✻ ✫, ➢ t✂✒✑✒æ✑✹✑✺✵× ✻✂❦, ✄✂☎æ❹ý❹þ✂❉✁✑✼✂Ù✂✔✂❳❂❽✁✽t✌❍✿✾æ✂✝✟ú❹û✟ü✂➬✁❀, ✪✌❳✁❁✌➇✁✫✝✟ú✌æ “ü✌✝✟ú✱✁✲✁✵❘✁✸✌✝✟ú✁✹✁✺✵ ” ❂✵❯✭✌➅. ò■❅✌❳❂✁❃t✌❍❄✾✝ ú✟û✟ü✌æ✌➬✁❀✌✻, ❽ ➺✌Ó ✝✟ú☎❃ t❄✾✱✁❅æ✁❆✁❇✁✜ 9–1 ✒ ✢ :✜ 9–1 í i t 1 2 3 4 5 ✱❆ ci 11 11 12 12 13 ➎✖➺✌✌✝✟ú✪ ❯✈✁❈t✛✌æ✁✹✁✺✵ ✁✜ 9–2 ✒ ✢ : ✜ 9–2 ✪ ❯✁❉t (0,1] (1,2] (2,3] (3,4] (4,5] ✹✁✺✵ bi b1 b2 b3 b4 b5 5 6 8 11 18 ö : ❄✁❊✌★✌✩æ✌✝✟ú✟û✟ü✌✯✌✰❰✌❿❉✌❥✌❦✌æ. ✌✁, ➢ t ❈✱✁✲❳✁❁ü✌✝✟ú, ❾❊ ✱✁✲ ✵✻ 11 + 11 + 12 + 12 + 13 = 59, ➞✌➢t✁✳✁✴æ✁✹✁✺✵✻ 5, ❃ t✁❋➬✌✻ 5 × 5 = 25. ✒✌❅ ☎✌➇✌❳✯✌✰✌é, ❂✵❯✌✻ 59 + 25 = 84. ❽✁●ä✁❍✌❳✯✌✰, ✁✌☎✌í✌❳✌t, í✁■✌t❘í❃ t✌✗ ✱✁❏❳✁❁ü✌✝✟ú, ✱✁✲✁✵✻ 11 + 12 + 13 = 36, ✹✁✺✵✻ 5 + 6 + 5 + 6 + 5 = 27, ❃ t✁❂✵ ❯✌✻ 36 + 27 = 63. á✑❑, ✁✑✼✂Ù✂✔✑✪✂②✑❂✵❯✭✌➅æ✌✝✟ú❹û✟ü✌➬✑❀✁▲? ❄✂❅✵➇ ❂❹ý❹þ✑▼✑◆✂✻✭✌✮❹øý þ , ❖✁P ❖✘P✁◗✁❘✁✌✑ 9–20:
10 第九章权与网络 图9-20 每 以 每位 w(,巧)=短i 每备把 建里简将台工花 =+孺+++b- i=1,,5j=2,,6,i<j 度购以-台新每备，如用至短5 底如期诸把2由 成如花忠大适】 看案，在此图 呢学 建 条边到简路 膏潮a共可得点执是如的高模管于专状到 下满 度作直 备更新上 简作决路问题 T(vj) 0 + + + 3 16 221 301 411 9 22 30 41, 572 301 41 53 5 411 533.4 6 53. 作决路呢三条， 简把。 备 用 越53：之一条期P-146， 图短1,4 用藏以 的 点T作改输手宽越月维修若井发21需台】 设2,6，拟它其 40吃维0吨.处20吨，处70吨6处90同置 知边处置 量50吨，2处 吨公里作排 花了 点解能以
10 ⑥✌⑦✌⑧⑩⑨✘❶✖❷✘❸ ✑ 9–20 ✝✌➤✌✠ v1, . . . , v6 ✜✌✢✗✌t✌t✁✬,v6 Ö✁❙✌s✌í❃ t✁❚. ✙ (vi , vj ) ✜✌✢☎✌í i t✌t✁✬✱ ❅❳✁❁✝✟ú❳✌Ô✁✪❯✡í j t✌t✁✬ (✟✁✪❯✌þ j − i t). ➢ ➄✌✙æ✌✚ w(vi , vj ) ❯✖➺✌✁❱✌✳❄✁❲é✁❳✌➬✌❤: w(vi , vj ) = í i t ✝✟ú✱✁✲✁✵ +(j − i) t✁✏æ✌✝✟ú✁✹✁✺✵ = ci + (b1 + b2 + . . . + bj−i), (i = 1, . . . , 5; j = 2, . . . , 6,i < j). ✤✁,(v3, v6) ❉ í 3 t✤t✝✬✱✝❅❳✝❁ ü✤✝✁ú, ✪ ❯➁í 5 t✤t✝❨, ✳✝✴✱✝✲✝✵ 12, r s✁✒✁✪❯ 3 t, ✎ ✹✁✺✵✻ 5+6+8=19, s❉✙ (v3, v6) ❀✌æ✌✚ w(v3, v6) = 31. ❰✤❿, ✼ s➢ ❳✝✫✤❄➝✤æ✤✝✁ú✁û✁ü✤✯✤✰, ☎ ➑ ✑➐✕❈✤▲Ö✽✤æ❳✤➄✞ v1 ✡ v6 æø. ➇✌➼, Ù✌✔✌❳❂ ✭✁❩æ✌✝✟ú✟û✟ü✌➬✁❀✌æ✟ý✟þ× ÿ✁❆s✌➒✌☞ v1 ✡ v6 æ✭✌✮✟øý✟þ. ❯ Dijkstra ❤✌✐❄✌②✠✌❤✁✡✁☛✁é : vj T(vj ) v1 v2 v3 v4 v5 v6 k 1 0 ∗ +∞ +∞ +∞ +∞ +∞ 2 16∗ 1 221 301 411 591 3 22∗ 1 301 411 572 4 30∗ 1 411 533 5 41∗ 1 533,4 6 53∗ 3,4 ✭✌✮✟ø▲✌✣➄, ❳✌➄❉ P ∗ 1 = v1v3v6, ✟✌í 1,3 t✁✬✌✗✱✁✲❳✁❁ü✌✝✟ú, ❃ t æ ❂✵❯ ✻ 53; ❍✌❳✌➄❉ P ∗ 2 = v1v4v6, ✟✌í 1,4 t✁✬✌✗✱✁✲❳✁❁ü✌✝✟ú, ❃ t æ ❂✵❯✌✻ 53. õ 7. ★✁❬ý✟þ. ▲✑❭✂❂✂✲✂✳✂✴✂✟:v1, v2, . . . , v6, ❪✑❋✑❖✂❳✲✂✳✸✂✹✂✺, ✗ ✠✂✥✂æ✦✂✧✁✂✑ 9-21 ✒ ✢ . ý ✲✌✳✸✌✹✌✺✽✌✝☎✁❫❂✌✠, ❄✁✪✌✭✌❐✠✁❴✦✌✧✻✭✌➅? ❽ ➺✌ v1 ❵ ✲✌✳✌✴✁❛ 50 ❜,v2 ❵ 40 ❜,v3 ❵ 60 ❜,v4 ❵ 20 ❜, v5 ❵ 70 ❜,v6 ❵ 90 ❜, ý✌✲✌✳✸✌✹✌✺✽✌✝☎✁❫❂✌✠, ❝ ➝ ❂ ❜✌♦✁✏✛ ✭✌➅?