最短路径问题-数学建模.ppt

Gong Qu edge= [ 2,3,1,3,3,5,4, 4,1,7,6,6,5, 5,11, 1,8,6,9,10,8,9, 9,10;... 3,4,2,7,5,3,5,11,7,6,7,5,6,11, 5, 8,1,9,5,11,9,8,10,9;... 3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7, 2, 9,9, 2, 2]; n=11; weight=inf*ones(n, n); for i=1:n weight(i, i)=0; end for i=1:size(edge,2) weight(edge(1, i), edge(2, i))=edge(3, i); end [dis, path]=dijkstra(weight, 1, 11) 运行上页程序输出： dis = 21 path = 1 8 9 10 11 因此顶点1到顶点11的最短路径为1→8 →9 →10 →11, 其长度为21。 建立脚本m文件如下： a= [ 0,50,inf,40,25,10;50,0,15,20,inf,25;inf,15,0,10,20,inf;… 40,20,10,0,10,25;25,inf,20,10,0,55;10,25,inf,25,55,0]; [D, path]=floyd(a) 运行便可输出结果。 运行输出结果： D = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25 35 0 path = 1 6 5 5 5 6 6 2 3 4 4 6 5 2 3 4 5 4 5 2 3 4 5 6 1 4 3 4 5 1 1 2 4 4 1 6 假设图有 n 个顶点，现需要求从顶点1到顶点n的最短路径. * * 最短路径问题 参考书： 1.傅鹂 龚劬 刘琼荪 何中市 《数学实验》科学出版社 2.张绍民 李淑华 《数据结构教程C语言版》中国电力出版社 主讲：重庆大学 龚 劬 主要内容 Floyd算法 Dijkstra算法 两个例子的求解 引例2：最廉价航费表的制定 引例1：最短运输路线问题 最短路径问题的0-1规划模型 如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？ 引例1：最短运输路线问题 10 2 3 7 4 11 6 5 9 8 1 3 5 12 2 10 6 1 5 8 8 7 9 9 3 2 2 7 某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（?表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。 引例2：最廉价航费表的制定 最短路径问题 定义：设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P). 从u到v的路径中权最小者 P*(u,v)称为u到v的最短路径. 10 2 3 7 4 11 6 5 9 8 1 3 5 12 2 10 6 1 5 8 8 7 9 9 3 2 2 7 最短路径算法 Dijkstra算法 使用范围: 寻求从一固定顶点到其余各点的最短路径; 有向图、无向图和混合图; 权非负. 算法思路： 采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径. 10 2 3 7 4 11 6 5 9 8 1 3 5 12 2 10 6 1 5 8 8 7 9 9 3 2 2 7 Dijkstra算法——算法步骤