实验教案4_MATLAB基础.pptVIP

1) 赋权图中从给定点到其余顶点的最短路 2) 求赋权图中任意两顶点间的最短路 算法的基本思想 算法的基本思想 （I）求距离矩阵的方法. （II）求路径矩阵的方法. （III）查找最短路路径的方法. （IV）Floyd算法：求任意两顶点间的最短路. 然后用同样的方法再分头查找．若： 例2 求下图中加权图的任意两点间的距离与路径. 插入点 v1，得： 矩阵中带“=”的项为经迭代比较以后有变化的元素. 实验4: MATLAB求最短路问题 * 信息与计算科学系 数学建模 实验4：MATLAB求解最短路问题 实验目的 实验原理、内容 2、会用Matlab软件求最短路 1、了解最短路的算法及其应用 1、最 短 路 问 题 及 其 算 法 2、实验作业 实验重点、难点 重点：Dijkstra与Floyd算法原理及步骤； 难点：Dijkstra与Floyd算法的Matlab实现。 最短路问题是图论应用的基本问题，很多实际 问题，如线路的布设、运输安排、运输网络最小费 用流等问题,都可通过建立最短路问题模型来求解. 最短路的定义 最短路问题的两种方法：Dijkstra和Floyd算法 . 1) 从给定点到其余顶点的最短路. 2) 任意两点间的最短路. 2) 在赋权图G中，从顶点u到顶点v的具有最小权 定义 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). 假设G为赋权有向图或无向图，G边上的权均非 负．若 ，则规定 最短路是一条路，且最短路的任一节也是最短路． 求下面赋权图中顶点u0到其余顶点的最短路． Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 . 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2). Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 . 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2). Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 . 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2). Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 . 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2). Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 . 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，