Правильность этих результатов ** была подтверждена при исследовании сетевых диаграмм.

АЛГОРИТМ 976

Кратчайший путь [Н]

Первоначально m[t,/]-это длина прямой связи от точки i сети до точки /. Если прямой связи между этими точками не существует, то

* В переводе ради наглядиостн символы Т л F заменены на 1 и О соответственно. (Прим. ред.)

** Вторая матрица (для п=6) здесь не приводится, поскольку в оригинале она .задана неправильно. (Прим. ред.)

Алгоритм 966 является стереотипным переизданием алгоритма 96а, правильность которого была подтверждена также И расчетами Г. В. Пе-ледова 125, с. 174]. Автор алгоритма 96 ссылается на работу С. Уаршала [31].

Свидетельство к алгоритму 96а

Алгоритм 96а получен в результате ординарной переработки алгоритма 96 (Floyd R.W. «САСМ», 1962, № 6).

Путем трансляции подтверждена правильность результатов для первой и третьей матрицы нижеследующего «Подтверждения к алгоритму 96» («САСМ», 1963, № 3). Вторая матрица в этом подтверждении задана неверно, поскольку она должна быть квадратной.

Подтверждение к алгоритму 96

Г. Тачер (Th а ch ег Н. С. «САСМ», 1963, № 3) Тело этой процедуры .было проверено на машине LGP 30 с использованием дартмутского транслятора. После заключения условных операторов в скобки begin и end (это необходимо для данного транслятора) процедура работала удовлетворительно для следующих матриц*: п=5, время 8 мин 16 с

m[i,j\ первоначально равно Ю*". После вьшолнения процедуры m[t,/] будет длиной кратчайшего пути от i до /. Если такового «е существует то m[i,j]-lO*. Массив т имеет размерность {1:п,1:п]. Более подробно см. в работе С. Уаршала [31].

procedure shortest path (n) dataresult: (m);

value n; integer n; array m; begin real inf.s; integer i,j,k;

inf:=iolO;

for i: = l step 1 until n do for j: = l step 1 until n do if m[j,i]<inf then for k:= 1 step 1 until n do if m[i,k]<inf then

begin s:=m[j,i]+mli,k];

if s<m[j,k] then m[j,k]: = s end

end shortest path;

Свидетельство к алгоритму 976

Алгоритм 976 является стереотипным переизданием алгоритма 97а.

Алгоритм 976 был транслирован на машине М-220 в системе ТА-1М, и с его помощью была решена следующая простая задача: найти кратчайшие пути между узловыми точками сети, изображенной на рис. 1.

Задавались параметры п=4 и

О 20 20 О 50 15

50 10 15 ,о10 О 30

10 ,о10 30 О Были получены следующие правильные результаты:

О 20 35 10

20 О 15 30 35 15 О 30 10 30 30 О

Другой алгоритм определения кратчайшего пути описан в работе Алексеевой С. М. и Алексеева О. Г. [43].

Свидетельство к алгоритму 97а

Процедура shortest path алгоритма 97а, .по существу, не отличается от /процедуры алгоритма 97 (Floyd R. W. «САСМ», 1962, № 6).

АЛГОРИТМ 986

Комплексный криволинейный интеграл [D1]

Процедура complint приближенно вычисляет комплексный криволинейный интеграл с помощью конечной суммы Римана - Стилтьеса

2 /(Zfe)[Zf -2<-г]. где a<t<b и z*G(zt-„ zt).

tz=l

Программист должен задать:

1) процедуру gamma{t,z) для вычисления z{t) на кривой Г и процедуру func (zj) для вычисления значений функции;

2) концевые точки а и b интервала изменения параметра и п- число подынтервалов, на которые должен быть разбит интервал [а,Ь].

procedure complint(a,b,n) result: (suml,sum2);

value a,b,n; real a,b,n,suml,sum2; begin real t,d,ztl I,ztl2,delzl,delz2,partl,part2;

integer i: array zt,zk,fz[l:2];

suml:=sum2:=0;

d:=:(b-a)/n; t: = a; line: gamma (t,zt);

If t=a then go to next;

delz 1:=ztll]~ztl 1; delz2: = zt[2]-ztl2;

zk[l]:=ztll +delzl/2; zk[2]:=ztl2+delz2/2;

func(zk,fz);

partl:=fz[l]xdelzl-fzI2]Xdelz2;

p art2: = f41] X delz2+fz[2 X delz 1;

sum 1: = sum 1 -b part 1;

sum2:=sum2+part2;

if tb-0.25Xd then go to final; next: ztll:=zt[l]; ztl2:=ztl2];

t:=t-bd;

go to line; final: end complint;

Свидетельство к алгоритму

Алгоритм 986 является стереотипным переизданием алгоритма 98а.

Алгоритм 986 был транслирован на машине БЭСМ-6 в системе БЭСМ-АЛГОЛ при n=il, 10, 25, 50, 100, 250, 500, 1000, 2000 для следующих задач из сборника Вол1ковыского Л. И. и др. {35].

/. Задача 888 (1). Вычисление h-i xdz и h= i ydz no радиусу-вектору точки 2=2+1