最短路径问题数学建模幻灯片.ppt

《最短路径问题数学建模幻灯片.ppt》由会员分享，可在线阅读，更多相关《最短路径问题数学建模幻灯片.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、最短路径问题数学建模Gong Qu1第1页，共31页，编辑于2022年，星期六主要内容主要内容Floyd算法Dijkstra算法两个例子的求解引例2：最廉价航费表的制定引例1：最短运输路线问题最短路径问题的0-1规划模型2第2页，共31页，编辑于2022年，星期六如如如如图图图图的的的的交交交交通通通通网网网网络络络络，每每每每条条条条弧弧弧弧上上上上的的的的数数数数字字字字代代代代表表表表车车车车辆辆辆辆在在在在该该该该路路路路段段段段行行行行驶驶驶驶所所所所需需需需的的的的时时时时间间间间，有有有有向向向向边边边边表表表表示示示示单单单单行行行行道道道道，无无无无向向向向边边边边表表表表示

2、示示示可可可可双双双双向向向向行行行行驶驶驶驶。若若若若有有有有一一一一批批批批货货货货物物物物要要要要从从从从1 1 1 1号号号号顶顶顶顶点点点点运运运运往往往往11111111号号号号顶顶顶顶点点点点，问问问问运运运运货货货货车车车车应应应应沿沿沿沿哪哪哪哪条条条条线线线线路路路路行驶，才能最快地到达目的地？行驶，才能最快地到达目的地？行驶，才能最快地到达目的地？行驶，才能最快地到达目的地？引例引例1 1：最短运输路线问题最短运输路线问题 102374116598135122106158879932273第3页，共31页，编辑于2022年，星期六 某某某某公公公公司司司司在在在在六六六六

3、个个个个城城城城市市市市C C C C1 1 1 1,C,C,C,C2 2 2 2,C,C,C,C3 3 3 3,C,C,C,C4 4 4 4,C,C,C,C5 5 5 5,C,C,C,C6 6 6 6都都都都有有有有分分分分公公公公司司司司，公公公公司司司司成成成成员员员员经经经经常常常常往往往往来来来来于于于于它它它它们们们们之之之之间间间间，已已已已知知知知从从从从CiCiCiCi到到到到C C C Cj j j j的的的的直直直直达达达达航航航航班班班班票票票票价价价价由由由由下下下下述述述述矩矩矩矩阵阵阵阵的的的的第第第第i i行行行行，第第第第j j列列列列元元元元素素素素给给给给

4、出出出出（表表表表示示示示无无无无直直直直达达达达航航航航班班班班），该该该该公公公公司想算出一张任意两个城市之间的最廉价路线航费表。司想算出一张任意两个城市之间的最廉价路线航费表。司想算出一张任意两个城市之间的最廉价路线航费表。司想算出一张任意两个城市之间的最廉价路线航费表。引例引例2 2：最廉价航费表的制定最廉价航费表的制定 4第4页，共31页，编辑于2022年，星期六最短路径问题l定义：设定义：设P(u,v)是加权图是加权图G中从中从u到到v的路径的路径,则该路径上则该路径上的边权之和称为该路径的权的边权之和称为该路径的权,记为记为w(P).从从u到到v的路径中的路径中权最小者权最小者

5、P*(u,v)称为称为u到到v的最短路径的最短路径.102374116598135122106158879932275第5页，共31页，编辑于2022年，星期六最短路径算法Dijkstra算法算法使用范围使用范围使用范围使用范围:1)1)寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径;2)2)有向图、无向图和混合图有向图、无向图和混合图有向图、无向图和混合图有向图、无向图和混合图;3)3)权非负权非负权非负权非负.算法思路：算法思路：算法思路：算法思路：采用标号作业法采用标号作业法采用标号作业法采

6、用标号作业法,每次迭代产生一个永久标号每次迭代产生一个永久标号每次迭代产生一个永久标号每次迭代产生一个永久标号,从而生从而生从而生从而生长一颗以长一颗以长一颗以长一颗以v v0 0为根的最短路树为根的最短路树为根的最短路树为根的最短路树,在这颗树上每个顶点与根在这颗树上每个顶点与根在这颗树上每个顶点与根在这颗树上每个顶点与根节点之间的路径皆为最短路径节点之间的路径皆为最短路径节点之间的路径皆为最短路径节点之间的路径皆为最短路径.102374116598135122106 158879932276第6页，共31页，编辑于2022年，星期六Dijkstra算法算法算法步骤算法步骤S:具有永久标号的

7、顶点集具有永久标号的顶点集;l(v):v的标记的标记;f(v):v的父顶点的父顶点,用以确定最短路径用以确定最短路径;输入加权图的带权邻接矩阵输入加权图的带权邻接矩阵w=w(vi,vj)nxm.1)初始化初始化 令令l(v0)=0,S=;v v0,l(v)=;2)更新更新l(v),f(v)3)寻找不在寻找不在S中的顶点中的顶点u,使使l(u)为最小为最小.把把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),直到所有顶点都在直到所

8、有顶点都在S中为止中为止.7第7页，共31页，编辑于2022年，星期六MATLAB程序（程序（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;f(start)=start;for i=1:nfor i=1:n if i=start if i=start label(i)=inf;label(i)=inf;

9、end,endend,ends(1)=start;u=start;s(1)=start;u=start;while length(s)nwhile length(s)(label(u)+w(u,v)if label(v)(label(u)+w(u,v)label(v)=(label(u)+w(u,v);f(v)=u;label(v)=(label(u)+w(u,v);f(v)=u;end,end,end end,end,end v1=0;v1=0;k=inf;k=inf;for i=1:n for i=1:n ins=0;ins=0;for j=1:length(s)for j=1:lengt

10、h(s)if i=s(j)if i=s(j)ins=1;ins=1;end,end end,end if ins=0 if ins=0 v=i;v=i;if klabel(v)if klabel(v)k=label(v);v1=v;k=label(v);v1=v;end,end,end end,end,end s(length(s)+1)=v1;s(length(s)+1)=v1;u=v1;u=v1;endendmin=label(terminal);min=label(terminal);path(1)=terminal;path(1)=terminal;i=1;i=1;while path

11、(i)=startwhile path(i)=start path(i+1)=f(path(i);path(i+1)=f(path(i);i=i+1;i=i+1;endend path(i)=start;path(i)=start;L=length(path);L=length(path);path=path(L:-1:1);path=path(L:-1:1);8第8页，共31页，编辑于2022年，星期六最短路径算法Dijkstra算法程序的使用说明：算法程序的使用说明：调用格式为调用格式为调用格式为调用格式为 min,path=dijkstra(w,start,terminal)min,pa

12、th=dijkstra(w,start,terminal),其中输入变量其中输入变量其中输入变量其中输入变量w w为所求图的带权邻接矩阵，为所求图的带权邻接矩阵，为所求图的带权邻接矩阵，为所求图的带权邻接矩阵，start,terminalstart,terminal分分分分别为路径的起点和终点的号码。别为路径的起点和终点的号码。别为路径的起点和终点的号码。别为路径的起点和终点的号码。返回返回返回返回startstart到到到到terminalterminal的最短路的最短路的最短路的最短路径径径径pathpath及其长度及其长度及其长度及其长度min.min.注意：顶点的编号从注意：顶点的编号

13、从注意：顶点的编号从注意：顶点的编号从1 1开始连续编号。开始连续编号。开始连续编号。开始连续编号。9第9页，共31页，编辑于2022年，星期六最短路径算法Floyd算法算法使用范围使用范围使用范围使用范围:1)1)求每对顶点的最短路径求每对顶点的最短路径求每对顶点的最短路径求每对顶点的最短路径;2)2)有向图、无向图和混合图有向图、无向图和混合图有向图、无向图和混合图有向图、无向图和混合图;算法思想算法思想算法思想算法思想:直接在图的带权邻接矩阵中用插入顶点的方法依次递推直接在图的带权邻接矩阵中用插入顶点的方法依次递推直接在图的带权邻接矩阵中用插入顶点的方法依次递推直接在图的带权邻接矩阵中用

14、插入顶点的方法依次递推地构造出地构造出地构造出地构造出n n个矩阵个矩阵个矩阵个矩阵D(1),D(2),D(n),D(n)D(1),D(2),D(n),D(n)是图的距离矩是图的距离矩是图的距离矩是图的距离矩阵阵阵阵,同时引入一个后继点矩阵记录两点间的最短路径同时引入一个后继点矩阵记录两点间的最短路径同时引入一个后继点矩阵记录两点间的最短路径同时引入一个后继点矩阵记录两点间的最短路径.102374116598135122106 1588799322710第10页，共31页，编辑于2022年，星期六Floyd算法算法算法步骤算法步骤 d(i,j):i到到j的距离的距离;path(i,j):i到到

15、j的路径上的路径上i的后继点的后继点;输入带权邻接矩阵输入带权邻接矩阵a(i,j).1）赋初值）赋初值 对所有对所有i,j,d(i,j)a(i,j),path(i,j)j,k=l.2）更新）更新d(i,j),path(i,j)对所有对所有i,j,若若d(i,k)+d(k,j)d(i,j),则则 d(i,j)d(i,k)+d(k,j),path(i,j)path(i,k),k k+13）重复）重复2)直到直到k=n+111第11页，共31页，编辑于2022年，星期六MATLAB程序（程序（Floyd算法）算法）function D,path,min1,path1=floyd(a,start,te

16、rminal)function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);D=a;n=size(D,1);path=zeros(n,n);for i=1:nfor i=1:n for j=1:n for j=1:n if D(i,j)=inf if D(i,j)=inf path(i,j)=j;path(i,j)=j;end,end,endend,end,endfor k=1:nfor k=1:n for i=1:n for i=1:n for j=1:n for j=1:n if D(i,

17、k)+D(k,j)D(i,j)if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);path(i,j)=path(i,k);end,end,end,endend,end,end,endif nargin=3if nargin=3 min1=D(start,terminal);min1=D(start,terminal);m(1)=start;m(1)=start;i=1;i=1;path1=;path1=;while path(m(i),terminal)=terminal whi

