第十三讲最短路问题.ppt

数学建模与数学实验;教学内容:;1. 图 论 的 基 本 概 念;定义;定义;;;顶点的次数;子图;关联矩阵;邻接矩阵;;2.最 短 路 问 题 及 其 算 法;基 本 概 念;;固 定 起 点 的 最 短 路;;算法步骤：; TO MATLAB(road1);; 1;每 对 顶 点 之 间 的 最 短 路;算法的基本思想;算法原理—— 求距离矩阵的方法;算法原理—— 求路径矩阵的方法;i ;算法步骤; TO　MATLAB　(road2(floyd));a=[0 9 inf 3 inf;9 0 2 inf 7;inf 2 0 2 4;3 inf 2 0 inf;inf 7 4 inf 0]; [D,R]=floyd(a);一、 可化为最短路问题的多阶段决策问题;可化为最短路问题的多阶段决策问题;;;; 选址问题--中心问题;S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5; 选址问题--重心问题;4.实验作业;a=[0 3 inf inf inf inf inf;3 0 2 inf 18 2.5 inf;... inf 2 0 6 2 inf inf;inf inf 6 0 3 inf inf;... inf 18 2 3 0 4 inf;inf 2.5 inf inf 4 0 1.5;... inf inf inf inf inf 1.5 0]; [D,R]=floyd(a)