В этой лекции мы рассмотрим некоторые классические алгоритмы, использующие графы и деревья, приведем и сравним рекурсивные и итеративные их варианты.
Используемая здесь терминология полностью совпадает с терминологией, введенной в предыдущей лекции.
Одно и то же
((a / (b + c)) + (x * (y - z)))
Все арифметические операции, привычные нам со школьных лет, записываются именно таким образом.
+( /(a, +(b,c)), *(x, -(y,z)))
Из знакомых всем нам функций sin(x), tg(x), f(x,y,z) и т.п.
((a,(b,c)+ )/ ,(x,(y,z)- )* )+
Этот способ записи менее распространен, однако и с ним многим из нас приходилось сталкиваться уже в школе: примером будет n! (факториал).
Разумеется, вид
(рис 12.1) Дерево синтаксического анализа и способ описания его элементовtype ukaz = ^tree;
tree = record
symbol: char;
left: ukaz;
right: ukaz;
end;
Для простоты мы будем считать, что правильное
Если не достигнут конец строки ввода, прочитать
Если этот символ - открывающая скобка, то:
Иначе:
Мы воспользуемся здесь описанием типа данных ukaz, приведенным на рис. 12.1:
procedure infix(var p: ukaz);
var c: char;
begin
read(c);
if c = '('
then begin
new(p);
infix(p^.left);
read(p^.symbol); {'+', '-', '*', '/'}
infix(p^.right);
read(c); {')'}
end
else begin {'a'..'z','A'..'Z'}
new(p);
p^.symbol:= c;
p^.right:= nil;
p^.left:= nil
end;
end;
begin
...
infix(root);
...
end.
Для простоты предположим, что правильное
Вновь воспользуемся описанием типа данных ukaz, приведенным на рис. 12.1:
procedure prefix(var p: ukaz); begin new(p); read(p^.symbol); if p^.symbol in ['+','-','*','/'] then begin prefix(p^.left); prefix(p^.right); end else begin p^.left:= nil; p^.right:= nil; end end; begin ... prefix(root); ... end.
Для простоты предположим, что правильное
По окончании работы этого алгоритма в стеке будет содержаться ровно один элемент - указатель на корень построенного дерева.
Для того чтобы упростить работу, добавим в структуру элемента дерева (см. рис. 1.12) дополнительное поле next:ukaz, которое будет служить для связки стека:
stek:= nil;
while not eof(f) do
begin
new(p);
read(f,p^.symbol);
if p^.symbol in ['+','-','*','/']
then begin
p^.right:= stek;
p^.left:= stek^.next;
p^.next:= stek^.next^.next;
stek:= p
end
else begin
p^.left:= nil;
p^.right:= nil;
p^.next:= stek;
stek:= p
end;
end;
Прежде чем приступить к изложению алгоритмов обхода, дадим пару необходимых определений.
В этом разделе будут представлены только алгоритмы
Напомним, что структуру
type ukazatel = ^tree;
tree = record mark: integer;
left: ukazatel;
right: ukazatel;
end;
Итак, приступим теперь к изучению различных вариантов
Префиксный обход: результатом
Замечание: Этот алгоритм может быть естественным образом распространен и на случай произвольного
procedure preorder(p:ukaz; k:integer);
begin p^.mark:= k;
if p^.left<>nil then preorder(p^.left,k+1);
if p^.right<>nil then preorder(p^.right,k+1);
end;
begin
...
preorder(root,1); {Вызов из тела программы}
...
end.
(рис 12.2) Последовательность нумерации вершин при прямом обходе дерева Для простоты изложения будем считать, что граф задан
procedure preorder_graph(v: byte);
var i: byte;
begin
k:= k+1;
mark[v]:= k; {текущей вершине v присвоен порядковый номер}
for i:= 1 to n do
if (mark[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v
в еще не помеченную вершину i}
then preorder_graph(i);
end;
begin
...
k:= 0;
preorder_graph(start); {Вызов из тела программы}
...
end.
Постфиксный обход: результатом
Замечание: Этот алгоритм также может быть распространен на случай произвольного
(рис 12.3) Последовательность нумерации вершин при обратном обходе дерева
procedure postorder(p:ukaz; k:integer);
begin if p^.left<>nil then postorder(p^.left,k+1);
if p^.right<>nil then postorder(p^.right,k+1)
p^.mark:=k;
end;
begin
...
postorder(root,1); {Вызов из тела программы}
...
end.
Для простоты изложения будем считать, что граф задан posesh - о фактах их посещения:
procedure postorder_graph(v:byte);
var i: integer;
begin
posesh[v]:=1; {текущая вершина v стала посещенной}
for i:=1 to n do
if (posesh[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v
в еще не помеченную вершину i}
then postorder_graph(i);
inc(k);
mark[v]:=k; {текущей вершине v
присвоен порядковый номер}
end;
begin
...
k:=0;
postorder_graph(start); {вызов из тела программы}
...
end.
Инфиксный обход: результатом
Обход "слева направо": название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.
Замечание: Этот обход специфичен только для бинарных деревьев, поэтому невозможно применить его к произвольному графу, каркасом которого совершенно не обязательно будет именно
procedure syntorder(p:ukaz; k:integer);
begin if p^.left<>nil then syntorder(p^.left,k+1);
p^.mark:=k;
if p^.right<>nil then syntorder(p^.right,k+1);
end;
begin
...
syntorder(root,1); {Вызов из тела программы}
...
end.
(рис 12.4) Последовательность нумерации вершин при синтаксическом обходе дереваЗамечание: Этот алгоритм может быть естественным образом распространен и на случай произвольного
Для простоты реализации вновь пополним структуру дерева полем next:ukaz, которое будет служить для связки очереди:
head:= root;
tail:= root;
k:= 0;
repeat
tail^.next:= head^.left;
if head^.left<>nil then tail:= tail^.next;
tail^.next:= head^.right;
if head^.right<>nil then tail:= tail^.next;
inc(k);
head^.znachenie:= k; {можно write(head^.znachenie);}
head:= head^.next
until head = nil;
(рис 12.5) Последовательность нумерации вершин при обходе дерева в ширину
Задача. Упорядочить заданный набор (возможно, с повторениями) некоторых элементов (чисел, слов, т.п.).
nil Мы приведем реализацию первого шага алгоритма, сортирующего числа (для элементов другой природы потребуется изменить только процесс считывания):
new(root);
read(f,root^.chislo);
root^.kol:= 1;
root^.left:= nil;
root^.right:= nil;
while not eof(f) do
begin
read(f,x);
p:= root;
while true do
begin
if x = p^.chislo
then begin inc(p^.kol);
break
end;
if x > p^.chislo
then if p^.right <> nil
then p:= p^.right
else begin new(p^.right);
p:= p^.right;
p^.chislo:= x;
p^.kol:= 1;
p^.left:= nil;
p^.right:= nil;
break
end
(* x < p^.chislo *)
else if p^.left <> nil
then p:= p^.left
else begin new(p^.left);
p:= p^.left;
p^.chislo:= x;
p^.kol:= 1;
p^.left:= nil;
p^.right:= nil;
break
end
end;
end;
Задача. Определить количество
Считаем, что граф задан
Каждый элемент специального линейного массива
Рекурсивная процедура
По окончании работы программы переменная kol будет содержать количество найденных
procedure step (v: integer);
var j: integer;
begin
mark[v]:= k;
for j:=1 to N do
if (mark[j]=0)and(sm[v,j]<>0) then step(j);
end;
begin
...
for i:= 1 to N do mark[i]:=0;
k:= 0; {номер текущей компоненты связности}
for i:= 1 to N do
if mark[i]=0 then
begin inc(k);
step(i);
end;
...
end.
Для этого алгоритма удобно, чтобы граф был представлен списком ребер.
Массив
Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:
mark [u]=0mark [v]=0kol увеличивается на единицу, а новая ks+1.mark [u]=0mark [v]<>0kol остается прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.mark [u]= mark [v]<>0kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменен будет номер именно самой последней компоненты По окончании работы этого алгоритма в массиве S различных целых чисел, каждое из которых будет означать отдельную компоненту
kol:=0;
ks:=0;
while not eof(f) do
begin
readln(f,u,v);
if mark[u]=0
then if mark[v]=0
then begin {случай 1}
inc(kol);
inc(ks);
mark[u]:= ks;
mark[v]:= ks;
end
else mark[u]:= mark[v] {случай 2}
else if mark[v]=0
then mark[v]:= mark[u]
{случай 2 - симметричный}
else if mark[u]<>mark[v] {случай 4}
then begin
max:= v;
min:= u;
if u>v then begin
max:= u;
min:= v end;
for i:= 1 to n do
if mark[i]= max
then mark[i]:= min;
dec(kol);
end
end;
for i:=1 to N do
if mark[i]=0 then inc(kol);
В худшем случае (при (N-1)! раз. Велика вероятность, что при достаточно большом N произойдет переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной 250 (см. лекцию 3).
N*(N+1)/2. В половине этих случаев возможна ситуация объединения двух N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N3/8. Возможное количество 32 000 ).
Задача. В заданном взвешенном
Этот алгоритм базируется на N-1 N - количество
procedure step(v,k: byte; r: longint);
var j: byte;
begin
if r < min then
if k = N-1
then min:= r
else for j:= 1 to N do
if (sm[v,j]<>0)and(mark[j]=0)
then begin
mark[j]:= 1;
step(j,k+1,r+sm[v,j]);
mark[j]:= 0
end;
end;
begin
...
for i:= 1 to N do mark[i]:= 0;
min:= MaxLongInt;
for i:= 1 to N do
begin mark[i]:=1;
step(i,1,0);
mark[i]:=0;
end;
writeln(min);
...
end.
Для того чтобы помимо суммарного веса каркаса алгоритм также запоминал включенные в каркас ребра, необходимо добавить дополнительный квадратный массив, в котором будут храниться пометки включения ребер в каркас.
Замечание: Выполнение N-1 )-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).
Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз-Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчет добавленных в каркас ребер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счетчик добавленных ребер станет равным N-1.
Задача. В заданном взвешенном s до вершины t. Веса всех ребер строго положительны.
Совершить t производится сравнение длины текущего пути с ранее найденным минимумом.
Пусть граф задан
procedure rasst(v: byte; r: longint);
var i: byte;
begin
if v = t
then if r< min then min:= r
else
else for i:= 1 to N do
if (mark[i]=0)and(sm[v,i]<>0)
then begin mark[i]:=1;
rasst(i,r+sm[v,i]);
mark[i]:=0
end
end;
begin
...
for i:= 1 to N do mark[i]:= 0;
min:= MaxLongInt;
mark[s]:= 1;
rasst(s,0);
mark[s]:= 0;
...
end.
s не только до одной вершины t, но и до всех остальных
Итак, пусть граф задан
dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими "бесконечность". По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.
Еще один done потребуется нам для того, чтобы хранить информацию о том, найден ли уже минимальный путь (он же расстояние) до соответствующей вершины и можно ли исключить эту вершину из дальнейшего рассмотрения.
Переменная last будет хранить номер последней помеченной вершины.
Отметим особо, что на каждом шаге N-1 итераций.
Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше - ведь веса всех ребер графа у нас положительны. Таким образом:
dist[s]:= 0; done[s]:= true; last:= s;
Повторить N-1 раз следующие действия:
для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:
dist[x]:= min(dist[x], dist[last]+ sm[last,x]);
dist: это будет новая вершина last ;done.Мы надеемся, что функцию поиска меньшего из двух целых чисел min, использованную в тексте программы, читатели смогут написать самостоятельно.
dist[s]:= 0; done[s]:= true; last:= s; for i:= 1 to N-1 do begin for x:= 1 to N do if (sm[last,x]<>0)and(not done[x]) then dist[x]:= min(dist[x],dist[last]+ sm[last,x]); min_dist:= MaxLongInt; for x:= 1 to N do if (not done[x])and(min_dist>dist[x]) then begin min_dist:= dist[x]; last:= x; end; done[last]:= true; end.
Сложность рекурсивного алгоритма пропорциональна N!, а ~N2. Комментарии, как говорится, излишни.
В этой лекции мы рассмотрим некоторые классические алгоритмы, использующие графы и деревья, приведем и сравним рекурсивные и итеративные их варианты.
Используемая здесь терминология полностью совпадает с терминологией, введенной в предыдущей лекции.
Одно и то же
((a / (b + c)) + (x * (y - z)))
Все арифметические операции, привычные нам со школьных лет, записываются именно таким образом.
+( /(a, +(b,c)), *(x, -(y,z)))
Из знакомых всем нам функций sin(x), tg(x), f(x,y,z) и т.п.
((a,(b,c)+ )/ ,(x,(y,z)- )* )+
Этот способ записи менее распространен, однако и с ним многим из нас приходилось сталкиваться уже в школе: примером будет n! (факториал).
Разумеется, вид
(рис 12.1) Дерево синтаксического анализа и способ описания его элементовtype ukaz = ^tree;
tree = record
symbol: char;
left: ukaz;
right: ukaz;
end;
Для простоты мы будем считать, что правильное
Если не достигнут конец строки ввода, прочитать
Если этот символ - открывающая скобка, то:
Иначе:
Мы воспользуемся здесь описанием типа данных ukaz, приведенным на рис. 12.1:
procedure infix(var p: ukaz);
var c: char;
begin
read(c);
if c = '('
then begin
new(p);
infix(p^.left);
read(p^.symbol); {'+', '-', '*', '/'}
infix(p^.right);
read(c); {')'}
end
else begin {'a'..'z','A'..'Z'}
new(p);
p^.symbol:= c;
p^.right:= nil;
p^.left:= nil
end;
end;
begin
...
infix(root);
...
end.
Для простоты предположим, что правильное
Вновь воспользуемся описанием типа данных ukaz, приведенным на рис. 12.1:
procedure prefix(var p: ukaz); begin new(p); read(p^.symbol); if p^.symbol in ['+','-','*','/'] then begin prefix(p^.left); prefix(p^.right); end else begin p^.left:= nil; p^.right:= nil; end end; begin ... prefix(root); ... end.
Для простоты предположим, что правильное
По окончании работы этого алгоритма в стеке будет содержаться ровно один элемент - указатель на корень построенного дерева.
Для того чтобы упростить работу, добавим в структуру элемента дерева (см. рис. 1.12) дополнительное поле next:ukaz, которое будет служить для связки стека:
stek:= nil;
while not eof(f) do
begin
new(p);
read(f,p^.symbol);
if p^.symbol in ['+','-','*','/']
then begin
p^.right:= stek;
p^.left:= stek^.next;
p^.next:= stek^.next^.next;
stek:= p
end
else begin
p^.left:= nil;
p^.right:= nil;
p^.next:= stek;
stek:= p
end;
end;
Прежде чем приступить к изложению алгоритмов обхода, дадим пару необходимых определений.
В этом разделе будут представлены только алгоритмы
Напомним, что структуру
type ukazatel = ^tree;
tree = record mark: integer;
left: ukazatel;
right: ukazatel;
end;
Итак, приступим теперь к изучению различных вариантов
Префиксный обход: результатом
Замечание: Этот алгоритм может быть естественным образом распространен и на случай произвольного
procedure preorder(p:ukaz; k:integer);
begin p^.mark:= k;
if p^.left<>nil then preorder(p^.left,k+1);
if p^.right<>nil then preorder(p^.right,k+1);
end;
begin
...
preorder(root,1); {Вызов из тела программы}
...
end.
(рис 12.2) Последовательность нумерации вершин при прямом обходе дереваДля простоты изложения будем считать, что граф задан
procedure preorder_graph(v: byte);
var i: byte;
begin
k:= k+1;
mark[v]:= k; {текущей вершине v присвоен порядковый номер}
for i:= 1 to n do
if (mark[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v
в еще не помеченную вершину i}
then preorder_graph(i);
end;
begin
...
k:= 0;
preorder_graph(start); {Вызов из тела программы}
...
end.
Постфиксный обход: результатом
Замечание: Этот алгоритм также может быть распространен на случай произвольного
(рис 12.3) Последовательность нумерации вершин при обратном обходе дерева
procedure postorder(p:ukaz; k:integer);
begin if p^.left<>nil then postorder(p^.left,k+1);
if p^.right<>nil then postorder(p^.right,k+1)
p^.mark:=k;
end;
begin
...
postorder(root,1); {Вызов из тела программы}
...
end.
Для простоты изложения будем считать, что граф задан posesh - о фактах их посещения:
procedure postorder_graph(v:byte);
var i: integer;
begin
posesh[v]:=1; {текущая вершина v стала посещенной}
for i:=1 to n do
if (posesh[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v
в еще не помеченную вершину i}
then postorder_graph(i);
inc(k);
mark[v]:=k; {текущей вершине v
присвоен порядковый номер}
end;
begin
...
k:=0;
postorder_graph(start); {вызов из тела программы}
...
end.
Инфиксный обход: результатом
Обход "слева направо": название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.
Замечание: Этот обход специфичен только для бинарных деревьев, поэтому невозможно применить его к произвольному графу, каркасом которого совершенно не обязательно будет именно
procedure syntorder(p:ukaz; k:integer);
begin if p^.left<>nil then syntorder(p^.left,k+1);
p^.mark:=k;
if p^.right<>nil then syntorder(p^.right,k+1);
end;
begin
...
syntorder(root,1); {Вызов из тела программы}
...
end.
(рис 12.4) Последовательность нумерации вершин при синтаксическом обходе дереваЗамечание: Этот алгоритм может быть естественным образом распространен и на случай произвольного
Для простоты реализации вновь пополним структуру дерева полем next:ukaz, которое будет служить для связки очереди:
head:= root;
tail:= root;
k:= 0;
repeat
tail^.next:= head^.left;
if head^.left<>nil then tail:= tail^.next;
tail^.next:= head^.right;
if head^.right<>nil then tail:= tail^.next;
inc(k);
head^.znachenie:= k; {можно write(head^.znachenie);}
head:= head^.next
until head = nil;
(рис 12.5) Последовательность нумерации вершин при обходе дерева в ширину
Задача. Упорядочить заданный набор (возможно, с повторениями) некоторых элементов (чисел, слов, т.п.).
nil Мы приведем реализацию первого шага алгоритма, сортирующего числа (для элементов другой природы потребуется изменить только процесс считывания):
new(root);
read(f,root^.chislo);
root^.kol:= 1;
root^.left:= nil;
root^.right:= nil;
while not eof(f) do
begin
read(f,x);
p:= root;
while true do
begin
if x = p^.chislo
then begin inc(p^.kol);
break
end;
if x > p^.chislo
then if p^.right <> nil
then p:= p^.right
else begin new(p^.right);
p:= p^.right;
p^.chislo:= x;
p^.kol:= 1;
p^.left:= nil;
p^.right:= nil;
break
end
(* x < p^.chislo *)
else if p^.left <> nil
then p:= p^.left
else begin new(p^.left);
p:= p^.left;
p^.chislo:= x;
p^.kol:= 1;
p^.left:= nil;
p^.right:= nil;
break
end
end;
end;
Задача. Определить количество
Считаем, что граф задан
Каждый элемент специального линейного массива
Рекурсивная процедура
По окончании работы программы переменная kol будет содержать количество найденных
procedure step (v: integer);
var j: integer;
begin
mark[v]:= k;
for j:=1 to N do
if (mark[j]=0)and(sm[v,j]<>0) then step(j);
end;
begin
...
for i:= 1 to N do mark[i]:=0;
k:= 0; {номер текущей компоненты связности}
for i:= 1 to N do
if mark[i]=0 then
begin inc(k);
step(i);
end;
...
end.
Для этого алгоритма удобно, чтобы граф был представлен списком ребер.
Массив
Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:
mark [u]=0mark [v]=0kol увеличивается на единицу, а новая ks+1.mark [u]=0mark [v]<>0kol остается прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.mark [u]= mark [v]<>0kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменен будет номер именно самой последней компоненты По окончании работы этого алгоритма в массиве S различных целых чисел, каждое из которых будет означать отдельную компоненту
kol:=0;
ks:=0;
while not eof(f) do
begin
readln(f,u,v);
if mark[u]=0
then if mark[v]=0
then begin {случай 1}
inc(kol);
inc(ks);
mark[u]:= ks;
mark[v]:= ks;
end
else mark[u]:= mark[v] {случай 2}
else if mark[v]=0
then mark[v]:= mark[u]
{случай 2 - симметричный}
else if mark[u]<>mark[v] {случай 4}
then begin
max:= v;
min:= u;
if u>v then begin
max:= u;
min:= v end;
for i:= 1 to n do
if mark[i]= max
then mark[i]:= min;
dec(kol);
end
end;
for i:=1 to N do
if mark[i]=0 then inc(kol);
В худшем случае (при (N-1)! раз. Велика вероятность, что при достаточно большом N произойдет переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной 250 (см. лекцию 3).
N*(N+1)/2. В половине этих случаев возможна ситуация объединения двух N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N3/8. Возможное количество 32 000 ).
Задача. В заданном взвешенном
Этот алгоритм базируется на N-1 N - количество
procedure step(v,k: byte; r: longint);
var j: byte;
begin
if r < min then
if k = N-1
then min:= r
else for j:= 1 to N do
if (sm[v,j]<>0)and(mark[j]=0)
then begin
mark[j]:= 1;
step(j,k+1,r+sm[v,j]);
mark[j]:= 0
end;
end;
begin
...
for i:= 1 to N do mark[i]:= 0;
min:= MaxLongInt;
for i:= 1 to N do
begin mark[i]:=1;
step(i,1,0);
mark[i]:=0;
end;
writeln(min);
...
end.
Для того чтобы помимо суммарного веса каркаса алгоритм также запоминал включенные в каркас ребра, необходимо добавить дополнительный квадратный массив, в котором будут храниться пометки включения ребер в каркас.
Замечание: Выполнение N-1 )-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).
Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз-Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчет добавленных в каркас ребер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счетчик добавленных ребер станет равным N-1.
Задача. В заданном взвешенном s до вершины t. Веса всех ребер строго положительны.
Совершить t производится сравнение длины текущего пути с ранее найденным минимумом.
Пусть граф задан
procedure rasst(v: byte; r: longint);
var i: byte;
begin
if v = t
then if r< min then min:= r
else
else for i:= 1 to N do
if (mark[i]=0)and(sm[v,i]<>0)
then begin mark[i]:=1;
rasst(i,r+sm[v,i]);
mark[i]:=0
end
end;
begin
...
for i:= 1 to N do mark[i]:= 0;
min:= MaxLongInt;
mark[s]:= 1;
rasst(s,0);
mark[s]:= 0;
...
end.
s не только до одной вершины t, но и до всех остальных
Итак, пусть граф задан
dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими "бесконечность". По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.
Еще один done потребуется нам для того, чтобы хранить информацию о том, найден ли уже минимальный путь (он же расстояние) до соответствующей вершины и можно ли исключить эту вершину из дальнейшего рассмотрения.
Переменная last будет хранить номер последней помеченной вершины.
Отметим особо, что на каждом шаге N-1 итераций.
Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше - ведь веса всех ребер графа у нас положительны. Таким образом:
dist[s]:= 0; done[s]:= true; last:= s;
Повторить N-1 раз следующие действия:
для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:
dist[x]:= min(dist[x], dist[last]+ sm[last,x]);
dist: это будет новая вершина last ;done.Мы надеемся, что функцию поиска меньшего из двух целых чисел min, использованную в тексте программы, читатели смогут написать самостоятельно.
dist[s]:= 0; done[s]:= true; last:= s; for i:= 1 to N-1 do begin for x:= 1 to N do if (sm[last,x]<>0)and(not done[x]) then dist[x]:= min(dist[x],dist[last]+ sm[last,x]); min_dist:= MaxLongInt; for x:= 1 to N do if (not done[x])and(min_dist>dist[x]) then begin min_dist:= dist[x]; last:= x; end; done[last]:= true; end.
Сложность рекурсивного алгоритма пропорциональна N!, а ~N2. Комментарии, как говорится, излишни.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.