凌晨: 第八章网络模型 网络模型的讨论,本质上属于图论范畴 用途极其广泛(如:运输系统设计、信息系统 设计、项目计划管理等)、实用性强,是网络 模型的特征之一,其解法的特殊,也是值得关 注的地方 需要重点掌握:各种网络模型的算法
Ling Xueling 网络模型的讨论，本质上属于图论范畴 用途极其广泛（如：运输系统设计、信息系统 设计、项目计划管理等）、实用性强，是网络 模型的特征之一，其解法的特殊，也是值得关 注的地方 需要重点掌握：各种网络模型的算法。 第八章 网络模型 凌晨: 凌晨:
凌晨: 第一节最短路问题 问题及网络图表示 1、什么是最短路问题 在网络中任意选择某点为起点,求出从此起点到网络中其余 各点的最短路径。如:Taxi的调度问题 2、例子 Gorman建筑公司承担了散布在邻近三个区域内的一些建筑 项目,公司总部与这些工地之间经常有人员、设备、材料等 的运输往来。与运输成本相关的最短路问题,就是很值得考 虑的重要问题 设公司总部与六个工地间的公路网络如下页所示: (单位:km)
Ling Xueling 一、问题及网络图表示 1、什么是最短路问题 在网络中任意选择某点为起点，求出从此起点到网络中其余 各点的最短路径。如：Taxi 的调度问题 2、例子 Gorman 建筑公司承担了散布在邻近三个区域内的一些建筑 项目，公司总部与这些工地之间经常有人员、设备、材料等 的运输往来。与运输成本相关的最短路问题，就是很值得考 虑的重要问题 设公司总部与六个工地间的公路网络如下页所示： ( 单位：km )。 第一节 最短路问题 凌晨: 凌晨:
凌晨: 第一节最短路问题 问题及网络图表示 17 2 15 1 4 6 10 总部 3 4 5 NODE ARC
Ling Xueling 一、问题及网络图表示 第一节 最短路问题 凌晨: 凌晨: 1 2 3 4 5 6 7 总部 1 5 3 1 0 1 7 6 2 4 6 5 4 node arc
凌晨: 第一节最短路问题 最短路算法 介绍 Dijkstra算法 ( Dijkstra于1959年提出,又称加标号法 labeling procedure 1、结点之标号(给出:累计路程、路径两个指标) 20.4 表示从起始结点 表示从起始结点至 到本结点的距离 是20 结点 本结点的最短路仨 上前一个结点是4
Ling Xueling 二 、 最 短 路 算 法 － － 介 绍 Dijkstra 算 法 (Dijkstra 于 1959 年提 出，又称 加标号 法 labeling procedure ) 1、结点之标号(给出：累计路程、路径两个指标) 第一节 最短路问题 凌晨: 凌晨: 20, 4 结点 表示从起始结点 到本结点的距离 是 20 表示从起始结点到 本结点的最短路径 上前一个结点是 4
凌晨: 第一节最短路问题 最短路算法( Dijkstra算法) 、结点标号的分类 1)有/无标号结点 有标号结点一一已指定从起始结点到此结点的一条路径 无标号结点一一未指定从起始结点到此结点的路径 2)永久/临时标号 有永久标号结点一一已求出从起始点到此结点的最短路径 有临时标号结点—一未求出从起始点到此结点的最短路径
Ling Xueling 二、最短路算法（Dijkstra算法） 2、结点标号的分类 1）有/无标号结点 有标号结点－－已指定从起始结点到此结点的一条路径 无标号结点－－未指定从起始结点到此结点的路径 2）永久/临时标号 有永久标号结点－－已求出从起始点到此结点的最短路径 有临时标号结点－－未求出从起始点到此结点的最短路径。 第一节 最短路问题 凌晨: 凌晨: