最短 最短 路径问题 路径问题 参考书： 参考书： 1. 1.傅鹂 傅鹂 龚劬 龚劬 刘琼荪 刘琼荪 何中市 何中市 数学实验 数学实验 科学出版社 科学出版社 2. 2.张绍民 张绍民 李淑华 李淑华 数据结构教程 数据结构教程C C语言版 语言版 中国电力出版社 中国电力出版社 主讲：重庆大学 主讲：重庆大学 龚 龚 劬 劬 1主要内容 主要内容 Floyd算法 Dijkstra算法 两个例子的求解 引例2：最廉价航费表的制定 引例1：最短运输路线问题 最短路径问题的0-1规划模型 2如图的交通网络，每条弧上的数字代表车辆在该路段行 如图的交通网络，每条弧上的数字代表车辆在该路段行 驶所需的时间，有向边表示单行道，无向边表示可双向 驶所需的时间，有向边表示单行道，无向边表示可双向 行驶。若有一批货物要从 行驶。若有一批货物要从1 1号顶点运往 号顶点运往11 11号顶点，问运 号顶点，问运 货车应沿哪条线路行驶，才能最快地到达目的地？ 货车应沿哪条线路行驶，才能最快地到达目的地？ 引例 引例 1 1 ： ： 最短运输路线问题 最短运输路线问题 10 2 3 7 4 11 6 5 9
