数学建模案例分析第8讲最短路问题.ppt

数学建模数学建模*数学建模数学建模与数学实验最短路问题实验目的*数学建模实验内容2．会用MATLAB软件求最短路1．了解最短路的算法及其应用1．图论的基本概念2．最短路问题及其算法3．最短路的应用4．建模案例：最优截断切割问题5．实验作业图论的基本概念01图的概念02图的定义03顶点的次数04子图05图的矩阵表示06关联矩阵07邻接矩阵08返回09图的定义*数学建模定义有序三元组G=(V,E,)称为一个图,如果：定义*数学建模定义返回顶点的次数*数学建模例在一次聚会中，认识奇数个人的人数一定是偶数.返回子图返回注：假设图为简单图关联矩阵返回邻接矩阵注：假设图为简单图返回固定起点的最短路返回每对顶点之间的最短路基本概念最短路问题及其算法基本概念*数学建模返回固定起点的最短路*数学建模最短路是一条路径，且最短路的任一段也是最短路．01假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．02因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．03算法步骤：TOMATLAB(road1)返回每对顶点之间的最短路返回算法的基本思想求距离矩阵的方法算法步骤求路径矩阵的方法查找最短路路径的方法算法的基本思想*数学建模返回算法原理——求距离矩阵的方法*数学建模返回算法原理——求路径矩阵的方法*数学建模在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．返回)(nR算法原理——查找最短路路径的方法*数学建模ijpkp2p1p3q1q2qm则由点i到j的最短路的路径为：返回算法步骤TOMATLAB(road2(floyd))返回数学建模数学建模