ПРОЕКТИРОВАНИЕ ЭЛЕКТРИЧЕСКИХ ЖГУТОВ ЭЛЕКТРОТЕХНИЧЕСКИХ КОМПЛЕКСОВ ЛЕТАТЕЛЬНЫХ АППАРАТОВ С УЧЕТОМ ПЕРЕКРЕСТНЫХ ПОМЕХ. Проектирование электрических жгутов электротехнических комплексов летательных аппаратов с учетом перекрестных помех

• Название: Проектирование электрических жгутов электротехнических комплексов летательных аппаратов с учетом перекрестных помех
• Анкор: ПРОЕКТИРОВАНИЕ ЭЛЕКТРИЧЕСКИХ ЖГУТОВ ЭЛЕКТРОТЕХНИЧЕСКИХ КОМПЛЕКСОВ ЛЕТАТЕЛЬНЫХ АППАРАТОВ С УЧЕТОМ ПЕРЕКРЕСТНЫХ ПОМЕХ
• Дата: 15.06.2022
• Размер: 4.32 Mb.
• Имя файла: Dissertatsiya.pdf
• Тип: Диссертация; #594728
• страница: 7 из 8

%Function 1:
Определение емкости между проводником и землей function c=tinhc11(a,l,h)
esl=8.85*10^-12;
N=a/l+2*h/l-sqrt(1+(a/l)^2)-sqrt(1+(2*h/l)^2);
c0=(4*pi*esl*l)/(log(l/a+sqrt(1+(l/a)^2))+log(l/(2*h)+sqrt(
1+(l/(2*h))^2))+N);
c=c0/2;
end
%Function 2:
Определение емкости между проводниками 1 и 2 function
[ap1,ap2,ap3] = tinhc12(a1,a2,l1,l2,d)
esl=8.85*10^-12;
ap1=(1/(2*pi*esl*l1))*(log(l1/a1+sqrt((l1/a1)^2+1))+a1/l1- sqrt((a1/l1)^2+1));
ap2=(1/(2*pi*esl*l2))*(log(l2/a2+sqrt((l2/a2)^2+1))+a2/l2- sqrt((a2/l2)^2+1));
ap3=(1/(4*pi*esl*l2))*(asin((l1/d))+(l2/l1)*log(l2/d+sqrt((
l2/d)^2+1))-(l2/l1-1)*asin((l2-l1)/d)
+d/l1+sqrt((d/l1)^2+(l2/l1-1)^2)-sqrt((d/l1)^2+1)- sqrt((d/l1)^2+(l2/l1)^2));
end
%Function 3:
Определение индуктивности проводники function
L = dcL(a,l,f)
gm=5.81*10^7;
M0=4*pi*10^-7;
k=sqrt(2*pi*f*M0*gm); x=(k*a)/sqrt(8);
if k*a<3
Tt=1-x^4/6;
else
Tt=1/x-3/(64+x^3);
end
L=((M0*l)/(2*pi))*(log((4*l)/(2*a))-
1+Tt/4);
%L1=L1'=L2=L2' end
Приложение 1. 2: Oопределения пути электрического жгута на графе с минимальной суммарной длиной проводников clc;
clear;
L=11;
% общее количество вершин графа a12=2; a13=2; a14=2; a23=1; a25=2; a26=6; a27=4; a34=1; a35=4; a36=2; a37=4; a45=6; a46=4; a47=2; a56=1; a58=2; a59=4; a510=6;