18、le path(m(i),terminal)=terminal k=i+1;k=i+1;m(k)=path(m(i),terminal);m(k)=path(m(i),terminal);i=i+1;i=i+1;end end m(i+1)=terminal;m(i+1)=terminal;path1=m;path1=m;end end 12第12页，共31页，编辑于2022年，星期六最短路径算法Floyd算法程序的使用说明：算法程序的使用说明：1.D,path=floyd(a),1.D,path=floyd(a),返回矩阵返回矩阵返回矩阵返回矩阵D,path D,path。其中。其中。其中。

19、其中a a是所求图的带是所求图的带是所求图的带是所求图的带权邻接矩阵，权邻接矩阵，权邻接矩阵，权邻接矩阵，D(i,j)D(i,j)表示表示表示表示i i到到到到j j的最短距离的最短距离的最短距离的最短距离;path(i,j);path(i,j)表示表示表示表示i i与与与与j j之间的最短路径上顶点之间的最短路径上顶点之间的最短路径上顶点之间的最短路径上顶点i i的后继点的后继点的后继点的后继点.2.D,path,min1,path1=floyd(a,i,j)2.D,path,min1,path1=floyd(a,i,j)返回矩阵返回矩阵返回矩阵返回矩阵D,path;D,path;并返并返并

20、返并返回回回回i i与与与与j j之间的最短距离之间的最短距离之间的最短距离之间的最短距离min1min1和最短路径和最短路径和最短路径和最短路径path1.path1.13第13页，共31页，编辑于2022年，星期六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;.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,4,2,7,5,3,5,11,7,6,7,5

