数学建模floyd算法最短路算法详解

最短路算法任意一对顶点之间的最短路算法:Floyd算法(二)算法原理1、求距离矩阵的方法2、求路径矩阵的方法3、查找最短路路径的方法（一）算法的基本思想（三）算法步骤算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵D(1)、D(2)、…、D()，使最后得到的矩阵D()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径．算法原理——求距离矩阵的方法把带权邻接矩阵W作为距离矩阵的初值，即D(0)=)()0(ijd=W（１）D(1)=)()1(ijd，其中)0(1)0()1(,min{iijijddd})0(1jd)1(ijd是从vi到vj的只允许以v1作为中间点的路径中最短路的长度．（2）D(2)=)()2(ijd，其中)1(2)1()2(,min{iijijddd})1(2jd)2(ijd是从vi到vj的只允许以v1、v2作为中间点的路径中最短路的长度．…（）D()=)()(ijd，其中)1()1()(,min{iijijddd})1(jd)(ijd是从vi到vj的只允许以v1、v2、…、v作为中间点的路径中最短路的长度．即是从vi到vj中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵．算法原理——求路径矩阵的方法R=)(ijr,rij的含义是从vi到vj的最短路要经过点号为rij的点．)()0()0(ijrR,jrij)0(每求得一个D(k)时，按下列方式产生相应的新的R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵R．即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．)(D)(R)(Rij算法原理——查找最短路路径的方法若1)(prij，则点p1是点i到点j的最短路的中间点.然后用同样的方法再分头查找．若：（１）向点i追朔得：2)(1prip,3)(2prip,…,kipprk)(（２）向点j追朔得：1)(1qrjp,2)(1qrjq,…,jrjqm)(pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,,,,,,,,21,12算法步骤Floyd算法：求任意两点间的最短路．D(i,j)：i到j的距离．R(i,j)：i到j之间的插入点．输入:带权邻接矩阵w(i,j)（１）赋初值：对所有i,j,d(i,j)w(i,j),r(i,j)j,k1(2)更新d(i,j),r(i,j)对所有i,j，若d(i,k)+d(k,j)d(i,j)，则d(i,j)d(i,k)+d(k,j),r(i,j)k(3)若k=，停止．否则kk+1，转（２）．自定义floyd函数function[d,r]=floyd(w)n=length(w);fori=1:nforj=1:nd(i,j)=w(i,j);r(i,j)=j;endendfork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=k;endendendend例1求下图中加权图的任意两点间的距离与路径．5333434331543243332444441,0646960243420256420793570RD951d，故从v5到v1的最短路为９．51r＝４．由v4向v5追朔：3,35354rr;由v4向v1追朔：141r所以从v5到v1的最短路径为：1435.clear;w=[0,9,inf,3,inf;9,0,2,inf,7;inf,2,0,2,4;3,inf,2,0,inf;inf,7,4,inf,0];[d,r]=floyd(w)（2）计算在各点iv设立服务设施的最大服务距离)(ivS．}{max)(1ijjidvS,2,1i选址问题--中心问题例2　某城市要建立一个消防站，为该市所属的七个区服务，如图所示．问应设在那个区，才能使它至最远区的路径最短．（1）用Floyd算法求出距离矩阵D=)(ijd．（3）求出顶点kv，使)}({min)(1iikvSvS则kv就是要求的建立消防站的地点．此点称为图的中心点．clear;w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0];[d,r]=floyd(w)S=max(d’)%求矩阵各列的最大值s=min(S)05.15.55.86475.10475.45.25.55.54032475.8730571065.42502545.24720375.5710530DS(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。选址问题--重心问题例3　某矿区有七个矿点，如图所示．已知各矿点每天的产矿量)(jvq（标在图的各顶点上）．现要从这七个矿点选一个来建造矿厂．问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小．（1）求距离阵D=)(ijd．（2）计算各顶点作为选矿厂的总运力)(ivmijjjidvqvm)()(1,2,1i（3）求kv使)}({min)(1iikvmvm，则kv就是选矿厂应设之矿点．此点称为图G的重心或中位点．clear;w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,inf,4,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,1,inf,inf;inf,inf,2,1,0,4,inf;inf,4,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0];[d,r]=floyd(w)q=[3,2,7,1,6,1,4];fori=1:7m1=0;forj=1:7m1=m1+q(j)*d(i,j);endm(i)=m1;endmmin(m)d=03.00005.00008.00007.00007.00008.50003.000002.00005.00004.00004.00005.50005.00002.000003.00002.00006.00007.50008.00005.00003.000001.00005.00006.50007.00004.00002.00001.000004.00005.50007.00004.00006.00005.00004.000001.50008.50005.50007.50006.50005.50001.50000m=13278709270106130ans=70实验八、最佳灾情巡视路线（节选部分）实验内容：求出下图中O到其它各点的最短路线（要求求出最短路线及其最短距离）（节选了教材上337面图中的16个点：即15、16、17、18、20、21、22、23、25、26、I、K、M、N、O、P等16个点）