122 a67=1; a68=4; a69=2; a610=4; a78=65; a79=4; a710=2; a89=1; a811=2; a910=1; a911=2; a1011=2;
%матрица количества проводников, соединяющих устройства n=[0 0 0 2 0 0 2 2 0 2 2;
0 0 0 0 0 0 2 2 0 0 0;
0 0 0 0 0 0 0 0 0 0 0;
2 0 0 0 2 0 2 2 0 0 2;
0 0 0 2 0 0 2 0 0 0 2;
0 0 0 0 0 0 0 0 0 0 0;
2 2 0 2 2 0 0 2 0 0 0;
2 2 0 2 0 0 2 0 0 2 0;
0 0 0 0 0 0 0 0 0 0 0;
2 0 0 0 0 0 0 2 0 0 0;
2 0 0 2 2 0 0 0 0 0 0];
% матрица расстояния между устройствами d=[inf a12 a13 a14 inf inf inf inf inf inf inf;
a12 inf a23 inf a25 a26 a27 inf inf inf inf;
a13 a23 inf a34 a35 a36 a37 inf inf inf inf;
a14 inf a34 inf a45 a46 a47 inf inf inf inf;
inf a25 a35 a45 inf a56 inf a58 a59 a510 inf;
inf a26 a36 a46 a56 inf a67 a68 a69 a610 inf;
inf a27 a37 a47 inf a67 inf a78 a79 a710 inf;
inf inf inf inf a58 a68 a78 inf a89 inf a811;
inf inf inf inf a59 a69 a79 a89 inf a910 a911;
inf inf inf inf a510 a610 a710 inf a910 inf a1011;
inf inf inf inf inf inf inf a811 a911 a1011 inf]
n1=10; n2=4; n3=0; n4=10; n5=6; n6=0; n7=10; n8=10; n9=0;n10=4;n11=6;
%матрица количества подключаемых проводников к каждому устройству
N=[n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11];
% матрица количество устройств на уровне
M0=[1];M1=[2 3 4]; M2=[5 6 7]; M3=[8 9 10]; M4=[11];
Mt=inf;
Ht=[];
H=[1];l=0;
Ndd=zeros(11,11);
P=zeros(11,11);
Q=zeros(11,11); D=zeros(L,L); for i=1:11
for j=1:11
[ M01 M02]=timM(M1,M2,M3,M4,i); [t,R]=mtranRT(M1,i); pij=ddaypT(d,N,M01,M02,R,i,j);Nij,bij]=timbnewT(d,N,n,M01,i
,j);
Ndd(i,j)=Nij;Q(i,j)=bij;P(i,j)=pij;Bij=bij+pij;
if
(ismember(i,M01)==1)&(ismember(j,M01)==1)
D(i,j)=inf;
elseif
(ismember(i,M02)==1)&(ismember(j,M02)==1)
D(i,j)=inf;
elseif
(i>j)|(Bij==0)

123
D(i,j)=inf;
else
D(i,j)=Bij end end end
D(1,1)=0; Nsd=Ndd;
Qb=Q; P=P; H=D; l=1; m=1;
A=[inf inf]; B=[1]; E=[];E1=[1]; E2=[11]; X=[]; minh=0;
%аллгорит Дейкстры пойска суммарной длины проводники
(
Б4)
while mif ismember(k,B)==0
A=[A;D(k,k) D(l,l)+D(l,k)]; else
A=[A;inf inf]; end end
A=A';[x,y]=min(A); for i=1:L
if ismember(i,B)==0
D(i,i)=x(i); end end
[z,h]=min(x); s=y(h); B=[B h]; minh=z; X=[X; x]; B1=X(:,h); B2=B1';
B3=find(B2==z); s1=B3(1); s2=B(s1);
E=[E; s2 h]; E1=E'; l=h; m=h; A=[inf inf];
end
E1=E1
;
s2=11;
while s2

=1
[c1 c2]=find(E1==s2); c1=c1'; c2=c2'; s4=size(c1); for t1=1:s4 if c1(t1)==1 s3=E1(2,c2(t1));
else s3=E1(1,c2(t1));
end if s3>=s2
E1(:,c2(t1))=[];s2=s2; else s2=s3; E2=[s3 E2]; E1(:,c2(t1))=[]; end end end
B=B
%
минимальной длиной проводников
Hmin=E2
%Путь жгута с минимальной длиной проводников disp([
'Lmin='
num2str(minh)])

124
Приложение 1.3: Oопределения пути электрического жгута на графе с минимальной суммарной длиной проводников с учетом перекрестных помех при условии, что путь прокладывания жгута проводников, соединяющих устройства 1 и 10 и путь прокладывания жгута проводников, соединяющих устройства 4 и 8 не могут проходить вместе clc;
clear;
L=11;
% общее количество вершин графа a12=2; a13=2; a14=2; a23=1; a25=2; a26=6; a27=4; a34=1; a35=4; a36=2; a37=4; a45=6; a46=4; a47=2; a56=1; a58=2; a59=4; a510=6; a67=1; a68=4; a69=2; a610=4; a78=6; a79=4; a710=2; a89=1; a811=2; a910=1; a911=2; a1011=2;
%матрица количества проводников, соединяющих устройства n=[0 0 0 2 0 0 2 2 0 2 2;
0 0 0 0 0 0 2 2 0 0 0;
0 0 0 0 0 0 0 0 0 0 0;
2 0 0 0 2 0 2 2 0 0 2;
0 0 0 2 0 0 2 0 0 0 2;
0 0 0 0 0 0 0 0 0 0 0;
2 2 0 2 2 0 0 2 0 0 0;
2 2 0 2 0 0 2 0 0 2 0;
0 0 0 0 0 0 0 0 0 0 0;
2 0 0 0 0 0 0 2 0 0 0;
2 0 0 2 2 0 0 0 0 0 0];
% матрица расстояния между устройствами (nxn); d= [inf a12 a13 a14 inf inf inf inf inf inf inf;
a12 inf a23 inf a25 a26 a27 inf inf inf inf;
a13 a23 inf a34 a35 a36 a37 inf inf inf inf;
a14 inf a34 inf a45 a46 a47 inf inf inf inf;
inf a25 a35 a45 inf a56 inf a58 a59 a510 inf;
inf a26 a36 a46 a56 inf a67 a68 a69 a610 inf;
inf a27 a37 a47 inf a67 inf a78 a79 a710 inf;
inf inf inf inf a58 a68 a78 inf a89 inf a811;
inf inf inf inf a59 a69 a79 a89 inf a910 a911;
inf inf inf inf a510 a610 a710 inf a910 inf a1011;
inf inf inf inf inf inf inf a811 a911 a1011 inf]; n1=10; n2=4; n3=0; n4=10; n5=6; n6=0; n7=10; n8=10; n9=0;n10=4;n11=6;
%матрица количества подключаемых проводников к каждому устройству
N= [n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11];
% матрица количество устройств на уровне (1xm)
M0= [1];M1=[2 3 4]; M2=[5 6 7]; M3=[8 9 10]; M4=[11];
Mt=inf; Ht=[]; H=[1]; l=0; u=1; w=10; p=4; q=8; ns=2;
%Определение первого центрального электрического жгута

125
N(p)=N(p)-2; N(q)=N(q)-2; n(p,q)=0; n(q,p)=0;
Ndd=zeros(11,11);P=zeros(11,11);
Q=zeros(11,11);
D=zeros(L,L); for i=1:11
for j=1:11
[ M01 M02]=timM(M1,M2,M3,M4,i);t,R]=mtranRT(M1,i); pij=ddaypT(d,N,M01,M02,R,i,j);
%
Б2
[Nij,bij]=timbnewT(d,N,n,M01,i,j);
%
Б1
Ndd(i,j)=Nij;
Q(i,j)=bij;
P(i,j)=pij; Bij=bij+pij;
if
(ismember(i,M01)==1)&(ismember(j,M01)==1)
D(i,j)=inf;
elseif
(ismember(i,M02)==1)&(ismember(j,M02)==1)
D(i,j)=inf;
elseif
(i>j)|(Bij==0)
D(i,j)=inf;
else
D(i,j)=Bij;
end end end
G=D; D(1,1)=0;
Nsd=Ndd
;
Qb=Q;
P=P
;
H=D;
l=1;
m=1;
A=[inf inf];
B=[1];
E=[];
E1=[1];
E2=[11];
X=[];minh=0;
%алгоритм Дейкстры поиска суммарной длины проводники(Б3)
while mif ismember(k,B)==0
A=[A;D(k,k) D(l,l)+D(l,k)];
else
A=[A;inf inf]; end end
A=A';
[x,y]=min(A); for i=1:L
if ismember(i,B)==0
D(i,i)=x(i);
end end
[z,h]=min(x);
s=y(h);
B=[B h];
minh=z;
X=[X; x]; B1=X(:,h);
B2=B1';
B3=find(B2==z);
s1=B3(1);
s2=B(s1);
E=[E; s2 h];
E1=E'; l=h; m=h; A=[inf inf]; end
E1=E1;s2=11;
while s2=1
[c1 c2]=find(E1==s2); c1=c1'; c2=c2'; s4=size(c1); for t1=1:s4

126 if c1(t1)==1 s3=E1(2,c2(t1));
else s3=E1(1,c2(t1));
end if s3>=s2
E1(:,c2(t1))=[]; s2=s2; else s2=s3; E2=[s3 E2];
E1(:,c2(t1))=[];
end end end
Bmin=B; Hmin=E2;Db=minh;
H1=nh3H(M0,M1,M2,M3,M4,u,w,Hmin);
%Определение второго центрального электрического жгута(
Б4)
s1=size(H1,2);
for s=1:(s1-1)
d(H1(s),H1(s+1))=inf; end
[Lp Hp Dp]=nh3pq1(d,p,q,M1,M2,M3,M4);
Hbd=Hmin
% Путь первого жгута проводников
Hpq=Hp
% Путь второго жгута проводников
Huw=H1
Dtd=Db+Dp
% минимальной длиной проводников
%Function 1: Определение уроненных матриц вершин i и j дуги ij function
[M01 M02]=timM(M1,M2,M3,M4,i)
if i==1
M01=[1]; M02=M1; elseif
(ismember(i,M1)==1)
M01=M1; M02=M2;
elseif
(ismember(i,M2)==1)
M01=M2; M02=M3;
elseif
(ismember(i,M3)==1)
M01=M3; M02=M4;
else
M01=[];M02=[];
end end
%Function 2: Определение Окращающей матрицы function
[t,R]=mtranRT(M1,i) m=size(M1,2); R1=[];
if i==1
R1=[1];
elseif i==11
R1=[1:11];
elseif
(ismember(i,M1)==1)
for k=1:M1(m)

127
R1=[R1 k];
end else
R1=[];
end
R=R1;
t=size(R,2);
end
%Function 3: Определение длины проводников дуги jj на боковом жгуте (
Б2
) function p = ddaypT(d,N,M1,M2,R,i,j)
N1=0; p1=0; N2=0; p2=0; N3=0; p3=0; N4=0; p4=0; m=size(M2,2);
if
(i==11)
p=0;
elseif j==1
p=0;
elseif j==11
p=0;
elseif d(i, j)==inf p=0;
else if
(ismember(i,M1)==1)&(ismember(j,M1)==1)&(ismember(j,R)==0) p=0;
elseif
(ismember(i,M2)==1)&(ismember(j,M2)==1)&(ismember(j,R)
==0)
p=0;
elseif
(j==M2(1))&((i==1)|(ismember(i,M1)==1))&(ismember(j,R)
==0)
for s5=M2(2):(M2(m))
for s6=s5:M2(m)
N3=N3+N(s6); end p3=p3+N3*d(s5-1,s5);N3=0;
end p=p3;
elseif
(j==M2(m))&(((i==1)|ismember(i,M1)==1))&(ismember(j,R)
==0)
for s7=M2(1):(M2(m-1)) for s8=M2(1):s7
N4=N4+N(s8); end p4=p4+N4*d(s7,s7+1); N4=0;
end p=p4; elseif
((i==1)|((ismember(i,M1)==1)&(ismember(j,M2)==1)&(ism embe r(j,R)==0)))&(j=M2(1))&(j=M2(m)) for s1=M2(1):(j-1)

128 for s2=M2(1):s1
N1=N1+N(s2);
end p1=p1+N1*d(s1,s1+1);
N1=0;
end for s3=j:(M2(m)-1)
for s4=s3+1:M2(m)
N2=N2+N(s4); end p2=p2+N2*d(s3,s3+1);
N2=0;
end p=p1+p2;
else p=0;
end end p=p;
end
%Function 4: Определение длины проводников дуги jj на централом жгуте (Б1)
function
[Nij,b]=timbnewT(d,N,n,M1,i,j)
R1=[];
m=size(M1,2); if
(i==1)
R1=[1];
elseif
(i==11)
R1=[1:11];
else for k=1:M1(m)
R1=[R1 k];
end end
R=R1; N1=0; N2=0;
t=size(R,2);
if i>j
Nij=0;b=0;
elseif i==j
Nij=N(i); b=0;
elseif d(i,j)==inf b=0; Nij=0;
else for s1=1:t
N1=N1+N(R(s1)); end for s2=1:t for s3=1:t
N2=N2+n(R(s2),R(s3));
end end
Nij=N1-N2;
b=d(i,j)*Nij;

129 end end
% Function 5: Определение пути проводниками, соединяющими приборы и устройства вершины u с приборами и устройствами вершины w(Путь центрального электрического жгута) function
H=nh3H(M0,M1,M2,M3,M4,u,w,h)
H=[];
if
(ismember(u,h)==1)&(ismember(w,h)==1)
[i1,j1]=find(h==u); [i2,j2]=find(h==w); for i=j1:j2
H=[H h(i)];
end elseif
(ismember(u,h)==1)&(ismember(w,h)==0)
[i1,j1]=find(h==u); M=nh3M(M0,M1,M2,M3,M4,w); k=intersect(M,h); [i2,j2]=find(M==w);
[i3,j3]=find(h==k); [i4,j4]=find(M==k); for i=j1:(j3-1)
H=[H h(i)];
end if w>k for i=j4:j2
H=[H M(i)]; end else s=k-w;
for i=0:s
H=[H M(j4-i)];
end end elseif
(ismember(u,h)==0)&(ismember(w,h)==1)
[i1,j1]=find(h==w); M=nh3M(M0,M1,M2,M3,M4,u); k=intersect(M,h);[i2,j2]=find(M==u);
[i3,j3]=find(h==k); [i4,j4]=find(M==k);
[i5,j5]=find(h==w); if u>k s=j2-j4; for i=0:s
H=[H M(j2-i)]; end else for i=j2:j4
H=[H M(i)];
end end for i=(j3+1):j5
H=[H h(i)];
end else

130
Mu=nh3M(M0,M1,M2,M3,M4,u);Mw=nh3M(M0,M1,M2,M3,M4,w); ku=intersect(Mu,h);kw=intersect(Mw,h);
[i1,j1]=find(h==ku); [i2,j2]=find(h==kw);
[i3,j3]=find(Mu==u); [i4,j4]=find(Mw==w);
[i5,j5]=find(Mu==ku);[i6,j6]=find(Mw==kw);
if u>ku s=j3-j5;
for i=0:(s-1);
H=[H Mu(j3-i)];
end else for i=j3:(j5-1)
H=[H M(i)];
end end for i=j1:(j2-1)
H=[H h(i)]; end if w>kw for i=j6:j4
H=[H Mu(i)];
end else s=j6-j4;
for i=0:s;
H=[H Mw(j6-i)]; end end end
H=H; end
%Function 6:
Определения пути проводниками, соединяющими приборы и устройства вершины p с приборами и устройствами вершины q с минимальной суммарной длиной проводников и с условием электромагнитной совместимости между проводниками, соединяющими приборы и устройства u-w и p-q function
[Lp Hp Dp]=nh3pq1(d,p,q,M1,M2,M3,M4)
L=11;
for i=1:L
for j=1:L
[M01 M02]=nh4_M(M1,M2,M3,M4,i);
if ismember(j,M01)==1 d(i,j)=inf;
else d(i,j)=d(i,j);
end end end

131
K=d;
D=d; L=11; D(p,p)=0; H=D; l=p; m=1; A=[inf inf]; B=[p];
E=[]; E1=[p]; E2=[q]; X=[]; minh=0;
%аллгорит Дейкстры пойска суммарной длины проводники while m=q for k=2:L
if ismember(k,B)==0
A=[A;D(k,k) D(l,l)+D(l,k)]; else
A=[A;inf inf];
end end
A=A';[x,y]=min(A); for i=2:L
if ismember(i,B)==0
D(i,i)=x(i); end end
[z,h]=min(x); s=y(h); B=[B h]; minh=z; X=[X; x];
B1=X(:,h); B2=B1'; B3=find(B2==z); s1=B3(1);
s2=B(s1); E=[E; s2 h];E1=E'; l=h; m=h; A=[inf inf];
end
E1=E1;s2=q;
while s2=p
[c1 c2]=find(E1==s2); c1=c1'; c2=c2'; s4=size(c1);
for t1=1:s4
if c1(t1)==1 s3=E1(2,c2(t1));
else s3=E1(1,c2(t1));
end if s3>=s2+2
E1(:,c2(t1))=[];s2=s2; else s2=s3; E2=[s3 E2]; E1(:,c2(t1))=[];
end end end
L2=B
;
Lp=E1; Hp=E2;Dp=2*minh;
end

132
Приложение 2: Описание шагов выполнения алгоритма
Алгоритм определения пути прокладывания жгутов с наименьшей суммарной длиной проводников к графу, изображенному на рис 1.4, для нахождения в нем кратчайшего пути между вершинами 1 и 11:
- Матрица количества проводников, соединяющих между устройствами:
L= [ 0 0 0 2 0 0 2 2 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 2 2 0 0 2 0 0 0 2 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 2 0 2 2 0 0 2 0 0 0 2 2 0 2 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 2 0 0 2 2 0 0 0 0 0 0]
- Матрица расстояния между вершинами A:
A=[∞ 2 2 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞
2 ∞ 1 ∞ 2 4 6 ∞ ∞ ∞ ∞
2 1 ∞ 1 4 2 4 ∞ ∞ ∞ ∞
2 ∞ 1 ∞ 6 4 2 ∞ ∞ ∞ ∞
∞ 2 4 6 ∞ 1 ∞ 2 4 6 ∞
∞ 4 2 4 1 ∞ 1 4 2 4 ∞
∞ 6 4 2 ∞ 1 ∞ 6 4 2 ∞
∞ ∞ ∞ ∞ 2 4 6 ∞ 1 ∞ 2
∞ ∞ ∞ ∞ 4 2 4 1 ∞ 1 2
∞ ∞ ∞ ∞ 6 4 2 ∞ 1 ∞ 2
∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 2 2 ∞]
- Матрица количества проводников N:
N= [10 4 0 10 6 0 10 10 0 4 6];

133
- Матрицы уровней М
k
M
1
= [1];
M
2
= [2 3 4];
M
3
= [5 6 7];
M
4
= [8 9 10];
M
5
= [11].
- Матрица длины проводников между вершинами:
D =[0 40 34 28 ∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ 60 96 132 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ 100 56 92 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ 140 96 52 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 40 78 116 ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 72 46 84 ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 104 78 52 ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 12
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 12
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 12
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞]
Последовательность действий для определения пути прокладывания жгутов с наименьшей суммарной длиной проводников на графе, изображенном на рис 4, между вершинами 1 и 11:
1.Перед первым выполнением шага 2 алгоритма окрашена только
Вершина 1. Кроме того D (1,1) =0 и D(х,х)=∞ для всех вершин х, не совпадающих с 1.
2. (у=1)
D (2,2) =min {D (2,2), D (1,1) +D (1,2)} =min {∞, 0+40} =40
D (3,3) =min {D (3,3), D (1,1) +D (1,3)} =min {∞, 0+34} =34
D (4,4) =min {D (4,4), D (1,1) +D (1,4)} =min {∞, 0+28} =28
D (5,5) =min {D (5,5), D (1,1) +D (1,5)} =min {∞, 0+∞} =∞
D (6,6) =min {D (6,6), D (1,1) +D (1,6)} =min {∞, 0+∞} =∞

134
D (7,7) =min {D (7,7), D (1,1) +D (1,7)} =min {∞, 0+∞} =∞
D (8,8) =min {D (8,8), D (1,1) +D (1,8)} =min {∞, 0+∞} =∞
D (9,9) =min {D (9,9), D (1,1) +D (1,9)} =min {∞, 0+∞} =∞
D (10,10) =min {D (10,10), D (1,1) +D (1,10)} =min {∞, 0+∞} =∞
D (11,11) =min {D (11,11), D (1,1) +D (1,11)} =min {∞, 0+∞} =∞
Поскольку величина D (4,4) =28 является минимальной из величин D
(2,2), D (3,3) …, D (11,11), то вершина 4 окрашивается. Так же окрашивается и дуга (1,4), которая и определяет величину D (4,4). Текущее дерево кратчайших путей состоит из дуги (1,4).
3.Поскольку вершина 11 остается неокрашенной, осуществляется переход к пункту 2
2. (у=4)
D (2,2) =min {D (2,2), D (4,4) +D (4,2)} =min {40, 28+∞} =40
D (3,3) =min {D (3,3), D (4,4) +D (4,3)} =min {34, 28+∞} =34
D (5,5) =min {D (5,5), D (4,4) +D (4,5)} =min {∞, 28+140} =168
D (6,6) =min {D (6,6), D (4,4) +D (4,6)} =min {∞, 28+96} =124
D (7,7) =min {D (7,7), D (4,4) +D (4,7)} =min {∞, 28+52} =80
D (8,8) =min {D (8,8), D (4,4) +D (4,8)} =min {∞, 28+∞} =∞
D (9,9) =min {D (9,9), D (4,4) +D (4,9)} =min {∞, 28+∞} =∞
D (10,10) =min {D (10,10), D (4,4) +D (4,10)} =min {∞, 28+∞} =∞
D (11,11) =min {D (11,11), D (4,4) +D (4,11)} =min {∞, 28+∞} =∞
Поскольку величина D (3,3) =34 является минимальной из величин D
(2,2), D (3,3) …, D (11,11), то вершина 2 окрашивается. Так же окрашивается и дуга (1,3), которая и определяет величину D (3,3). Текущее дерево кратчайших путей состоит из дуги (1,3).
3. Поскольку вершина 11 остается неокрашенной, осуществляется переход к пункту 2
2. (у=3)
D (2,2) =min {D (2,2), D (3,3) +D (3,2)} =min {40, 34+∞} =40
D (5,5) =min {D (5,5), D (3,3) +D (3,5)} =min {168, 34+100} =134

135
D (6,6) =min {D (6,6), D (3,3) +D (3,6)} =min {124, 34+56} =90
D (7,7) =min {D (7,7), D (3,3) +D (3,7)} =min {80, 34+92} =80
D (8,8) =min {D (8,8), D (3,3) +D (3,8)} =min {∞, 34+∞} =∞
D (9,9) =min {D (9,9), D (3,3) +D (3,9)} =min {∞, 34+∞} =∞
D (10,10) =min {D (10,10), D (3,3) +D (3,10)} =min {∞, 34+∞} =∞
D (11,11) =min {D (11,11), D (3,3) +D (3,11)} =min {∞, 34+∞} =∞
Поскольку величина D (2,2) =40 является минимальной из величин D
(2,2), D(5,5),…, D(11,11), то вершина 2 окрашивается. Так же окрашивается и дуга (1,2), которая и определяет величину D (2,2). Текущее дерево кратчайших путей состоит из дуги (1,2).
3. Поскольку вершина 11 остается неокрашенной, осуществляется переход к пункту 2
2. (у=2)
D (5,5) =min {D (5,5), D (2,2) +D (2,5)} =min {134, 40+60} =100
D (6,6) =min {D (6,6), D (2,2) +D (2,6)} =min {90, 40+96} =90
D (7,7) =min {D (7,7), D (2,2) +D (2,7)} =min {80, 40+92} =80
D (8,8) =min {D (8,8), D (2,2) +D (2,8)} =min {∞, 40+∞} =∞
D (9,9) =min {D (9,9), D (2,2) +D (2,9)} =min {∞, 40+∞} =∞
D (10,10) =min {D (10,10), D (2,2) +D (2,10)} =min {∞, 40+∞} =∞
D (11,11) =min {D (11,11), D (2,2) +D (2,11)} =min {∞, 40+∞} =∞
Поскольку величина D (7,7) =80 является минимальной из величин D
(5,5), D (6,6) …, D (11,11), то вершина 7 окрашивается. Так же окрашивается и дуга (4,7), которая и определяет величину D (7,7). Текущее дерево кратчайших путей состоит из дуги (4,7).