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

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

[i，j] = find(s1 == q2 | s2 == q2)；
s1 = [s1；i]；
s2 = [s2；j]；

w = w + pl；
k = k + 1；
T(q2，：) = inf；
T(：，q2) = inf；
end

E = [s1；s2]；
end
3.Ford 最短路算法

该算法用于求解一个赋权图中 s 到 t 的最短路，并且对于权值的情况同样
适用。
function [w，v] = Ford(W，s，t)
% W 为带权邻接矩阵，s 起点，t 终点

% 返回值 w 为最短路的权值之和，v 为最短路线上的顶点标号
n=length(W)；
d=W(s，：)； % d(v)=min{d(u)+w(u，v)} 的解，用 d 存放 vj 的初值为 W
的第 s 行，以存放 d(vj)，赋初值为 W 的第 s 行，以存放 d(vj)

v=s；
while true
b=d；
for i=1：n

b(i)=min(W(：，i)+d(i))；
end
d=[d；b]；

if all(d(end，：)==d(end-1，：)) % 找到最短路，跳出循环
break；
end
end

102