暑期集训1-乘公交看奥运2007B课件.ppt

Dijkstra算法（标号算法，1959） STEP1. 如果S=V, 则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得), 结束.否则继续. STEP0. (初始化) 令S= ，=V， ；对V 中的顶点j(j s)令初始距离标号 . STEP2. 从 中找到距离标号最小的节点i，把它从 删除，加入S. 对于所有从i出发的弧 , 若 ，则令 转STEP1. 特点：1. 算法求出从源点s到所有点的最短路长 2. 每点给一对标号 (uj, predj)，uj是从s到j的最短路长；predj是从s到j的最短路中j点的前一点 数学与统计学院 费文龙 feiwl@126.com * Example 数学与统计学院 费文龙 feiwl@126.com * Dijkstra算法（标号设定算法） 适用于正费用网络：“分层”设定标号 永久标号：S中的点，uj是最短路长 临时标号；其他点， uj是只通过S中的点的最短路长 对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次. 对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为 或 等 算法复杂度O( n2+m)：如链表或邻接矩阵实现 找最小标号点　　　修改标号 数学与统计学院 费文龙 feiwl@126.com * 　特点：求所有点对间最短路 　基本思想：逐步逼近，迭代求解最短路方程: O(n3) Floyd-Warshall算法 （标号修正算法，1962) 临时标号 是不通过k，k+1，…,n 节点(i,j 除外)时从节点i到节点j的最短路路长. 数学与统计学院 费文龙 feiwl@126.com * Floyd-Warshall算法的具体实现: O(n3) 由于要记录所有节点之间最短路的信息, 所以这里我们要用一个二维数组P； 可依据P, 采用“正向追踪”的方式得到最短路. STEP2：如果k=n, 结束; 否则转STEP1. STEP0: k=0. 对于所有节点i和j: 令 ， , ( ，若节点i和j之间没有弧, 认为 ) . STEP1: k=k+1. 对于所有节点i和j: 若 , 令 , ; 否则令 , . 数学与统计学院 费文龙 feiwl@126.com * 数学与统计学院 费文龙 feiwl@126.com 数学建模暑期集训 * 数学与统计学院 费文龙 feiwl@126.com 数学建模暑期集训 * 数学与统计学院 费文龙 feiwl@126.com 数学建模暑期集训 * 数学与统计学院 费文龙 feiwl@126.com 数学建模暑期集训 * 数学与统计学院 费文龙 feiwl@126.com 数学建模竞赛案例选讲 —乘公交 看奥运 2007B 主讲：费文龙 数学建模暑期集训 2007B 题目： 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