Page 214 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

path=0；
w=0；

@text(mydata1.txt)=@writefor(nodes(i)：@writefor(nodes(j)：
@format(w(i，j)，’ 10.0f’))，@newline(1))；
@text(mydata1.txt)=@write(@newline(1))；
@text(mydata1.txt)=@writefor(nodes(i)：@writefor(nodes(j)：
@format(path(i，j)，’ 10.0f’))，@newline(1))；
enddata

calc：
w(1，2)=50；w(1，4)=40；w(1，5)=25；w(1，6)=10；

w(2，3)=15；w(2，4)=20；w(2，6)=25；
w(3，4)=10；w(3，5)=20；
w(4，5)=10；w(4，6)=25；w(5，6)=55；
@for(link(i，j)：w(i，j)=w(i，j)+w(j，i))；
@for(link(i，j) |i#ne#j：w(i，j)=@if(w(i，j)#eq#0，10000，w(i，j)))；

@for(nodes(k)：@for(nodes(i)：@for(nodes(j)：
tm=@smin(w(i，j)，w(i，k)+w(k，j))；
path(i，j)=@if(w(i，j)#gt# tm，k，path(i，j))；w(i，j)=tm)))；
endcalc

end
我们编写的求起点 sb 到终点 db 通用的 Floyd 算法程序如下：
function [dist，mypath]=myfloyd(a，sb，db)；
% 输入：a—邻接矩阵 (aij) 是指 i 到 j 之间的距离，可以是有向的

% sb—起点的标号；db—终点的标号
% 输出：dist—最短路的距离；% mypath—最短路的路径
n=size(a，1)； path=zeros(n)；
for i=1：n

for j=1：n
if a(i，j)~=inf
path(i，j)=j； %j 是 i 的后续点

204