Кратчайшие пути в графах
© Захаров С.В., 2002 г.
Все приведённые в статье алгоритмы являются общеНАРОДным достоянием. Разрешается свободное их использование.
Нахождение кратчайшего пути между двумя атомами (т.е. количество лежащих между ними связей) часто требуется для предсказания свойств молекулы. Например, от расстояния до электроноакцепторной группы зависит её полярный (или индуктивный) эффект. Ниже приведён текст функции на Delphi, определяющей кратчайшее расстояние между двумя вершинами в графе:
// Нахождение длины кратчайшего пути между вершинами Top1 и Top2 в графе Graph.
// Если пути вовсе не существует, возвращает -1.
function GetShortestPath(Graph: TMathGraph; Top1, Top2: Integer): Integer;
label ex;
var
i,j,k,n: Integer;
p,p1: ^Integer;
Lst: TList;
begin
n:=Graph.TopCount-1;
if (n<1) or (Top1<0) or (Top2<0) or (Top1>n) or (Top2>n) then
begin Result:=-1; Exit; end;
if Top1=Top2 then begin Result:=0; Exit; end;
if Graph.Connected[Top1,Top2] then begin Result:=1; Exit; end;
Result:=n+1;
Lst:=TList.Create;
// Заполняем список указателями на динамически выделенные целые числа.
// Каждое число инициализируем значением Graph.TopCount.
AddIntegersToLst(Lst,n+1,n+1);
p:=Lst[Top1];
p^:=0;
for k:=1 to n do
begin
for i:=0 to n do
begin
p:=Lst[i];
if p^<k then Continue;
for j:=0 to n do
begin
if (i=j) or (not Graph.Connected[i,j]) then Continue;
p1:=Lst[j];
if (p^>k) and (p1^+1=k) then
begin
p^:=k;
if i=Top2 then
begin
Result:=p^;
goto ex;
end;
end;
end;
end;
end;
if Result=n+1 then Result:=-1;
ex:
// Освобождаем память, занимаемую содержимым списка и самим списком.
DisposeLst(Lst); Lst.Free;
end;
Иногда (хотя в приложениях к химии довольно редко) может понадобиться просто определить, существует ли вообще путь от одной вершины к другой. Путь между двумя атомами может отсутствовать, например, в структурных формулах ионных соединений (если атомы расположены в разных ионах), или в катенанах. Совокупность атомов в графе, между любой парой которых имеется путь, называется компонентой связности. Для определения, принадлежат ли две вершины в графе к одной и той же компоненте связности, используем процедуру MarkSubgraphViaRecursion, помечающую все вершины в графе, к которым имеется путь от заданной вершины:
// Функция определяет, существует ли путь от вершины Top1 к // вершине Top2 в графе Graph. function GraphPathExists(Graph: TMathGraph; Top1, Top2: Integer): Boolean; var i,n: Integer; strMark: string; begin n:=Graph.TopCount-1; for i:=0 to n do strMark:=strMark+'v'; MarkSubgraphViaRecursion(Graph,Top1,n,strMark); Result:=(strMark[Top2]='m'); end;