凌晨: 第一节最短路问题 二、最短路算法( Dijkstra算法) 3、例子的解 1)定起始点,写上永久标号[0,S]-一如:结点内涂黑表 示已有永久标号 2)(迭代)反复以下步骤: (1)为起始点能直达的结点写上临时标号 2)比较临时标号内第一个数,选择小的一个 (3)小者写成永久标号(圈内涂黑) (4)有最新永久标号的结点视为新的起始点
Ling Xueling 二、最短路算法（Dijkstra算法） 3、例子的解 1 ) 定起始点，写上永久标号 [0 ，S]－－如：结点内涂黑表 示已有永久标号 2 ) ( 迭代 ) 反复以下步骤： (1) 为起始点能直达的结点写上临时标号 (2) 比较临时标号内第一个数，选择小的一个 (3) 小者写成永久标号 ( 圈内涂黑 ) (4) 有最新永久标号的结点视为新的起始点。 第一节 最短路问题 凌晨: 凌晨:
凌晨: 第一节最短路问题 最短路算法( Dijkstra算法) 4、求出最短路 41-3 1-3-5-61-3-5-6-7 5、第二个例子 在如下页的网络中,求结点1和结点10之间的最短路径 解 3--5--8--10 total=19
Ling Xueling 二、最短路算法（Dijkstra算法） 4、求出最短路 1－3－2 1－3 1－3－5－4 1－3－5 1－3－5－6 1－3－5－6－7 5、第二个例子 在如下页的网络中，求结点 1 和结点 10 之间的最短路径 解答： 1－－3－－5－－8－－10 total = 19。 第一节 最短路问题 凌晨: 凌晨:
凌晨: 第一节最短路问题 最短路算法( Dijkstra算法) 12 4 5 14 8 5 5 10 6)5 10 12 13 9 10
Ling Xueling 二、最短路算法（Dijkstra算法） 第一节 最短路问题 凌晨: 凌晨: 1 2 3 4 5 6 7 8 9 1 0 2 5 1 1 2 1 4 6 1 0 4 1 3 1 2 1 1 3 9 6 5 8 1 0 5 2
凌晨: 第一节最短路问题 说明 1、算法中,起始结点可以任意选定,N个结点问题, 般需要有N-1次迭代 2、“MS软件包只要先输入网络,可以解决此类问题 3、其它用处:最小旅行时间问题、旅行成本问题、管 道铺设问题、线路安排问题、厂区布局问题、设备更 新问题等等 4、练习的第四题一一设备维护问题说明 5、标号法已发展到可以解决:(时间所限不展开讨论) (1)弧值为负数; )有向网络(如:单行道运输问题)
Ling Xueling 三、说明 1、算法中，起始结点可以任意选定, N 个结点问题， 一般需要有 N－1 次迭代 2、 “MS”软件包只要先输入网络，可以解决此类问题 3、其它用处：最小旅行时间问题、旅行成本问题、管 道铺设问题、线路安排问题、厂区布局问题、设备更 新问题等等 4、练习的第四题――设备维护问题说明 5、标号法已发展到可以解决：(时间所限不展开讨论) (1) 弧值为负数； (2) 有向网络 ( 如：单行道运输问题 )。 第一节 最短路问题 凌晨: 凌晨:
凌晨: 筒二节最小支撑树问题 概念 1、树一一不含圈的联通图 2、什么是(网络)最小支撑树 1)贯通网络所有结点一一支撑 2)分枝(弧)总长度最小一一最小 3、用处:分子结构问题、电网络分析问题、计算机 网络设立问题、管道铺设问题等等的解决
Ling Xueling 一、概念 1、树－－不含圈的联通图 2、什么是（网络）最小支撑树 1) 贯通网络所有结点――支撑 2) 分枝 (弧) 总长度最小――最小 3、用处：分子结构问题、电网络分析问题、计算机 网络设立问题、管道铺设问题等等的解决。 第二节 最小支撑树问题 凌晨: 凌晨: