最短路径问题

最短路径问题摘要在图论当中，任意两点间的最短路径问题，运用Dijkstra算法，Flord算法,匈牙利算法等都可以就解决这类相关问题,本文主要就是运用图论相关知识，来分析问题的。在问题一中，需要为货车司机选择一条从地点1到地点11的最短时间问题，其实际归结为求一个两点间最短路径问题，运用运筹学中的网络模型相关知识，建立了一个一个0-1线性模型，并最终求的其结果，最短时间为21，货车司机的运输路线为VtVtVtVtV。1891011运用Floyd算法解决问题二，并且运用Matlab软件编程,Floyd算法与Matlab软件编程所得出的结果一致，最后得出了一个最短航程表，及任意两点间的最短航程图。本文的最大亮点在于将问题二进行更深一步的拓展，从问题实际出发，从公司的差旅费用最小出发，利用Mtlab软件编程的出了公司到个城市间差旅费用最小图，从而更能为公司节省成本。C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80任意城市间差旅费用最小其次是本文结果的准确性，问题一运用Lingo软件编程，和WinQSB软件，所得出结果都是一致的，问题二更是运用Floyd算法，Matlab软件编程，WinQSB软件，大大地保证了结果的准确性，并且十分恰当地运用WinQSB软件将作图功能，把每一提的最短路径都清晰的描绘出来，更加直观地将结果展现出来。关键字：MatlabLingoWinQSBFloyd算法0-1规划#附录五问题二在进行Floydj算法进行插值时，每次插值所发生的选择路径的变化：P3=r112111、r11@111、P3=r112111、r11@111、2222[32222202233332@33330PA=「44444444444445[355515[4555gV662616丿v6606@6丿11p51国国1224333444455564641]2444V605511'2242333444444555464646丿r111111「「11111]222212222212343434343434P2二回434343434回4515551515551V666616丿「V66回616丿附录六问题二用Matlab软件编程程序与运行结果：>>clear>>n=6;>>a=zeros(n);>>a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;>>a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;>>a(4,5)=10;a(4,6)=25;a(5,6)=55;>>a=a+a';M=max(max(a))*M2;%M为充分大的正实数>>a=a+((a==0)-eye(n))*M;>>path=zeros(n);>>fork=1:nfori=1:n

forj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendend>>a,path运行结果：a,patha=035453525103501520302545150102035352010010252530201003510253525350path=065600065600500500040004500040004000001010附录七问题二的拓展用Matlab软件编程程序与运行结果：>>n=6;>>a=zeros(n);>>a(1,2)=69.5;a(1,4)=61;a(1,5)=34;a(1,6)=16;>>a(2,1)=71;a(2,3)=24;a(2,4)=32;a(2,6)=40;>>a(3,2)=24;a(3,4)=16;a(3,5)=32;>>a(4,1)=53.5;a(4,2)=32;a(4,3)=16;a(4,5)=16;a(4,6)=38.5;>>a(5,1)=34;a(5,3)=27.5;a(5,4)=16;a(5,6)=76;>>a(6,1)=14.8;a(6,2)=35.5;a(6,4)=34.3;a(6,5)=76;>>M=max(max(a))*n^2;>>a=a+((a==0)-eye(n))*M;>>path=zeros(n);>>fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendend>>a,path问题二拓展Matlab运行结果a=051.500061.500050.000034.000016.000054.8000024.000032.000048.000040.000066.000024.0000016.000032.000054.500050.000032.000016.0000016.000038.500034.