图论是应用数学的一个分支(2)

在古代有这样的难题：哥尼斯堡七桥问题、棋盘上马的行走路线问题、汉米尔顿（环游世界）数学难题等等;而在实际生活中，我们也会遇到这样的问题，当需要走的路径很多时，如何寻找最优路径，因为这样不仅耗时短，还方便。这些都和图论有所关联，图论利用图作为研究对象，从而解决一些问题、难题。而最短路问题就是图论理论上的一个经典问题，寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等很多方面。

通过操作发现可以很方便的解决此类问题。尤其是在路线安排、厂区布局中的应用具有很重要的意义。图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断的更新，从而为人们提供方便，减少计算量。

参考文献

[1] 朱顺泉、苏越良。《管理运筹建模与求解》。清华大学出版社，2011.6:192页-194页

[2]胡运权主编，《运筹学教程》，清华大学出版社，2011.6：242页-247页 [3]张德全，吴果林等.最短路问题的Floyd加速算法与优化 2009年17期：41页-46页

5

附录：

Matlab程序命令：

%floyd算法，

function [D,path,min1,path1]=floyd(a,start,terminal) %a是邻接矩阵 %start是起始点 %terminal是终止点 %D是最小权值表

%path是最短路线表。 D=a;n=size(D,1); path=zeros(n,n); for i=1:n for j=1:n

if D(i,j)~=inf

path(i,j)=j; end end end

for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end end end

if nargin==3

min1=D(start,terminal); m(1)=start; i=1;

path1=[ ];

while path(m(i),terminal)~=terminal

k=i+1; m(k)=path(m(i),terminal); i=i+1; end

m(i+1)=terminal; path1=m;

6

end

问题一的求解结果：

a= [0,2,9,inf,inf,inf,inf, inf,0,6,8,inf,inf,inf, inf,inf,0,1,3,inf,inf, inf,inf,inf,0,4,3.5,inf, inf,inf,inf,inf,0,inf,2.5, inf,inf,inf,inf,inf,0,5, inf,inf,inf,inf,inf,inf,inf,]; [D, path]=floyd(a) D =

0 2.0000 8.0000 13.5000

Inf 0 6.0000 11.5000

Inf Inf 0 5.5000

Inf Inf Inf 6.5000

Inf Inf Inf 2.5000

Inf Inf Inf 5.0000

Inf Inf Inf Inf path =

1 2 2 2 2 2 2 0 2 3 3 3 3 3 0 0 3 4 5 4 5

7

9.0000 7.0000 1.0000 0 Inf 9.0000 3.0000 4.0000 0 Inf Inf 4.5000 3.5000 Inf 0 Inf 11.0000 12.5000 10.5000 Inf Inf 0 0 0 4 5 6 5 0 0 0 0 5 0 7 0 0 0 0 0 6 7 0 0 0 0 0 0 0 问题二的求解结果：

>> a= [0,475,485,inf,inf,inf,inf, inf,0,200,425,520,inf,inf, inf,inf,0,440,490,650,inf, inf,inf,inf,0,150,inf,615, inf,inf,inf,inf,0,150,425, inf,inf,inf,inf,inf,0,490, inf,inf,inf,inf,inf,inf,inf,]; [D, path]=floyd(a) D =

0 475 1125 1400

Inf 0 670 945

Inf Inf 640 915

Inf Inf 300 575

Inf Inf 150 425

Inf Inf 0 490

Inf Inf Inf Inf

485 0 440 Inf Inf Inf Inf Inf 8

900 0 Inf 975 150 Inf Inf 200 425 520 490 0 Inf path =

1 2 3 2 3 3 3 0 2 3 4 5 5 5 0 0 3 4 5 5 5 0 0 0 4 5 5 5 0 0 0 0 5 6 7 0 0 0 0 0 6 7 0 0 0 0 0 0 0

9

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论是应用数学的一个分支(2)在线全文阅读。