文档介绍：最短路径问题最短路径问题最短路径问题参考书: 参考书: 1. 《数学实验》科学出版社《数学实验》科学出版社 2. 《数据结构教程《数据结构教程 C C语言版》中国电力出版社语言版》中国电力出版社主讲:重庆大学主讲:重庆大学龚龚劬劬主要内容主要内容 Floyd 算法 Dijkstra 算法两个例子的求解引例 2:最廉价航费表的制定引例 1:最短运输路线问题 3 如图的交通网络,每条弧上的数字代表车辆在该路段行如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道,无向边表示可双向驶所需的时间,有向边表示单行道,无向边表示可双向行驶。若有一批货物要从行驶。若有一批货物要从 1 1 号顶点运往号顶点运往 11 11 号顶点,问运号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地? 货车应沿哪条线路行驶,才能最快地到达目的地? 引例引例 1 1: :最短运输路线问题最短运输路线问题 10 237 411 6598 1 3 35 512 122 2 10 10 6 61 15 5 8 88 8 7 79 9 9 93 3 2 22 2 7 7 4 某公司在六个城市某公司在六个城市 C C 1 1,C ,C 2 2,C ,C 3 3,C ,C 4 4,C ,C 5 5,C ,C 6 6 都有分公司, 都有分公司, 公司成员经常往来于它们之间,已知从公司成员经常往来于它们之间,已知从 Ci Ci到到C C j j 的直达航的直达航班票价由下述矩阵的第班票价由下述矩阵的第 i i 行,第行,第 j j 列元素给出( 列元素给出( ??表示无表示无直达航班),该公司想算出一张任意两个城市之间的最直达航班),该公司想算出一张任意两个城市之间的最廉价路线航费表。廉价路线航费表。引例引例 2 2: :最廉价航费表的制定最廉价航费表的制定 050402510 500152025 1501020 40201001025 252010055 102525550 ???????????????????????? 5最短路径问题最短路径问题?定义:设 P(u,v) 是加权图 G中从 u到v的路径,则该路径上的边权之和称为该路径的权,记为 w(P). 从u到v 的路径中权最小者 P* (u,v) 称为 237 411 6598 1 3 35 512 122 2 10 10 6 61 15 5 8 88 8 7 79 9 9 93 3 2 22 2 7 7 最短路径算法最短路径算法 Dijkstra Dijkstra 算法算法使用范围使用范围: : 1) 1)寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径; ; 2) 2)有向图、无向图和混合图有向图、无向图和混合图; ; 3) 3)权非负权非负. .算法思路: 算法思路: 采用标号作业法采用标号作业法, ,每次迭代产生一个永久标号每次迭代产生一个永久标号, , 从而生长一颗以从而生长一颗以 v v 0 0为根的最短路树为根的最短路树, ,在这颗树上每个在这颗树上每个顶点与根节点之间的路径皆为最短路径顶点与根节点之间的路径皆为最短路径. . 10 237 4 11 6598 13 35 51 12 22 2 1 10 0 6 61 15 5 8 88 8 7 79 9 9 93 3 2 22 2 7 7 Dijkstra Dijkstra 算法算法————算法步骤 S: 具有永久标号的顶点集; l(v): v 的标记; f(v):v 的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵 w=[w(v i,v j )] nxm . 1)初始化令 l(v 0 )=0,S= ?;? v?v 0 ,l(v)= ?; 2)更新 l(v), f(v) 寻找不在 S中的顶点 u,使 l(u) S中, 然后对所有不在 S中的顶点 v,如 l(v)>l(u)+w(u,v), 则更新 l(v),f(v), 即 l(v) ? l(u)+w(u,v),f(v) ? u; 3)重复步骤 2), 直到所有顶点都在 S中为止. MATLAB MATLAB 程序( 程序( Dijkstra Dijkstra 算法) 算法) function [min,path]=dijkstra(w,start,terminal) function [min,path]=dijkstra(w,start,terminal) n=size(w,1); label(start)=0; f(start)=start; n=size(w,1); label(start)=0;