21、,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;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);n=11;weight=inf*ones(n,n);for i=1:nfor i=1:n weight(i,i)=0;weight(i,i)=0;endendfor i=1:size(edge,2)for i=1:size(edge,2)weight(edge(1,i),edge(2,

22、i)=edge(3,i);weight(edge(1,i),edge(2,i)=edge(3,i);endenddis,path=dijkstra(weight,1,11)dis,path=dijkstra(weight,1,11)引例引例1 1的的MatlabMatlab求解求解10237411659813 35 512122 210106 61 15 58 88 87 79 99 93 32 22 27 714第14页，共31页，编辑于2022年，星期六运行上页程序输出：运行上页程序输出：dis=21path=1 8 9 10 11 因此顶点因此顶点1到顶点到顶点11的最短路径为的最短路径

23、为18 9 10 11,其长度为其长度为21。引例引例1 1的求解的求解15第15页，共31页，编辑于2022年，星期六建立脚本建立脚本建立脚本建立脚本mm文件如下：文件如下：文件如下：文件如下：a=0,50,inf,40,25,10;50,0,15,20,inf,25;inf,15,0,10,20,inf;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;40,20,10,0,10,25;25,inf,20,10,0,55;

24、10,25,inf,25,55,0;D,path=floyd(a)D,path=floyd(a)运行便可输出结果。运行便可输出结果。运行便可输出结果。运行便可输出结果。引例引例2 2的的MatlabMatlab求解求解16第16页，共31页，编辑于2022年，星期六运行输出结果：运行输出结果：运行输出结果：运行输出结果：D=D=0 35 45 35 25 10 0 35 45 35 25 10 35 0 15 20 30 25 35 0 15 20 30 25 45 15 0 10 20 35 45 15 0 10 20 35 35 20 10 0 10 25 35 20 10 0 10 25

25、 25 30 20 10 0 35 25 30 20 10 0 35 10 25 35 25 35 0 10 25 35 25 35 0path=path=1 6 5 5 5 6 1 6 5 5 5 6 6 2 3 4 4 6 6 2 3 4 4 6 5 2 3 4 5 4 5 2 3 4 5 4 5 2 3 4 5 6 5 2 3 4 5 6 1 4 3 4 5 1 1 4 3 4 5 1 1 2 4 4 1 6 1 2 4 4 1 6D D便是最廉价的航费表，要求飞便是最廉价的航费表，要求飞便是最廉价的航费表，要求飞便是最廉价的航费表，要求飞行路线，由行路线，由行路线，由行路线，由path

26、path矩阵可以得矩阵可以得矩阵可以得矩阵可以得到，比如到，比如到，比如到，比如2 2到到到到5 5的路线：的路线：的路线：的路线：path(2,5)=4,path(4,5)=5,path(2,5)=4,path(4,5)=5,因因因因此，应为此，应为此，应为此，应为24 524 517第17页，共31页，编辑于2022年，星期六 假设图有假设图有 n 个顶点，现需要求从顶点个顶点，现需要求从顶点1到顶点到顶点n的最的最短路径短路径.最短路径问题的最短路径问题的0-10-1规划模型规划模型 设决策变量为设决策变量为xij,当顶点当顶点1至顶点至顶点n的路上含弧的路上含弧(i,j)时，时，xij

27、=1；否则；否则xij=0.其数学规划表达式为其数学规划表达式为18第18页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 例例（有向图最短路问题）（有向图最短路问题）在下图中，用点表示城市，现有在下图中，用点表示城市，现有 共共7个城市个城市.点与点之间的连线表示城市间有道路相连点与点之间的连线表示城市间有道路相连.连线旁的数字表连线旁的数字表示道路的长度示道路的长度.现计划从城市现计划从城市 到城市到城市 铺设一条天然气管道，请铺设一条天然气管道，请设计出最小价格管道铺设方案设计出最小价格管道铺设方案.本质是求从城市本质是求从城市 到城市到城市

28、 的一条最短路的一条最短路19第19页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 解：解：写出相应的写出相应的LINGO程序，程序，MODEL:1!We have a network of 7 cities.We want to find 2 the length of the shortest route from city 1 to city 7;3 4sets:5 !Here is our primitive set of seven cities;6 cities/A,B1,B2,C1,C2,C3,D/;7 8 !The Derived

29、 set roads lists the roads that 9 exist between the cities;20第20页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 10 roads(cities,cities)/11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/:w,x;13 endsets 14 15 data:16 !Here are the distances that correspond 17 to above links;18 w=2 4

30、3 3 1 2 3 1 1 3 4;19 enddata 21第21页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 20 21 n=size(cities);!The number of cities;22 min=sum(roads:w*x);23 for(cities(i)|i#ne#1#and#i#ne#n:24 sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);25 sum(roads(i,j)|i#eq#1:x(i,j)=1;END22第22页，共31页，编辑于2022年，星期六最短路径问题的最短路

31、径问题的0-10-1规划模型规划模型 在上述程序中，在上述程序中，21句中的句中的n=size(cities)是计算集是计算集cities的个数，这里的计算结果是的个数，这里的计算结果是 ,这样编写方法目的这样编写方法目的在于提高程序的通用性在于提高程序的通用性.22句表示目标函数句表示目标函数,即求道路的最即求道路的最小权值小权值.23,24句表示约束中句表示约束中 的情况，即最短路中的情况，即最短路中中间点的约束条件中间点的约束条件.25句表示约束中句表示约束中 的情况，即最短的情况，即最短路中起点的约束路中起点的约束.约束中约束中 的情况，也就是最短路中终点的情况，没的情况，也就是最短路

32、中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关有列在程序中，因为终点的约束方程与前个方程相关.当当然，如果你将此方程列入到然，如果你将此方程列入到LINGO程序中，计算时也程序中，计算时也不会出现任何问题，因为不会出现任何问题，因为LINGO软件可以自动删除描软件可以自动删除描述线性规划可行解中的多余方程述线性规划可行解中的多余方程.23第23页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 LINGO软件计算结果（仅保留非零变量）如下软件计算结果（仅保留非零变量）如下Global optimal solution found at

33、 iteration:0 Objective value:6.000000 Variable Value Reduced Cost X(A,B1)1.000000 0.000000 X(B1,C1)1.000000 0.000000 X(C1,D)1.000000 0.000000 即最短路是即最短路是 ,最短路长为最短路长为6个单位个单位.24第24页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 例例（无向图的最短路问题）求下图中（无向图的最短路问题）求下图中 到到 的最短路的最短路.本本例例是是处处理理无无向向图图的的最最短短路路问问题题，在

34、在处处理理方方式式上上与与有有向向图图的的最最短短路路有有一些差别一些差别.25第25页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 解：解：对于无向图的最短路问题，可以这样理解，从点对于无向图的最短路问题，可以这样理解，从点 到点到点 和点和点 到点到点 的边看成有向弧，其他各条边均看成有的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写问题来编程序，但按照这种方法编写LINGO程序相当于边程序相当于边（弧）增加了一倍（弧）增

35、加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序程序.MODEL:1 sets:2 cities/1.11/;3 roads(cities,cities):p,w,x;4 endsets 26第26页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 5 data:6 p=0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0

36、 11 0 0 1 0 1 0 1 0 1 0 0 12 0 0 1 1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0;27第27页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 17 w=0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0

37、0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0 3 0 4 0 6 0 0 23 0 0 2 9 0 4 0 0 3 1 0 24 0 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0;28 enddata28第28页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 29n=size(cities);30min=sum(roads:w*x);31for(cities(i)|i#

38、ne#1#and#i#ne#n:32 sum(cities(j):p(i,j)*x(i,j)33 =sum(cities(j):p(j,i)*x(j,i);34sum(cities(j):p(1,j)*x(1,j)=1;END29第29页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 在上述程序中在上述程序中，第，第6行到第行到第16行给出了图的邻接矩阵行给出了图的邻接矩阵 ，到到 和和 到到 的边按单向计算，其余的边按单向计算，其余边双向计算边双向计算.第第17行到第行到第27行给出了图的赋权矩阵行给出了图的赋权矩阵 ,注意：注意：由于有了邻接矩

39、阵由于有了邻接矩阵 ，两点无道路连接时，权值可以定义，两点无道路连接时，权值可以定义为为0.其它的处理方法基本上与有向图相同其它的处理方法基本上与有向图相同.用用LINGO软件求解，得到（仅保留非零变量）软件求解，得到（仅保留非零变量）Global optimal solution found at iteration:2 0 Objective value:13.00000 30第30页，共31页，编辑于2022年，星期六最短路径问题的最短路径问题的0-10-1规划模型规划模型 Variable Value Reduced Cost X(1,2)1.000000 0.000000 X(2,5)1.000000 0.000000 X(3,7)1.000000 0.000000 X(5,6)1.000000 0.000000 X(6,3)1.000000 0.000000 X(7,10)1.000000 0.000000 X(9,11)1.000000 0.000000 X(10,9)1.000000 0.000000 即最短路径为即最短路径为最短路长度为最短路长度为13.31第31页，共31页，编辑于2022年，星期六