数学建模图论模型(1).ppt

数学与统计学院 李书选 2012/07/17不积硅步，无以至千里不积硅步，无以至千里-荀子荀子劝学劝学下下回回停停 1. 几个引例几个引例2. 基本概念基本概念 1. 基本概念基本概念 3. 最短路问题及算法最短路问题及算法 4. 简单应用简单应用 下下回回停停ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题1:七桥问题七桥问题 能否从任一陆地出发通过每座桥恰好一次而回到出发点？1. 几个引例几个引例下下回回停停七桥问题模拟图七桥问题模拟图ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出从任一陆地出发，必能通过每座桥恰好一次而回到出发地。发地。下下回回停停 莱昂哈德欧拉(Leonhard Euler，1707.4.5-1783.9.18) 瑞士的数学家和物理学家。他被称为历史上最伟大的两位数学家之一（另一位是卡尔弗里德里克高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林，尔后再返圣彼得堡(1766)。 欧拉的一生很虔诚。然而，那个广泛流传的传说却不是真的。传说中说到，欧拉在叶卡捷琳娜二世的宫廷里，挑战德尼狄德罗：“先生，(a+b)n/n = x；所以上帝存在，这是回答！” 欧拉的离世也很特别：据说当时正是下午茶时间，正在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。 欧拉是第一个使用“函数”一词来描述包含各种参数的表达式的人，例如：y = F(x) (函数的定义由莱布尼兹在1694年给出)。他是把微积分应用于物理学的先驱者之一。欧拉是有史以来最多产的数学家，他的全集共计75卷。欧拉实际上支配了18世纪的数学，对于当时新发明的微积分，他推导出了很多结果。在他生命的最后7年中，欧拉的双目完全失明，尽管如此，他还是以惊人的速度产出了生平一半的著作。 小行星欧拉2002是为了纪念欧拉而命名的。莱昂哈德莱昂哈德欧拉欧拉 下下回回停停问题问题2:哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？下下回回停停问题问题3:四色问题四色问题 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。德德摩尔根致哈密顿的信（摩尔根致哈密顿的信（1852年年10月月23日）日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。下下回回停停问题问题4(4(关键路径问题关键路径问题) ) 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目, , 影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？ 2.图论的基本概念图论的基本概念1) 图的概念图的概念2) 赋权图与子图赋权图与子图3) 图的矩阵表示图的矩阵表示4) 图的顶点度图的顶点度5) 路和连通路和连通1) 图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中: 其中元素称为图其中元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.),(jivv 定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|, 用用来表示；来表示；v图的边的数目图的边的数目|E(G)|用用 来表示来表示. 也用也用来表示边来表示边jivv).,(jivv,)(21vvvGV是非空有限集，称为是非空有限集，称为顶顶点集点集，1)2) E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对).,(EVG )(),(GEGVG 表示图，表示图，简记简记 用用 定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图. 只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图都称为所有图都称为非平凡图非平凡图. 定义若若图图G中的边均为有序偶对中的边均为有序偶对,称称G为为有向有向),(jivv边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称图图. 称边称边为为有向边有向边或或弧弧,称称),(jivve 是从是从),(jivve iv连接连接jv，称，称 为为e的的尾尾，称，称 为为e的的头头. ivjv 若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称jivv为为e的的端点端点. jivve ivjvivjv 既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图. 常用术语常用术语1) 边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合为一点的边称为端点重合为一点的边称为环环， 端点不相同的边称为端点不相同的边称为连杆连杆.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5) 既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 常用术语常用术语6) 任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图. 记为记为Kv. 7) 若若 ， ，且且X 中任意两顶点不中任意两顶点不YXGV)(YX ， 相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)nmK,8) 图图 叫做叫做星星.nK, 1:X1x2x3x:Y1y2y3y4y二部图二部图6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K2) 2) 赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都赋以都赋以)(),(GEGVG 一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图.),(EVG ),(EVG 1) 若若 ,称称 是是 的一个的一个子图子图,记记 EEVV,GG.GG 2) 若若 ， ，则称，则称 是是 的的生成子图生成子图.VV EE GG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG 为为 的的由由 导出的子图导出的子图，记为，记为 .GVVG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EGGVVG 为为 的的由由 导出的子图导出的子图，记为，记为 .3) 3) 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： G)(ijaA., 0, 1不相邻与若相邻与若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假设图为简单图以下均假设图为简单图).2) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： )(ijaA),(EVG .),(, 0,),(, 1EvvEvvajijiij若若432143210100001000001110uuuuAuuuu其中：其中：3) 对有向赋权图对有向赋权图 , 其邻接矩阵其邻接矩阵 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，为其权，且若43214321040608730uuuuAuuuu对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义. 关联矩阵关联矩阵 1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,),(EVG )(ijmM其中：其中：., 0, 1不关联与若相关联与若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee2) 对有向图对有向图 ，其关联矩阵，其关联矩阵 ,),(EVG )(ijmM., 0, 1, 1的头与尾不是若的头是若的尾是若jijijiijevevevm其中：其中：43215432111000101100001101101uuuuMeeeee 邻接矩阵 A = (aij )nn , EvvEvvajijiij, 0, 1例 写出右图的邻接矩阵0101100101001010A解：图的矩阵表示图的矩阵表示 权矩阵A = (aij ) nn EvvjiEvvvvFajijijiij , , 0 ,例 写出右图的权矩阵：05420370860A解：图的矩阵表示图的矩阵表示4) 图的顶点度图的顶点度定义定义 1) 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点.2) 在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度或或次数次数定理定理.2)(Vvvd的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点4)(1vd1)(3ud2)(3ud3)(3ud5) 路和连通路和连通 定义定义1) 无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替kkveevevW2110 地为顶点和边，使得对地为顶点和边，使得对 ， 的端点是的端点是 和和 ,ki 1ie1iviv称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径. 整整0vkv),(0kvv数数k称为称为W的的长长. 顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点 ,0vkv而而 称为称为W的的内部顶点内部顶点.121,kvvv 2) 若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W为为迹迹或或简单链简单链. 3) 若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路0vkv),(0kvv记为记为).,(0kvvP 定义定义 1) 途径途径 中由相继项构成子序列中由相继项构成子序列kkvevevW.110 称为途径称为途径W的的节节.jjiiivevev.11 2) 起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径. 3) 起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长，长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck. 4) 若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通. 5) 若在图若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之之间的之间的距离距离d(u,v)是指图是指图G中最短中最短(u,v)路的长；若没路的长；若没没有路连接没有路连接u和和v，则定义为无穷大，则定义为无穷大. 6) 图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 7) 对于有向图对于有向图G，若，若 ，且，且 有有kkveevevW2110ie 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈.头头 和尾和尾 ，则称，则称W为为有向途径有向途径.iv1iv 例例 在右图中：在右图中： 途径或链：途径或链： 迹或简单链：迹或简单链： 路或路径：路或路径： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg例例 一摆渡人欲将一只狼，一头羊，一篮菜从一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。河方法。解：解：用四维用四维0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取状态，（在西岸则分量取1，否则取，否则取0.）共共24=16种状态，种状态，由题设，状态（由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不是不允许的，允许的，从而对应状态（从而对应状态（1,0,0,1），），(1,1,0,0),(1,0,0,0)也是也是不允许的，不允许的，图论的基本概念图论的基本概念人在河西：（1,1,1,1） （1,1,1,0） （1,1,0,1） （1,0,1,1）（1,0,1,0）（0,1,0,1） （0,1,0,0） （0,0,1,0） （0,0,0,1） （0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。图论的基本概念图论的基本概念3最短路问题及算法最短路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法 .1) 求赋权图中从给定点到其余顶点的最短求赋权图中从给定点到其余顶点的最短路路. .2) 求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路. 2) 在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的具有最小权定义定义 1) 若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的各的各边的权和边的权和 为为H的的权权. 类似地，若类似地，若)()()(HEeewHw称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称)()()(PEeewPw 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3) 把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v). 1) 赋权图中从给定点到其余顶点的最短路赋权图中从给定点到其余顶点的最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非边上的权均非负若负若 ，则规定，则规定 )(),(GEvu.),(vuw最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点的最短路到其余顶点的最短路Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul02Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul03Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul04Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul05Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul06Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul07Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul)()(min10ulvlSv8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).定义 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v0u的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱点点，记为，记为z(v), 即即z(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径. 例例5的标号过程也的标号过程也可按如下方式进行：可按如下方式进行： 首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵024782063446046340357630135102273201847210W因因G是无向图，故是无向图，故W是对称阵是对称阵1u0u6u7u2u4u3u5uDijkstra算法：算法：求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均均非负边上的权均均非负. 对每个顶点，定义两个标记（对每个顶点，定义两个标记（l(v)，z(v)），其中），其中: l(v) ：表从顶点表从顶点u0到到v的一条路的权的一条路的权 z(v) ：v的先驱点，用以确定最短路的路线的先驱点，用以确定最短路的路线.l(v)为从顶点为从顶点u0到到v的最短路的权的最短路的权算法的过程就是在每一步改进这两个标记，使最终算法的过程就是在每一步改进这两个标记，使最终S：具有永久标号的顶点集：具有永久标号的顶点集.输入输入: G的带权邻接矩阵的带权邻接矩阵 w(u,v)备用备用-将求最短路与最短路径结合起来将求最短路与最短路径结合起来:算法步骤：算法步骤：l(v)u0vl(u)uw(u,v)首先写出带权邻接矩阵首先写出带权邻接矩阵024782063446046340357630135102273201847210W例例 求下图从顶点求下图从顶点u0到到其余顶点的最短路其余顶点的最短路因因G是无向图，故是无向图，故W是对称阵是对称阵1u0u6u7u2u4u3u5u2) 求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路 算法的基本思想算法的基本思想 （I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.（III）查找最短路路径的方法）查找最短路路径的方法. Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路. 举例说明举例说明算法的基本思想算法的基本思想（I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R ivjv（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.例例 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径. ,053142503330212044401210 )0(D,654321654321654321654321654321654321 )0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v2，得：得：,053132503330212043401210)1(D矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入点插入点 v3，得：得：,05313250333021204534012510)2(D,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D插入点插入点 v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入点插入点 v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v6，得：得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d8)6(52d故从故从v5到到v2的最短路为的最短路为8 6)6(52R由由v6向向v5追溯追溯: . 6)6(56R由由v6向向v2追溯追溯: , 1)6(62R. 2)6(12R所以从到的最短路径为：所以从到的最短路径为： .2165vvvv学而时习之，不亦说乎学而时习之，不亦说乎-论语论语学而学而4最短路问题的简单应用最短路问题的简单应用返回返回 选址问题选址问题-中心问题中心问题则kv就是要求的建立消防站的地点此点称为图的中心点中心点05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故应将消防站设在v3处. 返回返回 选址问题选址问题-重心问题重心问题返回返回