数学建模提高班第六讲网络优化模型及案例分析市公开课一等奖百校联赛特等奖课件.pptx

网络优化模型及案例分析网络优化模型及案例分析赵承业赵承业 /4/2 /4/24 4第1页本专题学习目本专题学习目掌握把实际问题转化为图或网络问题方法了解图基本概念和矩阵表示方法掌握最短路问题、最小生成树问题算法了解旅行商问题第2页主要内容主要内容第3页主要内容主要内容第4页图论起源：七桥问题图论起源：七桥问题第5页 c a b d c a b d 图论起源：七桥问题图论起源：七桥问题图1图2第6页欧拉图论之父 定理1：一个图存在经过每边恰好一次回到出发点路线充要条件是：1）图要是连通连通2）与图中每一顶点相连边必须是偶数偶数条。于是得出结论：七桥问题无解。图论起源：七桥问题图论起源：七桥问题返返返返 回回回回第7页无向图，普通用大写字母G,H表示。一个表示工具一个表示工具图图顶点顶点边边 d c a b 图3第8页 无向图：G=(V,E)，顶点集：V；边集：E。e与顶点u,v相关联。u与v相邻。两边相邻。重边 c a b d 一个表示工具一个表示工具图图图4第9页两种特殊图：简单图 完全图，记为Knb d c a b d c a 一个表示工具一个表示工具图图图6图5第10页有向图：V1V2V3V5V4你能给出一个可用有向图描述实际例子吗？一个表示工具一个表示工具图图图7第11页网络网络这些数字能够代表距离距离，费用费用，可可靠性靠性或其它相关参数。12345869157103一个表示工具一个表示工具图图图8第12页(G)和(G)分别表示图G顶点数和边数在无向图中，v度数，记为d(v)；在有向图中，v出度，记为d+(v);v入度，记为d-(v)。一个表示工具一个表示工具图图返返返返 回回回回第13页一个时间安排问题一个时间安排问题 学校要为一年级硕士开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册学生必须选修其中一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选课程，在时间上不会发生冲突。第14页一个时间安排问题一个时间安排问题表1第15页SNGRPM完成上述表示课程冲突关系图直观、清楚地表示已知信息方式一个时间安排问题一个时间安排问题返返返返 回回回回图9第16页人狼羊菜渡河问题人狼羊菜渡河问题摆渡人F狼W羊G菜C图10第17页 南岸状态：16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：人狼羊菜渡河问题人狼羊菜渡河问题第18页FWGCFWG FWC FGCFGOCGWWC寻求图中从顶点“FWGC”到顶点“O”最短路径，这么路径有几条？求出最优渡河方案。语言描述时未显示关系跃然纸上人狼羊菜渡河问题人狼羊菜渡河问题图11第19页FWGCFWG FWC FGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河问题人狼羊菜渡河问题返返返返 回回回回图12第20页图矩阵表示方法图矩阵表示方法邻接矩阵关联矩阵边矩阵邻接次序表返返返返 回回回回第21页v1v2v5v6v7v4v3abjkcghidfe邻接矩阵图13第22页 无向图邻接矩阵：A=(aij)nn，其中无向图邻接矩阵有何特点？由邻接矩阵是否能作出原图？邻接矩阵返返返返 回回回回第23页关联矩阵v1v2v5v6v7v4v3abjkcghidfe图13第24页 无向图关联矩阵：M=(mij)nm,其中 无向图关联矩阵有哪些特征？由关联矩阵能否作出原图？关联矩阵返返返返 回回回回第25页边矩阵v1v2v5v6v7v4v3abjkcghidfe返返返返 回回回回图13第26页最短路问题及算法最短路问题及算法 最短路问题是图论应用基本问题，很多实际最短路问题是图论应用基本问题，很多实际问题，如线路布设、运输安排、运输网络最小费问题，如线路布设、运输安排、运输网络最小费用流等问题用流等问题,都可经过建立最短路问题模型来求解都可经过建立最短路问题模型来求解.最短路定义最短路定义最短路问题两种方法：最短路问题两种方法：Dijkstra和和Floyd算法算法.1)1)求赋权图中从给定点到其余顶点最短路求赋权图中从给定点到其余顶点最短路求赋权图中从给定点到其余顶点最短路求赋权图中从给定点到其余顶点最短路.2)求赋权图中任意两点间最短路求赋权图中任意两点间最短路.第27页 2)在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v含有最小权含有最小权定义定义1 1)若若H是赋权图是赋权图G一个子图，则称一个子图，则称H各各边权和边权和 为为H权权.类似地，若类似地，若称为路称为路P权权若若P(u,v)是赋权图是赋权图G中从中从u到到v路路,称称 路路P*(u,v)，称为，称为u到到v最短路最短路 3)把赋权图把赋权图G中一条路权称为它中一条路权称为它长长，把，把(u,v)路最小权称为路最小权称为u和和v之间之间距离距离，并记作，并记作 d(u,v).第28页1)赋权图中从给定点到其余顶点最短路赋权图中从给定点到其余顶点最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上权均非边上权均非负若负若 ，则要求，则要求 最短路是一条路，且最短路任一节也是最短路最短路是一条路，且最短路任一节也是最短路例例 求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点最短路到其余顶点最短路图14第29页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第30页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第31页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第32页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第33页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第34页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第35页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第36页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第37页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第38页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第39页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第40页Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点最短路到其余顶点最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把到达这个最小值，并把到达这个最小值一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停顿；若，则停顿；若 ，则用，则用 i+1 代代替替i，并转，并转2).第41页第42页定义2 依据顶点依据顶点v标号标号l(v)取值路径，使取值路径，使 到到v最短路中与最短路中与v相邻前一个顶点相邻前一个顶点w，称为，称为v先驱先驱点点，记为，记为z(v),即即z(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径.例例5标号过程也标号过程也可按以下方式进行：可按以下方式进行：首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵因因G是无向图，故是无向图，故W是对称阵是对称阵第43页表2第44页续表2图8第45页2)求赋权图中任意两顶点间最短路求赋权图中任意两顶点间最短路算法基本思想（I）求距离矩阵方法）求距离矩阵方法.（II）求路径矩阵方法）求路径矩阵方法.（III）查找最短路路径方法）查找最短路路径方法.Floyd算法：求任意两顶点间最短路算法：求任意两顶点间最短路.举例说明举例说明第46页算法基本思想算法基本思想第47页（I）求距离矩阵方法）求距离矩阵方法.第48页（II）求路径矩阵方法）求路径矩阵方法.在建立距离矩阵同时可建立路径矩阵在建立距离矩阵同时可建立路径矩阵R 第49页（III）查找最短路路径方法）查找最短路路径方法.然后用一样方法再分头查找若：然后用一样方法再分头查找若：图16第50页（IV）Floyd算法：求任意两顶点间最短路算法：求任意两顶点间最短路.第51页例例 2求下列图中加权图任意两点间距离与路径求下列图中加权图任意两点间距离与路径.图17第52页插入点插入点 v1，得：得：矩阵中带矩阵中带“=”项为经迭代比较以后有改变元素项为经迭代比较以后有改变元素.第53页插入点插入点 v2，得：得：矩阵中带矩阵中带“=”项为经迭代比较以后有改变元素项为经迭代比较以后有改变元素.第54页插入点插入点 v3，得：得：第55页插入点插入点 v4，得：得：插入点插入点 v5，得：得：第56页插入点插入点 v6，得：得：第57页故从故从v5到到v2最短路为最短路为8 由由v6向向v5追溯追溯:由由v6向向v2追溯追溯:所以从到最短路径为：所以从到最短路径为：返返返返 回回回回第58页最小生成树及算法最小生成树及算法许多应用问题都是一个求无向连通图最小生成树问题。比如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市任意两个之间都能够通信，但铺设光缆费用很高，且各个城市之间铺设光缆费用不一样；另一个目标是要使铺设光缆总费用最低。这就需要找到带权最小生成树。第59页1)树定义与树特征定义定义3 连通且不含圈无向图称为连通且不含圈无向图称为树树惯用惯用T表示表示.树中边称为树中边称为树枝树枝.树中度为树中度为1顶点称为顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡树平凡树.平凡树平凡树图18第60页定理定理2 设设G是含有是含有n个顶点图，则下述命题等价：个顶点图，则下述命题等价：1)G是树（是树（G无圈且连通）；无圈且连通）；2)G无圈，且有无圈，且有n-1条边；条边；3)G连通，且有连通，且有n-1条边；条边；4)G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.第61页2）图生成树）图生成树定义定义4 若若T是包含图是包含图G全部顶点子图全部顶点子图,它又是树它又是树,则称则称T是是G生成树生成树.图图G中不在生成树边叫做中不在生成树边叫做弦弦.定理定理3 图图G=(V,E)有生成树充要条件是图有生成树充要条件是图G是连是连 通通.证实证实 必要性必要性是显然是显然.第62页第63页（II）找图中生成树方法）找图中生成树方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法破圈法 第64页A 避圈法避圈法 定理定理3充分性证实提供了一个结构图生充分性证实提供了一个结构图生成树方法成树方法.这种方法就是在已给图这种方法就是在已给图G中，每步选出一条中，每步选出一条边使它与已选边不组成圈，直到选够边使它与已选边不组成圈，直到选够n-1条边为止条边为止.这种方法可称为这种方法可称为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边选法不一样，找图中生在避圈法中，按照边选法不一样，找图中生成树方法可分为两种：成树方法可分为两种：深探法深探法和和广探法广探法.第65页a)深探法深探法 若这么边另一端均已经有标号，就退到标号为若这么边另一端均已经有标号，就退到标号为步骤以下：步骤以下：i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v各边，另一各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例3用深探法求出下列图用深探法求出下列图10一棵生成树一棵生成树 图19012345678910111213图20第66页3b)广探法广探法步骤以下：步骤以下：i)在点集在点集V中任取一点中任取一点u,ii)令全部标号令全部标号i点集为点集为是否均已标号是否均已标号.对全部未对全部未标标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1点重复步点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检验检验Vi,VVi中边端点中边端点边边.例例4用广探法求出下列图用广探法求出下列图10一棵生成树一棵生成树 图191012213212234标号为止标号为止.图21第67页B 破圈法 相对于避圈法，还有一个求生成树方法叫做相对于避圈法，还有一个求生成树方法叫做“破圈法破圈法”.这种方法就是在图这种方法就是在图G中任取一个圈，任中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直意舍弃一条边，将这个圈破掉，重复这个步骤直到图到图G中没有圈为止中没有圈为止.例例5 用破圈法求出用破圈法求出下列图一棵生成树下列图一棵生成树.图22第68页B B 破圈法破圈法例例6 用破圈法求出下列图另一棵生成树用破圈法求出下列图另一棵生成树.不难发觉，图不难发觉，图生成树不是唯生成树不是唯一一.图23第69页3)最小生成树与算法最小生成树与算法 介绍最小树两种算法：介绍最小树两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法.5第70页A Kruskal算法（或避圈法）算法（或避圈法）步骤以下：步骤以下：1)选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2)若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)尽可能小权，尽可能小权，3)当第当第2)步不能继续执行时，则停顿步不能继续执行时，则停顿.定理定理4 由由Kruskal算法构作任何生成树算法构作任何生成树都是最小树都是最小树.第71页例例7用用Kruskal算法求下列图最小树算法求下列图最小树.在左图中在左图中 权值权值最小边有最小边有 任取一条任取一条 在在 中选取权值中选取权值最小边最小边 中权值最小边有中权值最小边有 ,从中选从中选任取一条边任取一条边会与已选边组成圈会与已选边组成圈,故停顿故停顿,得得中选取在中选取中选取在中选取 中选取中选取 .但但 与与 都都图24第72页B破圈法算法算法2 步骤以下：步骤以下：1)从图从图G中任选一棵树中任选一棵树T1.2)加上一条弦加上一条弦e1，T1+e1中中 马上生成一个圈马上生成一个圈.去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检验剩下弦，直到全检验剩下弦，直到全部弦检验完成为止部弦检验完成为止.例例8 用破圈法求下列图最小树用破圈法求下列图最小树.先求出上图一棵生成树先求出上图一棵生成树.加以弦加以弦 e2,得到圈得到圈v1v3v2v1,去掉最大权边去掉最大权边e2,得到一棵新得到一棵新树仍是原来树；树仍是原来树；再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,去掉最大权边去掉最大权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全全部弦均已试过全部弦均已试过,得最小树得最小树.返返返返 回回回回图25第73页旅行售货员问题旅行售货员问题 定义定义6设设G=(V,E)是连通无向图，包含图是连通无向图，包含图G每个每个顶点路称为顶点路称为G哈密尔顿路哈密尔顿路(Hamilton路路或或H路路).包含图包含图G每个顶点圈，称为每个顶点圈，称为G哈密尔顿圈哈密尔顿圈(或或Hamilton圈圈或或H圈圈).含含Hamilton圈图称为圈图称为哈密尔顿图哈密尔顿图(或或Hamilton图图或或H图图).第74页旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题 一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各城镇之间距离后，应怎样计划给定各城镇之间距离后，应怎样计划他旅行路线，使他能对每个城镇恰好经过一次他旅行路线，使他能对每个城镇恰好经过一次而总距离最小？而总距离最小？它可归结为这么它可归结为这么图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个最小权找出一个最小权H圈圈,称这种圈为称这种圈为最优圈最优圈.但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),当前还当前还没有一个求解旅行售货员问题有效算法，所以没有一个求解旅行售货员问题有效算法，所以只能找一个求出相当好（不一定最优）解只能找一个求出相当好（不一定最优）解.第75页一个可行方法一个可行方法:是先求一个是先求一个H圈圈,然后适当然后适当修改修改,以得到含有较小权另以得到含有较小权另一个一个H圈圈.图26第76页定义7 若对于某一对若对于某一对i和和j，有，有则圈则圈Cij将是圈将是圈C一个一个改进改进.定义定义8 二边逐次修正法二边逐次修正法:在接连进行一系列修改之后在接连进行一系列修改之后,最终得一个圈最终得一个圈,不能不能再用此方法改进了，这个最终圈可能不是最优再用此方法改进了，这个最终圈可能不是最优,不过它是比很好，为了得到更高精度，这个不过它是比很好，为了得到更高精度，这个程序能够重复几次，每次都以不一样圈开始程序能够重复几次，每次都以不一样圈开始.这种这种方法叫做方法叫做二边逐次修正法二边逐次修正法.第77页例例9 对下列图对下列图,用二边逐次修正法求较优用二边逐次修正法求较优H圈圈.较优较优H圈圈:其权为其权为W(C3)=192图27第78页 分析分析:找出这个解好坏可用最优找出这个解好坏可用最优H圈权圈权下界与其比较而得出下界与其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈一个下界，圈一个下界，方法以下方法以下：设设C是是G一个最优一个最优H圈，则对圈，则对G任一顶点任一顶点v,C-v是是G-v路，也路，也G-v是生成树是生成树.假如假如T是是G-v最小生成树最小生成树,且且e1是是e2与与v关联边中权最小两条关联边中权最小两条边边,则则w(T)+w(e1)+w(e2)将是将是w(C)一个下界一个下界.取取v=v3,得得G-v3一一最小生成树最小生成树(实线实线),其其权权w(T)=122,与与v3关联关联权最小两条边为权最小两条边为w(T)+w(v1v3)+w(v2v3)=178.故最优故最优H圈权圈权v1v3和和v2v3,故故w(C)应满足应满足178 w(C)192.返返返返 回回回回第79页1.1.设设某某校校田田径径选选拔拔赛赛共共设设六六个个项项目目标标比比赛赛，即即跳跳高高，跳跳远远，标标枪枪，铅铅球球，100100米米和和200200米米短短跑跑，要要求求每每个个选选手手至至多多参参加加三三个个项项目目标标比比赛赛。现现有有七七名名选选手手报报名名，选选手手所所选选项项目目如如表表1 1所所表表示示。现现在在要要求求设设计计一一个个比比赛赛日日程程安安排排表表，使得在尽可能短时间内完成比赛使得在尽可能短时间内完成比赛。田径赛时间安排练习题练习题第80页表1 参赛选手比赛项目表 第81页第82页附录：图论算法附录：图论算法matlab实现实现第83页最短路问题最短路问题例 某企业在六个城市中有分企业，从ci到cj直接航程票价记在下述矩阵位置上。（表示无直接航路），请帮助该企业设计一张城市c1到其它城市间票价最廉价路线图。第84页用矩阵 （为顶点个数）存放各边权邻接矩阵，行向量pb、index1、index2、d分别用来存放标号信息、标号顶点次序、标号顶点索引、最短通路值。其中分量 index2(i)存放始点到第点最短通路中第顶点前一顶点序号；d(i)存放由始点到第点最短通路值。第85页Dijkstra Matlab程序以下：M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a=a+a;第86页pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);end index2(temp)=index;endd,index1,index2 第88页Floyd算法Matlab程序以下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);b=a+a;path=zeros(length(b);第89页for k=1:6 for i=1:6 for j=1:6 if b(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;end end endendb,path第90页最小生成树问题最小生成树问题第91页prim算法以下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult第92页Kruskal算法以下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=find(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;用 存放各边端点信息，当选中某一边之后，就将此边对应顶点序号中较大序号改记为此边另一序号，同时把后面边中全部序号为改记为。此方法几何意义是：将序号这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发觉某边两个顶点序号相同时，认为已被收缩掉，失去了被选取资格。第93页while length(result)v2 index(find(index=v1)=v2;else index(find(index=v2)=v1;end data(:,flag)=;index(:,flag)=;endresult第94页