第九章图与网络 图论是运筹学中发展十分迅速，应用也比较广泛的一个分支，它的理论和方法在许多 领域诸如物理学.化学.电子计算机信息论.控制论.社会科学以及经济管理中都得到 了广泛的应用.图论之所以能够迅速发展和得到广泛的应用，是因为它同其它分支相比较 具有对实际问题描述的直观性以及易于将一些复杂的问题分解或转化成为更有效的方法 求解等特点 图论的内容十分丰富，涉及的面也比较广.本书所介绍的是图与网络理论和算法的基 本内容，是实际生活.生产和科研工作中经常用到的.我们首先学习一些有关图与网络的 基本概念，再研究几种标准的网络模型，即最短路问题和最小生成数问题。关于最大流问 题、最小费用流问题及最小费用最大流的应用将在第十章网络流问题中介绍. S9.1图与网络的基本概念 一 人们在日常的生活和工作中，经常见到各种各样的图，如公路或铁路交通图，通讯线 路图等运筹学中所研究的图”是一个抽象的数学概念为了能够理解这个概念，我们先 讨论几个例子 例1.数学家欧拉1736年发表了图论方面的第一篇论文即著名的哥尼斯堡七桥 题十八世纪东欧有个叫哥尼斯巴堡的城镇，小镇风景独特，有条普雷格尔河从镇中穿流 而过.该河中有两个岛，河上有七座桥把河的两岸和河中的两个岛连接起来.如图9-1所 示 图9-1 图92 当时该城的居民热衷于这样一个问题：一个人能否从某地出发一次把七座桥都走过 一遍，最后回到原地而不重复.这个问题的答案是否定的.欧拉用A,B,C,D四个点分别 表示河两岸和可中的两个岛.每座桥用连接相应两点的一条边表示.把图91化为图9-2 的一笔画问题。从而证明了这是不可能的，因为图9-2中的每个点都只与奇数条边相连 不可能不重复地一笔画出. 例2.图9-3所示是我国某地区的铁路交通示意图，反映了该地区铁路上各车站间相 对位置。这里点代表车站，用点和点之间的连线代表两车站之间的铁路线 例3.若发点1和s2可运送货物到收点t1,t2和，我们用点表示发点或收点，带箭 头的边表示货物发送方向，可以得到图94 1
✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠✡☛✡☞✡✌✡✍✏✎✒✑✡✓✡✔✡✕✡✖✡✗, ✘✡✙✡✚✏✛✒✜✡✢✡✣✡✤✡✥✡✦✕✡✧. ★✡✤✡✩✠✡✪✡✫✡✬✡✭✡✮✡✯ ✰✡✱, ✲✡✳✡✴✡✩✍ . ✵ ✍ . ✶✒✷✡✸✡✹✡✺. ✻✡✼✠ . ✽✡✾✠ . ✿✡❀✡❁✍✡❂✡❃✡❄✡❅✡❆✩ ✎❈❇✡❉❋❊ ●✢✡✣✡✤✡✘✡✙. ✟✡✠✡❍✡■✡❂✡❏✡❑✡✖✡✗✡✑✡✓✡✪✡❉✡❊✢✡✣✡✤✡✘✡✙, ☛✡▲✡▼★✡◆✡❖✡★✕✡✧✡P ✛✒✜ ◗✡❘✡❙✡❚✡❯✡❱✡❲✡❳✡❨✤✡❩✡❬✡❭❂✡❃✡❪✡❫✡❴✥✡❵✡❛✡❜✡✤❱✡❲✕✡❝✡❞✡❡✵✡❢▼✡❣❘✡❤✤✫✡✬ ✐❝✡❥✡❦✡❧. ✟✡✠✤✏♠✒♥✔✡✕✡♦✡♣, q❃ ✤✡r✡✚✏✛✒✜✡✢. s✡t■✡✉✡✈✤☛✡✟✡✇✏①✒②✩✠✡✪✹✬ ✤✡③ s✏♠✒♥, ☛❚✡❯✡④✡⑤. ④✡⑥✪❁✡⑦✡⑧✡⑨ ✎✒❄✡⑩✙❊ ✤. ❶✡❷✡❸✡❹✍✡❺✥✡❵❘✡❻✟✡✇❼①✒②✤ ③✡s✡❽✡❾, ❿✡⑦✡➀✡➁✡➂✡➃✡➄✡✤ ①✒②✡➅❋➆, ➇✡➈✡➉✡➊❱✡❲✪➈✡➋④ ❢❋➌❱❋❲. ❻❫➈✡➍✡➎❱ ❲✡➏ ➈✡➋✡➐✡✙✡➎❱✡❲❃ ➈✡➋✡➐✡✙✡➈✡➍✡➎✡✤✡✘✡✙❴✡✭✡➑✡✔✡➒✏①✒②➎ ❱✡❲ ✎✒✉✡✈. §9.1 ➓→➔→➣→↔→↕→➙→➛→➜→➝ ➞✡➟ ➠ ❷✭➢➡➤⑩✤④❋⑤✪⑧❋⑨ ✎ , ❄❋⑩❋➥❋❊❋➦➂ ➦❋➧✤ ✟ , ✳❋➨❋➊❞❋➩➊❋➫❋➭✟ , ➭❋➯❋➲ ➊ ✟✡❥. ☞✡✌✡✍✏✎✒■⑦✡➀✡✤ “✟ ” ☛ ✥✡✦✡➳✡➵✡✤✡➌✍❽✡❾. ▼●❏✡❑✩❝✡➸✦✡❽✡❾, ❶✡❷✡❹ ➺✠ ➁✡✦✡➻✡✷. ➼ 1. ➌ ✍❋➽❋➾❋➚ 1736 ➪ ✑❋➶● ✟❋✠❋✫r❋✤➑✥❋➹✠❋➘, ➇❋➴❋➷❋✤❋➬❋➮❋➱❋✃❋❐❋❒❱ ❲ . ✔✡❮✡❰✡Ï✡Ð✡➾❘✦✏Ñ✒➬✡➮❋➱✏Ò❈✃✡✤❋Ó❋Ô, ➋✡Ô✡Õ✡Ö✡×❦ , ❘✡Ø✡Ù✡Ú✡Û✡Ü✡Ý✡ÞÔ ✎✒ß➎ à✡á. â Ý ✎❘✡ã✦✡ä, Ý✡å✡❘❐✡æ✡❒✡çÝ ✤ã✡è✪Ý ✎✤ã ✦✡ä❋é✡ê✡ë❋ì. ✳ ✟ 9–1 ■ í . ✟ 9–1 ✟ 9–2 î❋ïâ❋Ó❋✤❋ð❼ñ❈ò❋ó❫❋➸❋➧✥❋✦❱❋❲: ✥❋✦➠❏❋ôÞ❋õ❋ö❋÷ ✑ ✥❋ø❋ç❋❐❋æ❋❒❇❋ùá ✥❋ú, ➈❋û❼ü ❊❋ýöà❋þ❋ÿ❛. ➸ ✦ ❱❋❲✤✁✁✂☛❋ô✁✄✤. ➾❋➚✙ A, B, C, D ☎❋✦❧❋✕✁✆ ➶íÝ✡ã✡è✪Ý ✎✤ã ✦✡ä, ✝✡æ✡❒✡✙✡é✡êP✘ ã❧ ✤✡✥Ø✟✞➶í . ç ✟ 9–1 ✵ ▼✡✟ 9–2 ✤❋✥✁✠✁✡❱❋❲. Þà✁☛✌☞● ➸❋☛þ✁✍❏ ✤, ▲❋▼❋✟ 9–2 ✎✤✁✝❋✦❧❋❇✁✎❋✇✁✏➌ Ø✁✞Pé, þ✟✍❏þ✡ÿ❛ ö✥✟✠✟✡÷ . ➼ 2. ✟ 9–3 ■í☛ ❶✟✑õ✡ö✟✒✤➩ ➊✡➫✡➭í✟✓✟ , ✔✟✕●â ö✟✒➩ ➊ å➦✟✖✟✗✟✘✡P ❙✟✙✟✚. ➸✟✛✡❧✟✜✡➶✟✖✟✗, ✙❧✡✪✡❧✡❍✟✘✤✡é✡➲✜✡➶ã✖✟✗✡❍✟✘✤➩ ➊✡➲. ➼ 3. ✢ ✑✡❧ s1 ✪ s2 ✍☞✟✣✟✤✴ ❊✟✥✡❧ t1,t2 ✪ t3, ❶✡❷✡✙❧✡➶í✑✡❧✡❞✟✥✡❧, ✦✟✧ ★ ✤✞➶í✤ ✴✑✟✣✡✫✪✩, ✍❂✡❉✡❊✡✟ 9-4. 1
2 第九章图与网络 图9-3 图9-4 从以上的例题中可以看出，我们所研究的图，指的是由若干个点和连接这些点的连线 所组成的图形.它不要求按比例尺绘制，其线段不代表真正的长度，点和线的位置具有随 意性它只注重反映点、线之间的关系 一个图G是指一个给定的集合V及其反映V中元素间关系的无序元素对的集合E 记为G=(化，E).V和E分别为图G的顶点集合和边的集合.图G的顶点集合与边集合 分别用V(G和E(G)表示 个图可用图形表示，用点表示V中的元素，用点与点之间的连线表示E中的元素 二无向图 设V是一个有n个顶点的非空集合，V={1,,》,E是一个有m条边的集 合，E={,2,6n，E中任一条边e是V的无序元素对(，)≠》则称V和E 这两个集合组成了一个无向图，记为无向图G=(V,E).如图95所示. 图9-5 三有向图 设顶点的非空集合V={1,2 h边的集合E=1,enE中任一条 边e是V的一个有序元素对(：，)i≠)，则称V和E组成了一个有向图，记为有向图 G-(VE).如图-6所示 图96
2 ✫✟✬✟✭✯✮✱✰✪✲✱✳ ✟ 9–3 ✟ 9–4 Þ❂ å ✤✡➻❲ ✎✍❂✟✴÷ , ❶✡❷■ ⑦✡➀✡✤✟ , ✵✡✤☛✪✶ ✢✟✷✡✦❧✡✪é✡ê➸ ❵ ❧ ✤✡é✡➲ ■✁✸❢❋✤✟✁✹. ★þ✁✺✐✁✻ ✛❈➻✁✼✁✽❋✾, ❖❋➲✁✾þ✜❋➶✁✿✁❀✤✁❁✁❂, ❧❋✪➲❋✤✙✁✚❋◗❋❘✁❃ ✓❭, ★ ✎✟❄ÿ ✔✟✕❧➏ ➲ ❍✟✘✤❻✟❅. ✥✡✦ ➟G ☛ ✵✡✥✡✦✟❆✄ ✤✟❇✟❈ V ❃ ❖✟✔✟✕ V ✎✱❉✟❊✟✘❻✟❅✤✟❋✟●❉✟❊❙ ✤✟❇✟❈ E, ❍▼ G = (V, E). V ✪ E ✕✟✆✡▼✡✟ G ✤✟■❧❇✟❈✪✞ ✤✟❇✟❈. ✟ G ✤✟■❧❇✟❈✇✞ ❇✟❈ ✕✟✆✙ V (G) ✪ E(G) ➶í . ✥✡✦✟✍ ✙✟✟✹✡➶í , ✙❧✡➶í V ✎✤❉✟❊, ✙❧✡✇✡❧✡❍✟✘✤✡é✡➲➶í E ✎✤❉✟❊. ❏ ❑▼▲▼◆ ❖ V ☛ ✥❋✦❘ n ✦✁■❧ ✤✁P✁◗✁❇✁❈,V = {v1, v2, . . . , vn}, E ☛ ✥❋✦❘ m Ø✁✞✤✁❇ ❈,E = {e1, e2, . . . , em},E ✎✱❘✥ Ø✟✞ e ☛ V ✤✟❋✟●❉✟❊❙ (vi , vj ) (i 6= j), ❙✟❚ V ✪ E ➸ã ✦✟❇✟❈✸ ❢ ●✥✡✦✟❋ ✩✒✟, ❍▼❋ ✩✒✟ G = (V, E). ✳ ✟ 9-5 ■í . ✟ 9–5 ❯ ❱▲▼◆ ❖ ■ ❧ ✤✟P✟◗✟❇✟❈ V = {v1, v2, . . . , vn}, ✞ ✤✟❇✟❈ E = {e1, e2, . . . , em}, E ✎✱❘✥ Ø ✞ e ☛ V ✤✡✥✡✦❘ ●❉✟❊❙ (vi , vj )(i 6= j), ❙✟❚ V ✪ E ✸ ❢ ●✥✡✦❘ ✩✒✟, ❍▼❘ ✩✒✟ G = (V, E). ✳ ✟ 9–6 ■í . ✟ 9–6
59.1图与网络的基本概念 3 四同构图 上面我们已经指出，图论中所研究的图，既然是反映对象之间的某种关系，所以它不 同于儿何学中或者函数论中的图.在这里，顶点的准确位置，顶点之间连线的长短曲直都 是无关紧要的，重要的是顶点之间相互连接的情祝.例如图97和9-8从结构上来说是 样的，称为同构图 图9-7 图9-8 又如图9-9和9-10也是同构的 图9-9 图9-10 由于同构图被认为是相同的，这就给我们在网络规划中建立网络模型带来很多方便， 在第十章中利用网络算法解运输问题时，就要用到同构图 五网络 如果图的边上带有数量指标（或称权），根据所研究的系统及所讨论问题的需要，其数 量指标可以表示距离.费用时间或流量等，这样的图称为网络。有时网络与图不加区别地 统称为图 六链、圈、路、回路 若G=(心，E)为给定的图，若G的某些顶点和边可排列成如下交错序列（心 Uik-1:eik 使边=(，+1）(s=1,2 k-1,则称这个交 错序列为一条连接：和的能。其中：和称为这条链的端点把这条链记为 …-,图9-5中2r是一条链 对起点和终点相重合的链称为圈.如图95中购助为一个圈 若链，。-中顶点都不相同，则称这条链为一条连接：和的路。图 g5中边2 4%是一条联接和%路.起点和终点重合称为回路。图95中，边的序 列124构成一个回路。 对无向图和有向图，链的概念是一致的.但对路和回路要求路和回路中边的方向一致
§9.1 ✮✱✰✪✲✱✳✪❲✱❳✟❨✟❩✟❬ 3 ❭ ❪▼❫◆ år❋❶❋❷✌❴❄ ✵ ÷ , ✟❋✠❼✎❈■⑦❋➀❋✤✟ , ❵✁❛☛ ✔✁✕❙ ➵ ❍✁✘✤õ ➂❻✁❅, ■❋❂ ★þ ◆❫➁✟❜✍✏✎✒❞✟❝✟❞➌ ✠❼✎✤ ✟ . ✭✡➸✟✛, ■ ❧ ✤✡➄✟❡✙✟✚, ■ ❧✡❍✟✘é✡➲✡✤✟❁✡➉✪❢✒❩❇ ☛ ❋❻✟❣✺ ✤, ÿ✟✺✤☛ ■ ❧✡❍✟✘✡P✟❤é✡ê✡✤✟✐✟❥. ➻✡✳✟ 9-7 ✪ 9-8 Þ✟❦✟❧✡åì✟♠☛ ✥ ➧ ✤, ❚ ▼ ◆❧✟ . ✟ 9–7 ✟ 9–8 ♥ ✳ ✟ 9–9 ✪ 9–10 ✚ ☛ ◆❧ ✤. ✟ 9–9 ✟ 9–10 ✶✒❫◆❧✟✟♦✟♣✡▼✡☛✡P◆✡✤, ➸✟q❆✡❶✡❷✭✏①✒②✟r✟s✏✎✉t✁✈✏①❈②❋➅✡➆✦✡ì✁✇✯✡✫✁①, ✭✡➑✡✔✡➒✏✎✱②✙ ①✒②✹✬✡❝✡☞✟③❱✡❲ï , q✺ ✙❊ ◆❧✟ . ④ ⑤▼⑥ ✳✟⑦✟ ✤✞✡å✦ ❘➌✟⑧✟✵✡➃ (❞❚✟⑨), ⑩✟❶■ ⑦✡➀✡✤❅✟❷❃✡■➺✠❱✡❲✤✟❸✺ , ❖✡➌ ⑧❹✵➃✍❂➶í❹❺❹❻. ➐✙. ï✘❞ ➎❹⑧❥ , ➸➧ ✤ ✟❚ ▼ ①② . ❘ï①②✇✟þ❹❼✒✆ö ❷❚ ▼✡✟. ❽ ❾ ❿➁➀▼❿➁➂▼❿➁➃➄➂ ✢ G = (V, E) ▼❆ ✄ ✤ ✟ , ✢ G ✤õ ❵✁■❧❋✪✞✍✁➅✁➆❢❋✳✁➇❋➫✁➈✁●➆ (vi1 , ei1 , vi2 , ei2 , vi3 , . . .,vik−1 , eik−1 ,vik ), ➉✞ eis = (vis , vis+1 ) (s = 1, 2, . . . , k − 1), ❙✁❚➸ ✦❋➫ ➈✁●➆▼✥ Øé❋ê vi1 ✪ vik ✤✁➊. ❖ ✎ vi1 ✪ vik ❚ ▼❋➸Ø ➊❋✤✁➋❧ . ç➸Ø ➊ ❍▼ vi1 vi2 . . . vik−1 vik , ✟ 9–5 ✎ v1v2v5v7 ☛ ✥ Ø ➊. ❙ ë ❧✡✪✟➌✡❧✡Pÿ ❈✡✤✟➊✟❚▼✟➍. ✳ ✟ 9-5 ✎ v1v2v4v3v1 ▼✥✡✦➍ . ✢✁➊ vi1 vi2 . . . vik−1 vik ✎■ ❧❋❇þP ◆, ❙✁❚➸Ø ➊ ▼✥ Øé❋ê vi1 ✪ vik ✤❋➊. ✟ 9–5 ✎✞ v1v2v4v6 ☛ ✥ Ø✟➎ê v1 ✪ v6 ➊. ë ❧✡✪✟➌✡❧ÿ ❈✟❚▼ ü✒➊. ✟ 9–5 ✎ , ✞ ✤✟● ➆ v1v2v4v3v1 ❧❢✡✥✡✦✏ü✒➊. ❙ ❋ ✩✟✪❘ ✩✟ , ➊✤❽❾ ☛ ✥❹➏✤. ➐ ❙ ➊ ✪ ü➊ ✺✐➊ ✪ ü➊ ✎✞ ✤✫✪✩✥✟➏
￥ 第九章图与网络 七连通图 若一个图中的任意两点间至少存在一条能，则称这个图为连通图.连通图中不存在任 何孤立的顶点，图95是连通图，如果把图中边9和10去掉，顶点？就称为孤立的顶 点，整个图也就不是一个连通图了 八欧拉图 在连通无向图G中，经过图G每条边一次且仅仅一次的链称为欧拉链 如果图G有一条起点与终点相同的欧拉链（闭链），则称该链为G的欧拉环游.若图 G含有一条欧拉环游，则称图G为欧拉图. 例如在图9-11(a)中，1242s4是一条欧拉链图9-11(b)是欧拉图，因为在图 G中存在欧拉环游即闭的欧拉链。 (a) 图9-11 九树和生成树 一个无圈的无向连通图G称为树，记为T=(Y,E).给定连通图G,若树T满足 风莲长EG盟称工为图G的生成损生农村为把原顶点以最小 一图中由于边的取法不同可以有很多生成树.如图9-13和图9-14就 是图9-12的生成树. 图9-12 图9-13 图9-14
4 ✫✟✬✟✭✯✮✱✰✪✲✱✳ ➑ ➒▼➓◆ ✢✡✥✡✦✟✏✎✤❘✓ã❧✟✘✟➔✟→✟➣✡✭✥ Ø ➊, ❙✟❚➸ ✦ ✟✡▼é✡➭✟ . é✡➭✟✏✎þ➣✡✭✟❘ ❜✁↔✈ ✤✁■❧ , ✟ 9–5 ☛é❋➭✟ , ✳✁⑦❋ç✟❼✎✞ e9 ✪ e10 ↕✁➙, ■ ❧ v7 q❚ ▼↔ ✈ ✤✁■ ❧ , ➛✡✦✟✚ qþ☛ ✥✡✦✡é✡➭✟● . ➜ ➝▼➞◆ ✭é✡➭✟❋ ✩✒✟ G ✎ , ❄á✟ G ✝ Ø✟✞✥✡ø✟➟✟➠✟➠✡✥✡ø✡✤✟➊, ❚ ▼➢➡✟➤✟➥. ✳✟⑦✟ G ❘✥ Ø ë ❧✡✇✟➌✡❧✡P◆✡✤➾✡➚➊ (➦✟➊), ❙✟❚✡â✟➊▼ G ✤➾✡➚✟➧✟➨. ✢ ✟ G ➩ ❘✥ Ø➾✡➚✟➧✟➨, ❙✟❚✟ G ▼➢➡✟➤➟. ➼✟➫ ✭✡✟ 9–11(a) ✎ ,v1v2v3v4v2v5v4 ☛ ✥ Ø➾✡➚➊. ✟ 9–11(b) ☛✡➾✡➚✡✟, ▲✡▼✡✭✡✟ G ✎✱➣✡✭✡➾✡➚✟➧✟➨➇✟➦✡✤➾✡➚➊. (a) (b) ✟ 9–11 ➭ ➯▼➲▼➳▼➵▼➯ ✥❋✦✁❋➍ ✤✁❋ ✩é❋➭✟ G ❚ ▼➺➸, ❍▼ T = (V, E). ❆ ✄é❋➭✟ G, ✢✁➻ T ➼✁➽ V (T) = V (G),E(T) ⊆ E(G), ❙✟❚ T ▼✡✟ G ✤➚➾✟➪➸ . ④ ❢✟➻▼✡❏ç ý✡✟å ■ ❧✡❂ ➈✡➋ ✞ ➌✡é✡ê✡ë✡ì. ✭ ◆✡✥✟✏✎✟✶✒❫✞ ✤✟➶✬þ ◆✍❂ ❘✇ ✯④ ❢✟➻. ✳ ✟ 9–13 ✪✡✟ 9–14 q ☛✡✟ 9–12 ✤④ ❢✟➻. ✟ 9–12 ✟ 9–13 ✟ 9–14
59.2最短路问题 5 S9.2最短路问题 一、最短路问题的数学模型 在网络图中顶点：与：可可以理解为空间位带或时间坐标.也可可以理解为其它意义 下的事件与活动：边上的权可理解为空间距离或时间间隔，也可以理解为活动的经费 能耗等.也就是说。网络最短路的实际意义是广泛的，可以是空间距离上的最短路。也可以 是时间概念上的“最短路”（总时间最少，或者是一系列活动的总经费或总能耗最少. 于是，网络图最短路题的数学模型为：给定图G-(化，E),V={,2,,n小，E {e1,e2,,em}.若图G的每条边e=(e,)都与一个非负实数w(e)=w(,）= 对应则称G为非负赋权图，简称网络，其中(e)称为e的权. 若P为G中至m的路，称 W(P)-∑ 为P的长度，其中E(P)表示P上边的集合 若P为G中至m的路，且满足 W(P*)=min{W(PP为G中1至n的路} 则称P为1至的最短路。 我们的问题就是在图G中如何寻找1至的最短路并求出其长度 最短路问题可以直接应用于解决生产实际，运输管理和工程建设问题，诸如各种管道 的铺设，线路安排设备更新问题等等.例如，现在要铺设从地点到地点2，，，”的 铁路线路。要求铁路必须沿图915所规定的道路铺设.设图中各边的权数表示两点间的 距离，要求选择从到2或，或4，，或的铁路长度最短的铺设方案.又例如，从 原料产地把原料送往各加工厂2,3，，7，如图916各边权数为对应的两点间距离， 要求从1将原料送往各工厂去距离最短的路。 图9-15 图9-16 从上述两个例子可以看出，问题都是要求从”到其它各点距离最短的路，称之为最 短路问题它们分别对应有向网络和无向网络的最短路问题。最短路问题是图论应用的基 本问题之 二、最短路问题的算法 求解最短路问题的算法很多，目前公认的最好算法是由E.W.Dijkstra于199年提出 的，它不仅求出到的最短路，最后所得到的实际上是从始点到各点的最短路
§9.2 ➹✟➘✟➴✪➷✱➬ 5 §9.2 ➮✃➱✃❐✃❒✃❮ ❰❿➁Ï▼Ð▼➂▼Ñ➄ÒÔÓ➄ÕÔÖ➄×➄Ø ✭✏①✒②✡✟✏✎, ■ ❧ vi ✇ vj ✍❂ ✩❝✡▼◗ ✘✙✟✚❞ï✘✟Ù➃, ✚ ✍❂ ✩❝✡▼❖✡★✓✟Ú ➇❋✤✁Û✁Ü✇⑤✁Ý; ✞ e å ✤✁⑨✍ ✩❝❋▼◗ ✘❺✁❻❞ï✘✁✘✁Þ, ✚ ✍❂ ✩❝❋▼⑤✁Ý✤❄ ➐, ❏✟ß✡❥. ✚ q✡☛♠, ①✒②➈✡➉✡➊✡✤❚✡❯✓✟Ú☛ ✢✡✣✡✤, ✍❂✡☛◗ ✘❺✟❻å ✤✡➈✡➉✡➊, ✚ ✍❂ ☛ï✘❽✡❾å ✤ “➈✡➉✡➊”(àï✘➈→ ), ❞✟❝✡☛✥ ❅➆⑤✟Ý✤✟à❄ ➐❞ à❏✟ß➈→ . ❫✡☛, ①✒②✡✟➈✡➉✡➊❱✡❲✤✡➌✍✡➅✡➆✡▼: ❆ ✄✡✟ G = (V, E),V = {v1, v2, . . . , vn}, E = {e1, e2, . . . , em}. ✢ ✟ G ✤✟✝Ø✟✞ e = (vi , vj ) ❇✡✇✥✡✦✟P✟á❚➌ w(e) = w(vi , vj ) = wi,j ❙ ✘, ❙✟❚ G ▼➢â✟ã✟ä✟å➟, æ✟❚➢ç✟è, ❖ ✎ w(e) ❚ ▼ e ✤ å . ✢ P ▼ G ✎ v1 ➔ vn ✤✡➊, ❚ W(P) = X e∈E(P ) w(e) ▼ P é✟ê✟ë, ❖ ✎ E(P) ➶í P å✟✞✤✟❇✟❈. ✢ P ∗ ▼ G ✎ v1 ➔ vn ✤✡➊, ➟✟➼✟➽ W(P ∗ ) = min{W(P)|P▼ G ✎ v1 ➔ vn ✤✡➊} ❙✟❚ P ∗ ▼ v1 ➔ vn ✤➢ì✟í✟î. ❶✡❷✡✤❱✡❲q✡☛✡✭✡✟ G ✎✳✟❜✟ï✟ð v1 ➔ vn ✤✡➈✡➉✡➊✟ñ✐÷ ❖✟❁✟❂. ➈✡➉✡➊❱✡❲✍❂ ❩✡ê✡✘✡✙❫✡❝✟ò④✡⑥✡❚✡❯, ☞✟③✡❆✩ ✪⑧✟ót❖❱✡❲, ✲✡✳➦ ➂ ❆✟ô õ❹ö❹❖, ÷❹ø❹ù➅ , ❖❹ú❹û❹ü❹ý❹þ❹ÿ❹ÿ. ✂✁, ✄✂☎✂✆ö✂✝✂✞✂✟✂✠ v1 ✡✟✂✠ v2, v3, . . . , v7 õ ☛ ø✟÷✟ø, ✆✌☞☛ ø✌✍✌✎✌✏✌✑ 9–15 ✒✌✓✌✔õô ø ö✌✝. ✝ ✑✖✕✘✗✌✙õ✌✚✌✛✌✜✌✢✌✣✤✠✌✥✁õ ✦✌✧, ✆✌☞✌★✌✩✞ v1 ✡ v2 ✪ v3, ✪ v4, . . ., ✪ v7 õ☛ ø✌✫✌✬✌✭✌✮õ✟ö✌✝✌✯✌✰. ✱✌✌✁, ✞ ✲✌✳✌✴✌✟ v1 ✵ ✲✌✳✌✶✌✷✗✌✸✌✹✌✺ v2, v3, . . . , v7, ✁✌✑ 9–16 ✗✌✙✚✌✛✌✻✌✼✌✽✟õ✌✣✌✠✌✥✦✌✧, ✆✌☞✞ v1 ✾ ✲✌✳✌✶✌✷✗✌✹✌✺✌✿✦✌✧✭✌✮õø. ✑ 9–15 ✑ 9–16 ✞✤❀✤❁✤✣✤❂✤❃✤❄✤❅✤❆✤❇, ý✁þ✤❈✤❉✆✤☞✞ v1 ✡✤❊✤❋✗ ✠✦✤✧✭✤✮õø, ●✤❍✻✭ ✮❹øý❹þ. ❋✂■✂❏✂❑✼✂✽✂▲◆▼✂❖◗P✂❘✂❙◆▼✌❖✘P❹õ✭✂✮✟øý✟þ. ✭✂✮❹øý❹þ✂❉✑✂❚✽✂❯❹õ✂❱ ❲ý✟þ❍✌❳. ❨❬❩❪❭❬❫❬❴❬❵❜❛❞❝❜❡❞❢ ☞✌❣✌✭✌✮✟øý✟þ✟õ✌❤✌✐✌❥✌❦, ❧♥♠✌♦✌♣õ✭✌q❤✌✐✌❉✖r E.W.Dijkstra s 1959 t✌✉✌❇ õ , ❋✌✈✌✇☞✌❇ v1 ✡ vn õ✭✌✮✟ø, ✭✌①✌✒✌②✡ õ✌③✌④✌❀✌❉✌✞✌⑤✌✠ v1 ✡✗ ✠✟õ✭✌✮✟ø
第九章图与网络 算法思路 若P=u.vU是从到的最短路，则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间的比 234更短的路，这与假设矛盾. 图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 ✜✌✢✌➬✌❤↕✁✂, ✾ ❀✌❁✌➢↕➬✌❤✒✌②✁✄✁☎✝✆✁✞✤☎✌❳→ , ✟✌②
8 第九章图与网络 如下运算矩阵， T() 0° +o +∞ 15 +0 +0 10 135 + 15 436 > 3 从而P()=0,P(2)=10,P(w)=11,P(a)=8,P()=15,Pw)=13,P() 35. 例5.求图9-19中m至w的最短路及其长度 图9-19 解我们仅列出运算矩阵： T(v;) U6 + + + 11 21 十0 21 A2 42 + + + 45 4 42 +0 + 6 6* + 756 10 由矩阵知：P(%)=10,它由产生；P()=7,它由或%产生：若P()由%产 生，P(=4,它由2产生：P(2)=1.它由产生：若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它由2产必P)=L它由n产必故至的最短路有两条 P=功257g; P登=t2467g, 长度为10 修预菊产法色中女的洗肉来“多 向造通的有向边数它们的权都为uO,即ua,g)=r,）=o, 以上两个例题 表示明了这一点 两、应距选例 例6.设备更新问题 某工厂或用一长设备每年年度该厂所对该设备的更新与否最出根」 若又屋新设 各.就要支 之在的有制宽个若干年之的设备理 ：若继续或用日设各，则所支 ,定的维修 经各或用的年数 为长，每年所所的维修 或一这长设备的“新设备入置和旧设备赁 用最小.我们以一个五年之将设 备更新的计上为例，若已知该设备在五年将 的看如表91所示 表9-1 第4年☐123T 45 1111121213 还已知设备或用不您年数的维修把如表9-2所示 表92 或用是年 0,1(1,223(3,4(45 维修： b 5 6811 18 把解可其选择的设备更新方案显然是很多的.例如每年都又置一新设备，则其又置 为11+11+12电12+13=59，而每年支的维修为5，五年它计5×5=25.所以 变这一方案下， 讲一 用为36季27=68， 那么，如何制定或得 题，建立网络模和如图g2 把用最小的设备更新计上有可以把这个问题前化为最短路问
§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 设顶点1，，%表示各年年初，%相当于第五年末边(，)表示在第i年年初购 买一台设备一直使用到第j年年初（即使用了j-i年）. 每条边的通，)据已知资之可按下式计算： w(4,)一第i年设备购置费+（行-）年里的设备维修费 9+6+b2++- 6=1,,5j=2,6,i< 例如，(2，%)是第3年年初购买一台新设备，使用至第5年年底。支付购置费12，由 这样，制定一个最优的设备更新计划的问题就等价于寻求到的最短路问题 用Dijkstra算法可得运算矩阵如下 T(vj) 0 +o + +00 3 16 221 301 411 22 30 41 57 4 301 411 53 5 41i 533.4 6 最短路有两条， 一条是P 1购，即第1,3年初各购置 台新设备，五年的总费用 为53：另一条是P=146,即第1,4年初各购置一台新设备，五年的总费用为53. %拉合建一置文 ,各点间的距离图9-21所示.问 ,干设在那个点可使最大运输距离为鳗攀修若子知处置产量0电处 0是老动克处”电，处0电处侧吃问置目唯移于设在可个点才能想 吨公里数最小？
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 ❜, ý✌✲✌✳✸✌✹✌✺✽✌✝☎✁❫❂✌✠, ❝ ➝ ❂ ❜✌♦✁✏✛ ✭✌➅?